Known binary search tree and two values, find the number of nodes in the binary search tree, where the value of node is between two values

int foo(tree* node, int min, int max, int& count)
{
if(!root) return;
if(root->val>min && root->val < max)
{
count++;
foo(node->left,min,max,count);
foo(node->right,min,max,count);
}
else if(root->val>max) foo(node->left,min,max,count);
else if(root->val < min) foo(node->right,min,max,count);
}

Convert string to integer num, convert integer num to string

Convert string to integer num, convert integer num to string
1 A
2 B
…
27 AA
28 AB
int foo(char* str)
{
if(!str) return 0;
int num=0;
int len=strlen(str)-1;
int idx=len;
while(idx>=0)
{
num+=(str[idx]-'A'+1)*pow(26,len-idx);
idx--;
}
return num;
}
char* foo(int num)
{
if(num<=0) return NULL;
char* str=new char[11];
int idx=0;
while(num>=0)
{
str[idx]=num%26+'A'-1;
num/=26;
idx++;
}
str[idx]='\0';
return reverse(str);
}

Given a set of points (x,y) on a 2D coord system, identify list of 2D coords that are of distance less than x units long.

Given a set of points (x,y) on a 2D coord system, identify list of 2D coords that are of distance less than x units long.
Eg.
Let x = 1;
Given (0,0), (0,1), (1, 2), (4,6);
Return 1 -> (0,0), (0,1)
Build the kd tree, iteratively find the neighbors for the node where the distance is less than 1
http://en.wikipedia.org/wiki/Kd-tree#Nearest_neighbor_search
foo(tree* root, tree* node, stack s,int len)
{
if(!root) return;
if(DIS(root,node)<(-1*len))
foo(root->left,node,s,len);
else if(DIS(root,node)>len))
foo(root->right,node,s,len);
else
{ if(!root->left&&!root->right)//left node is the point node
{
s.push(root);
return;
}
foo(root->left,node,s,len);
foo(root->right,node,s,len);
}
}

There exits 2D array. We need to find out whether a given string ("microsoft") exits in the given matrix. The string can be vertical or horizontal or

There exits 2D array. We need to find out whether a given string ("microsoft") exits in the given matrix. The string can be vertical or horizontal or in snake form but not in diagonal.

mi..
...c.o..oft
.....r.s

the basic way is just scan the 2d array row by row (col by col ) and find the matching, we can use backtrack
{{{
int row;
int col;
int len;
char str[len]="microsoft";
char a[row][col]="…";
foo(int idx, int i,int j, char* str,const& char a[][col])
{
for(;i < row;i++,j=0)
for(;j < col;j++)
{
if(str[idx]==a[i][j])
{
if(idx==len-1) return true;
bool result=foo(idx+1,i,j+1,str,a);
if(result) return true;
}
}
return false;
}
}}}

Write a function that prints out all sets of consecutive integers that add up to all and any numbers within a given range. For example, given a range

