Difference between revisions of "Algorithm Problems"

Latest revision as of 05:22, 3 August 2014

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/2; 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);
?>

Extention read http://www.geeksforgeeks.org/find-duplicates-in-on-time-and-constant-extra-space/

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

Find a sub array which sum equals to 4.
input : {1,2,4,5,6,1,2,4,3,5,7,2,1}
output : {1,1,2}, {2,2}, {3,1}, {1,2,1}

<?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]); // Unset only affects the current level of array. Does not affect the original outside this function.
			//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
*/

Swap 2 numbers in one line

//swap
$a=10;
$b=20;
$a=$a+$b-($b=$a);
echo $a." and ". $b."\n";
// output 20 and 10
$a^=$b^=$a^=$b; //This has a bug. You cannot do things like this $a^=$a^=$a^=$a
echo $a." and ". $b;
//output 10 and 20

Calculate degree between hour and minute hand

<?php
$time=array();
$time['h']=12;
$time['m']=15;
$time['s']=30;
function clockDegree($time){
	$mPercent=((float)$time['m']+((float)$time['s']/60.0))/60.0;
	$mDegree=$mPercent*360;
	$hdegree=((int)$time['h']%12+(float)$mPercent)/12.0*360;
	echo abs($mDegree-$hdegree);
}
clockDegree($time);

Permutation 1

A link to js fiddle http://jsfiddle.net/2v5fJ/

//this method is not very good, it requires some extra space
var input_arr = [1,2,3,4,5,6];
var exclude_index = [];
var prefix_arr = [];
function perm(arr, exclude_index, prefix_arr) {
    if(prefix_arr.length == arr.length) {
        ///got an end
        console.log(prefix_arr);
    } else {
        for(var i = 0; i < arr.length; i++) {
            //select i from arr and place it in the new array
            if(exclude_index.indexOf(i) != -1) {
                continue;
            }
            var new_exclude_index = exclude_index.slice(0);
            new_exclude_index.push(i);
            var new_prefix_arr = prefix_arr.slice(0);
            new_prefix_arr.push(arr[i]);
            perm(arr, new_exclude_index, new_prefix_arr) ;
        }
    }
}
perm(input_arr, exclude_index, prefix_arr);

Permutation 2

A link to js fiddle http://jsfiddle.net/2v5fJ/1/

var input_arr = [1,2,3];
function swap(arr, i, j) {
    if(i != j) {
        var tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }    
}
function perm(arr, index) {
    if(index == arr.length) {
        console.log(arr);
    } else {
        for(var i = index; i < arr.length; i++) {
            swap(arr, index, i);
            perm(arr, index + 1);
            swap(arr, index, i);
        }
    }
}
perm(input_arr, 0);