Difference between revisions of "Algorithm Problems"

From Hawk Wiki
Jump to: navigation, search
(Sub sum NP problem)
(Find duplicate numbers in array)
 
(13 intermediate revisions by the same user not shown)
Line 4: Line 4:
  
 
==Print linklist inversed==
 
==Print linklist inversed==
<pre>
+
<pre class="brush:c">
 
///////////////////////////////////////////////////////////////////////
 
///////////////////////////////////////////////////////////////////////
 
// Print a list from end to beginning
 
// Print a list from end to beginning
Line 24: Line 24:
 
}
 
}
 
</pre>
 
</pre>
 +
 
==Inverse Array==
 
==Inverse Array==
<pre>
+
<pre class="brush:c">
for (int i = 0; i < b; i=i++){
+
for (int i = 0; i < b/2; i=i++){
 
char temp1 = a[i];
 
char temp1 = a[i];
 
a[i] = a[(b-1)-i];
 
a[i] = a[(b-1)-i];
Line 33: Line 34:
 
}
 
}
 
</pre>
 
</pre>
 +
 
==Find duplicate numbers in array==
 
==Find duplicate numbers in array==
<pre>
+
<pre class="brush:php">
 
<?php
 
<?php
 
/*  
 
/*  
Line 52: Line 54:
 
?>
 
?>
 
</pre>
 
</pre>
 +
Extention read
 +
http://www.geeksforgeeks.org/find-duplicates-in-on-time-and-constant-extra-space/
 +
 
==Interpolation search==
 
==Interpolation search==
<pre>
+
<pre class="brush:c">
 
  public int interpolationSearch(int[] sortedArray, int toFind){
 
  public int interpolationSearch(int[] sortedArray, int toFind){
 
   // Returns index of toFind in sortedArray, or -1 if not found
 
   // Returns index of toFind in sortedArray, or -1 if not found
Line 80: Line 85:
 
  }
 
  }
 
</pre>
 
</pre>
 +
 
==Random Selector==
 
==Random Selector==
 
Select k smallest value in array. O(n)
 
Select k smallest value in array. O(n)
<pre>
+
<pre class="brush:php">
 
<?php
 
<?php
 
function swap(&$a,&$b){
 
function swap(&$a,&$b){
Line 122: Line 128:
 
echo 'final result:'.select($Arr, 0, sizeof($Arr)-1,10);
 
echo 'final result:'.select($Arr, 0, sizeof($Arr)-1,10);
 
</pre>
 
</pre>
 +
 
==N choose K in order==
 
==N choose K in order==
<pre>
+
<pre class="brush:php">
 
<?php
 
<?php
 
$n=6;
 
$n=6;
Line 164: Line 171:
 
echo select($list,$k);
 
echo select($list,$k);
 
</pre>
 
</pre>
 +
 
==Max sub array==
 
==Max sub array==
 
Kadane's algorithm<br>
 
Kadane's algorithm<br>
Line 180: Line 188:
 
input : {1,2,4,5,6,1,2,4,3,5,7,2,1}<br>
 
input : {1,2,4,5,6,1,2,4,3,5,7,2,1}<br>
 
output : {1,1,2}, {2,2}, {3,1}, {1,2,1}<br>
 
output : {1,1,2}, {2,2}, {3,1}, {1,2,1}<br>
<pre>
+
<pre class="brush:php">
 
<?php
 
<?php
 
//Sub sum problem NP
 
//Sub sum problem NP
Line 201: Line 209:
 
//keep $a
 
//keep $a
 
$head1=$head.$a." ";
 
$head1=$head.$a." ";
unset($arr[$i]);
+
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 />";
 
//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);
 
subsum($arr,$sum-$a,$head1);
Line 220: Line 228:
 
*/
 
*/
 
</pre>
 
</pre>
 +
 
==Swap 2 numbers in one line==
 
==Swap 2 numbers in one line==
<pre class="php">
+
<pre class="brush:php">
 
//swap
 
//swap
 
$a=10;
 
$a=10;
Line 234: Line 243:
  
 
==Calculate degree between hour and minute hand==
 
==Calculate degree between hour and minute hand==
<pre class="php">
+
<pre class="brush:php">
 
<?php
 
<?php
 
$time=array();
 
$time=array();
Line 247: Line 256:
 
}
 
}
 
clockDegree($time);
 
clockDegree($time);
 +
</pre>
 +
==Permutation 1==
 +
A link to js fiddle http://jsfiddle.net/2v5fJ/
 +
<pre class="brush:javascript">
 +
//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);
 +
</pre>
 +
 +
==Permutation 2==
 +
A link to js fiddle http://jsfiddle.net/2v5fJ/1/
 +
<pre class="brush:javascript">
 +
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);
 
</pre>
 
</pre>

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);