Difference between revisions of "Algorithm Problems"

Revision as of 23:21, 1 March 2012

Binary Tree

All about Binary search tree
All about Linked List

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 in order

<?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).'<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 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);

Max sub array

Kadane's algorithm

Kadane's algorithm consists of a scan through the array values, computing at each position the maximum subarray ending at that position. This subarray is either empty (in which case its sum is zero) or consists of one more element than the maximum subarray ending at the previous position. Thus, the problem can be solved with the following code, expressed here in Python:

def max_subarray(A):
    max_so_far = max_ending_here = 0
    for x in A:
        max_ending_here = max(0, max_ending_here + x)
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far

Sub sum NP problem

<?php
//Sub sum problem NP
$arr=array(2,1,3,1,6,5,6,2,8,4);
function subsum($arr,$sum,$head=""){
	//find a possible num.
	if($sum<=0||sizeof($arr)==0)
	return;
	foreach($arr as $i=>$a){
		if ($a>$sum){
			unset($arr[$i]);
			continue;
		}
		else if($a==$sum){//this is the only possbility
			echo "Result: ".$head.$a." from sum $sum & head $head & a=$a<br />";
			unset($arr[$i]);
			return;
		}
		else{
			//keep $a
			$head1=$head.$a." ";
			unset($arr[$i]);
			//echo "case3: keep a=$a and send to sum".($sum-$a)." with head=$head and arr_len=".sizeof($arr)."<br />";
			subsum($arr,$sum-$a,$head1);
			//skip $a then continue
		}
	}
	return;
}
subsum($arr,5);
/* output
Result: 2 1 2 from sum 2 & head 2 1 & a=2
Result: 2 3 from sum 3 & head 2 & a=3
Result: 1 3 1 from sum 1 & head 1 3 & a=1
Result: 1 4 from sum 4 & head 1 & a=4
Result: 3 2 from sum 2 & head 3 & a=2
Result: 1 4 from sum 4 & head 1 & a=4
Result: 5 from sum 5 & head & a=5
*/