Difference between revisions of "Algorithm Problems"

Revision as of 23:46, 22 February 2012

Binary Tree

Binary search

def search_binary_tree(node, key):
     if node is None:
         return None  # key not found
     if key < node.key:
         return search_binary_tree(node.leftChild, key)
     elif key > node.key:
         return search_binary_tree(node.rightChild, key)
     else:  # key is equal to node key
         return node.value  # found key

Binary tree insert

 /* Inserts the node pointed to by "newNode" into the subtree rooted at "treeNode" */
 void InsertNode(Node* &treeNode, Node *newNode)
 {
     if (treeNode == NULL)
       treeNode = newNode;
     else if (newNode->key < treeNode->key)
       InsertNode(treeNode->left, newNode);
     else
       InsertNode(treeNode->right, newNode);
 }

Binary tree depth

///////////////////////////////////////////////////////////////////////
// Get depth of a binary tree
// Input: pTreeNode - the head of a binary tree
// Output: the depth of a binary tree
///////////////////////////////////////////////////////////////////////
int TreeDepth(SBinaryTreeNode *pTreeNode)
{
      // the depth of a empty tree is 0
      if(!pTreeNode)
            return 0;

      // the depth of left sub-tree
      int nLeft = TreeDepth(pTreeNode->m_pLeft);
      // the depth of right sub-tree
      int nRight = TreeDepth(pTreeNode->m_pRight);

      // depth is the binary tree
      return (nLeft > nRight) ? (nLeft + 1) : (nRight + 1);

Print linklist inversed

///////////////////////////////////////////////////////////////////////
// Print a list from end to beginning
// Input: pListHead - the head of list
///////////////////////////////////////////////////////////////////////
void PrintListReversely(ListNode* pListHead)
{
      if(pListHead != NULL)
      {
            // Print the next node first
            if (pListHead->m_pNext != NULL)
            {
                  PrintListReversely(pListHead->m_pNext);
            }
 
            // Print this node
            printf("%d", pListHead->m_nKey);
      }
}

Inverse Array

for (int i = 0; i < b; i=i++){
char temp1 = a[i];
a[i] = a[(b-1)-i];
a[(b-1)-i] = temp1;
cout << a[i] ;
}

Find duplicate numbers in array

<?php
/* 
Find duplicate number in array
*/
//construct $b[n]=n
$b=array();
$duplicateArr=array();
$a=array("1","3","4","1","5","2","8","3","2244","1");
for($i=0;$i<sizeof($a);$i++){
	if(isset($b[$a[$i]]))
		array_push($duplicateArr,$a[$i]);
	else
	$b[$a[$i]]=$a[$i];
}
var_dump($duplicateArr);
?>

interpolation search

 public int interpolationSearch(int[] sortedArray, int toFind){
  // Returns index of toFind in sortedArray, or -1 if not found
  int low = 0;
  int high = sortedArray.length - 1;
  int mid;
 
  while (sortedArray[low] <= toFind && sortedArray[high] >= toFind) {
   mid = low +
         ((toFind - sortedArray[low]) * (high - low)) /
         (sortedArray[high] - sortedArray[low]);  //out of range is possible  here
 
   if (sortedArray[mid] < toFind)
    low = mid + 1;
   else if (sortedArray[mid] > toFind)
    // Repetition of the comparison code is forced by syntax limitations.
    high = mid - 1;
   else
    return mid;
  }
 
  if (sortedArray[low] == toFind)
   return low;
  else
   return -1; // Not found
 }