Difference between revisions of "Algorithm Problems"

Revision as of 01:34, 29 February 2012

Binary Tree

All about Binary search tree

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
 }

Random Selector

Select k smallest value in array. O(n)

<?php
function swap(&$a,&$b){
	if($a!=$b)
	$a=$a+$b-($b=$a);
	//$a^=$b^=$a^=$b;
}
 function partition(&$listArr, $left, $right, $pivotIndex){
     $pivotValue = $listArr[$pivotIndex];
	 swap($listArr[$pivotIndex],$listArr[$right]);
     $storeIndex = $left;
	 echo "L: $left ,pval: $pivotValue ,right: $right <br />";
     for ($i =$left;$i< $right;$i++){
         if ($listArr[$i] < $pivotValue){
		 swap($listArr[$storeIndex] ,$listArr[$i]);
             //$listArr[$storeIndex] ^= $listArr[$i]^= $listArr[$storeIndex]^= $listArr[$i]; //This has a bug
             $storeIndex++;
			 }
	 }
	 swap($listArr[$right],$listArr[$storeIndex]); // Move pivot to its final place
	 var_dump($listArr);
     return $storeIndex;
}
//select k smallest value
function select($listArr, $left, $right, $k){
         $pivotIndex = floor(($right+$left)/2);
         $pivotNewIndex = partition($listArr, $left, $right, $pivotIndex);
         $pivotDist = $pivotNewIndex - $left + 1;
		 //var_dump($listArr);
		 //echo $pivotDist." ".$left.' '.$right." $k<br />";
         if ($pivotDist == $k)
             return $listArr[$pivotNewIndex];
		else if ($pivotDist>$k )
			return select($listArr, $left, $pivotNewIndex - 1, $k);
		else
			return select($listArr, $pivotNewIndex + 1, $right, $k - $pivotDist);
}
$Arr=array(1,29,3,45,5,6,7,8,9,0,22,36,88,66,44,55,33,22,14,23,31,16,94,25,10,11,12,13,2,4);
echo 'final result:'.select($Arr, 0, sizeof($Arr)-1,10);

N Choose K with order

<?php
$n=5;
$k=3;
$list=array();
for($i=0;$i<$n;$i++){
	$list[$i]=$i;
}
function delete($list,$i){
$res=array();
	for($j=0;$j<sizeof($list);$j++){
		if($j>$i)
		array_push($res,$list[$j]);
	}
	//var_dump($res);
	return $res;
}
function select($list,$k,$head="")	{
	$n=sizeof($list);
	//end condition
	if($n<$k)
	return;
	if($n==$k){
		echo $head.implode(' ',$list).'<br />';
	}
	else if($k==1){
		for($i=0;$i<$n;$i++)
		echo $head.$list[$i].'<br />';
	}
	else if($n>$k){
		for($i=0;$i<=$n-$k;$i++){//select the smallest element
		//echo "i=$i<br /> ";
		//delete $i element and before in array
		$list1=delete($list,$i);
		$head1=$head.$list[$i].' ';
		select($list1,$k-1,$head1);
		}
	}
}
echo select($list,$k);