Write a function that prints out all sets of consecutive integers that add
up to all and any numbers within a given range. For example, given a range of 4-9, your function must print out the fact that 5=2+3, 6=1+2+3, 7=3+4, 9=2+3+4, 9=4+5.
{{{
int min=4;
int max=9;
int idx1=1;//pointer 1 position
int idx2=2;//pointer 2 position
foo(int idx1, int idx2)
{
if(idx2>ceiling(max/2)||idx1>idx2)
return;
sum=sum_up(idx1…idx2);
if(sum foo(idx1,idx2++);
else if(sum>max)
foo(idx1++,idx2);
else //sum is between min and max
{
print(idx1...idx2);
foo(idx1++,idx2);
foo(idx1,idx2++);
}
}
}}}

Given a list A with n elements, produce a list B with n elements such that the ith element of B is equal to the product of all elements except the ith

Given a list A with n elements, produce a list B with n elements such that the ith element of B is equal to the product of all elements except the ith in list A. Example: Given list A = [1, 2, 3], make a function f(x) such that f(A) = [6, 3, 2].
foo(int* a,int len)
{
int prod=1;
int* b=new int[len];
for(int i=len-1;i>=0;i--)
{
b[i]=prod;
prod=prod*a[i];
}
prod=1;
for(int i=0;i < len;i++)
{
b[i]=b[i]*prod;
cout< < b[i]< < endl;
prod=prod*a[i];
}
}

Print all the paths in the tree

Print all the paths in the tree
foo(tree* root, int* arr, int idx)
{
if(!root) return;
arr[idx]=root->val;
if(!root->left&&!root->right){print arr; return;}//left node
foo(root->left,arr,idx+1);
foo(root->right,arr,idx+1);
}

In a linked list find the nth node from the end of the list

In a linked list find the nth node from the end of the list
list* foo(list* head, int n)
{
if(!head) return NULL;
list* p1=head;
list* p2=head;
int c=0;
while(p1->next)
{
p1=p1->next;
c++;
if(c>n)
return p2=p2->next;
}
if(c>n)
return p2;
else rturn NULL;
}

detect a cycle in linked list

detect a cycle in linked list
bool foo(list* head)
{
if(!head||!head->next) retrun false;
list* p1=head;
list* p2=head->next;
while(p1!=p2)
{
p1=p1->next;
if(p2->next)
p2=p2->next;
else
return false;

if(p1==p2) return true;

if(p2->next)
p2=p2->next;
else
return false;
}
return true;
}

Write the iterative version of post order traversal

Write the iterative version of post order traversal
From Wikipedia:
nonrecursivepostorder (rootNode)
nodeStack.push (rootNode)
while (true)
currNode = nodeStack.last ()
if ((currNode.left != null) and (currNode.left.visited == false))
nodeStack.push (currNode.left)
else
if ((currNode.right != null) and (currNode.right.visited == false))
nodeStack.push (currNode.right)
else
{
print currNode.value
currNode.visited := true
nodeStack.pop ()
}
if nodeStack.empty()
break

parenthesis matching onlu “(“ and ”)”

parenthesis matching on “(“ and ”)”
bool foo(char* a, int c, int idx)//initially, idx=0,c=0
{
if(strlen(a)==idx&&c==0) return true;
if(strlen(a)==idx&&c!=0) return false;
if(a[idx]==’(’) c++;
else if(a[idx]==’)’) c--;
if(c<0) return false;
return foo(a,c,idx+1);
}

bool foo(char* arr)
{
int p=0;
int c=0;
while(!arr[p])
{
if(c<0) return false;
if(arr[p]=='(') c++;
if(arr[p]==')') c--;
p++;
}
if(c==0) return true;
else trturn false;
}

Given two integers A & B. Determine how many bits required to convert A to B. Write a function

Given two integers A & B. Determine how many bits required to convert A to B. Write a function
int BitSwapReqd(int A, int B)
{
unsigned int count;
int diffnum = A ^ B;
for(count=0; diffnum; count++){
diffnum &= diffnum-1;
}
// here count is total no. of bit
return count;
}

Write an algorithm to print a binary tree level wise and that too from leaves to root. Use two counters to differ continues levels, put NULL in the st

Write an algorithm to print a binary tree level wise and that too from leaves to root.
Use two counters to differ continues levels, put NULL in the stack to differ two continues levels
bool foo(tree* root)
{
if(!root) return false;
queue q;
stack s;
q.push(root);
int c1=1;
int c2=0;
while(!q.empty())
{
tree* node=q.front();
q.pop();
s.push(node);
c1--;
if(c1==0) {node=NULL;s.push(node);}
if(node->right)
{
q.push(node->right);
c2++;
}
if(node->left)
{
q.push(node->left);
c2++;
}
if(c1==0) {c1=c2;c2=0;}
}
while(!s.empty())
{
tree* node=s.top();
s.pop();
if(node) cout< < node->val;
else cout< < endl;
}
return true;
}

Algorithm to find if a tree is symmetric?

Algorithm to find if a tree is symmetric?
(The tree is a generalized tree with as many child nodes as possible)
bool foo(tree* root1,tree* root2)
{
if(!root1&&!root2) return true;
if(!root1) return false;
if(!root2) return false;
if(root1->val!=root2_val) return false;
return foo(root1->left,root2->right)&&foo(root1->right,root2->left);
}

There is a binary expression tree. The leaves of the expression tree hold operands & nodes contain operator. How will you compute the value stored in

There is a binary expression tree. The leaves of the expression tree hold operands & nodes contain operator. How will you compute the value stored in the tree ?
int foo(tree* root)
{
if(!root)return 0;
if(!root->left&&!root->right) return root->val;
int left=foo(root->left);
int right=foo(root->right);
return calc(root->val,left,right);
}

In a general tree, how would you find the lowest common ancestor of two nodes that are given to you as parameters?

In a general tree, how would you find the lowest common ancestor of two nodes that are given to you as parameters?
tree* foo(tree* root, tree* n1, tree* n2)
{
if(!root) return NULL;

if(root==n1||root==n2) return root;

tree* left=foo(root->left);
tree* right=foo(root->right);
if(left&&right) return root;
return left?left:right;
}

Determine a bt is a bst

Determine a bt is a bst
bool foo(tree* root, int max, int min)
{
if(!root) return true;

if(root->valval>max)
return false;
return foo(root->left,root->val,min)&&foo(root->right,max,root->val);
}

Non recursion in-order

Non recursion in-order

void inorder(const Node* node) {
std::stack stack;
while (node != NULL || !stack.empty()) {
if (node == NULL) {
node = stack.top(); stack.pop();
process(node->value);
node = node->right;
}
if (node != NULL) {
stack.push(node);
node = node->left;
}
}
}

Find max consecutive sum in array

Find max consecutive sum in array
int foo(vector a)
{
int max=0;
int tmp_max=0;
for(int idx=0;idx < a.size();idx++)
{
tmp_max+=a[idx];
if(tmp_max<0)
tmp_max=0;
if(tmp_max>max)
max=tmp_max;
}
return max;
}

It is a game. There are 1...N persons. the count 'M' is given. The M-th person is out of the game. The recounting starts again from M+1 th person. Fin

It is a game. There are 1...N persons. the count 'M' is given. The M-th person is out of the game. The recounting starts again from M+1 th person. Finally only one is remaining. He is the winner. Implement the algo.
list* foo(list* head, int n)
{
int idx=1;
while(head->next!=head)
{
if(idx==n)
{
tmp=head;
head->prev->next=head->next;
head->next->prev=head->prev;
head=head->next;
free(tmp);
idx=1;
}
else
{
head=head->next;
idx++;
}
}
return head;
}