Algorithm Problems
From Hawk Wiki
Contents
- 1 Binary Tree
- 2 Print linklist inversed
- 3 Inverse Array
- 4 Find duplicate numbers in array
- 5 Interpolation search
- 6 Random Selector
- 7 N choose K in order
- 8 Max sub array
- 9 Sub sum NP problem
- 10 Swap 2 numbers in one line
- 11 Calculate degree between hour and minute hand
- 12 Permutation 1
- 13 Permutation 2
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);
