Difference between revisions of "Algorithm Problems"

From Hawk Wiki
Jump to: navigation, search
(Created page with "==Binary search== <pre> def search_binary_tree(node, key): if node is None: return None # key not found if key < node.key: return search_binary_tree(...")
 
(→‎Find duplicate numbers in array)
 
(35 intermediate revisions by the same user not shown)
Line 1: Line 1:
−
==Binary search==
+
==Binary Tree==
−
<pre>
+
[[All about Binary search tree]]<br>
−
def search_binary_tree(node, key):
+
[[All about Linked List]]<br>
−
    if node is None:
+
 
−
        return None  # key not found
+
==Print linklist inversed==
−
    if key < node.key:
+
<pre class="brush:c">
−
        return search_binary_tree(node.leftChild, key)
+
///////////////////////////////////////////////////////////////////////
−
    elif key > node.key:
+
// Print a list from end to beginning
−
        return search_binary_tree(node.rightChild, key)
+
// Input: pListHead - the head of list
−
    else:  # key is equal to node key
+
///////////////////////////////////////////////////////////////////////
−
        return node.value  # found key
+
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);
 +
      }
 +
}
 
</pre>
 
</pre>
−
==Binary tree insert==
+
 
−
<pre>
+
==Inverse Array==
−
/* Inserts the node pointed to by "newNode" into the subtree rooted at "treeNode" */
+
<pre class="brush:c">
−
void InsertNode(Node* &treeNode, Node *newNode)
+
for (int i = 0; i < b/2; i=i++){
−
  {
+
char temp1 = a[i];
−
    if (treeNode == NULL)
+
a[i] = a[(b-1)-i];
−
      treeNode = newNode;
+
a[(b-1)-i] = temp1;
−
    else if (newNode->key < treeNode->key)
+
cout << a[i] ;
−
      InsertNode(treeNode->left, newNode);
+
}
−
    else
+
</pre>
−
      InsertNode(treeNode->right, newNode);
+
 
 +
==Find duplicate numbers in array==
 +
<pre class="brush:php">
 +
<?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);
 +
?>
 +
</pre>
 +
Extention read
 +
http://www.geeksforgeeks.org/find-duplicates-in-on-time-and-constant-extra-space/
 +
 
 +
==Interpolation search==
 +
<pre class="brush:c">
 +
  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
 
  }
 
  }
 +
</pre>
 +
 +
==Random Selector==
 +
Select k smallest value in array. O(n)
 +
<pre class="brush:php">
 +
<?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);
 +
</pre>
 +
 +
==N choose K in order==
 +
<pre class="brush:php">
 +
<?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);
 +
</pre>
 +
 +
==Max sub array==
 +
Kadane's algorithm<br>
 +
 +
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:<br>
 +
<pre>
 +
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
 +
</pre>
 +
==Sub sum NP problem==
 +
Find a sub array which sum equals to 4. <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>
 +
<pre class="brush:php">
 +
<?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
 +
*/
 +
</pre>
 +
 +
==Swap 2 numbers in one line==
 +
<pre class="brush:php">
 +
//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
 +
</pre>
 +
 +
==Calculate degree between hour and minute hand==
 +
<pre class="brush:php">
 +
<?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);
 +
</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);
Retrieved from "http://wiki.hawkguide.com/index.php?title=Algorithm_Problems&oldid=310"