Difference between revisions of "Algorithm Problems"

Revision as of 04:01, 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);

<?php $n=6; $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; } // 3/5 -> 2/4 -> 1/3 || 3/5 -> select 2nd 2/3-> 1/3 function select($list,$k,$head="") { $n=sizeof($list); //end condition if($n<$k) return; if($n==$k && $k>1){ echo $head.implode(' ',$list).'
'; } else if($k==1){ for($i=0;$i<$n;$i++) echo $head.$list[$i].'
'; } else if($n>$k){ for($i=0;$i<=$n-$k;$i++){//select the smallest element 4-3=1 //delete $i element and before in array $list1=delete($list,$i);//delete all elements before $i $head1=$head.$list[$i].' ';//construct head select($list1,$k-1,$head1);//select $k-1 from ($n-$i) } } } echo select($list,$k);