Loading...

Tuesday, December 29, 2009

Two Closest Points in plane


Set of points, the points closest to each other

Given a set of points in a x and y coordinates, find the pairs of points (x1, y1) (x2, y2) that are closest.

Algorithm will be used plane sweep and data structure will be 2-4 tree.
d - minimum distance between the so-far found closest points.
p is current point.
D is the ordered set of points present in strip.
  1. Remove the points further than d to the left of p from the ordered set D that is storing the points in the strip.
  2. Determine the point on the left of p that is closest to it
  3. If the distance between this point and p is less than d (the current minimum distance), then update the closest current pair and d.

Algorithm given http://www.cs.mcgill.ca/~cs251/ClosestPair/ClosestPairPS.html
2-4 tree link is http://www.cs.mcgill.ca/~cs251/ClosestPair/2-4trees.html.

Thursday, December 24, 2009

Permutations Sum(xi)

You have given "k" dice. How many way you can get a sum "S" and yes you have to throw all the dice. Write program for this.

Its same permutations program...but we have to try with all the six S(1,2,3,4,5,6)
possibilities for a dice. Exit condition will be
If all the dice run out.

SumP(dice,sum) = SumP(dice-1,sum-i)+i (from S).

All possiblities of balanced Parenthesis

print all balanced parenthesis of size "n".
[ex:- for 1: (), for 2: ()(), (()); like this]

Printing balance paranthesis, need dynamically updating your options.
Such as initially only openeing brace can be choosen and closing braces are not present.
You choose one opening brace and add into your result, this will decrease the number of opening
brace but increase the closing brace count by one.

In normal permuations program, we try with every element in set with every other element.
So, here are only two choices given one opening brance and closing brace with n numbers.
So, everytime we try to choose, we check for the opening brace count available and closing brance count available.

I am posting my program here,


#include
using namespace std;
static int permcnt;
void print( char out[], int cnt)
{
//Print all the index from 0 to cnt-1 of out
permcnt++;
}

void generate ( char in[], int i, int opara,int cpara)
{
int j;
if ( opara == 0 && cpara == 0)
{
print(in, i);
return;
}
for ( j = 0; j < 2;j++)
{
if ( j == 0 && opara != 0 )
{
in[i] = '{';
generate(in,i+1,opara-1,cpara+1);
}
else if ( j == 1 && cpara != 0 )
{
in[i] = '}';
generate(in,i+1,opara,cpara-1);
}
}
}
int main()
{
int num;
cout<<"Enter the size:";
cin>>num;
char *in = new char [num*2];
in[0] = '{';
generate(in,1,num-1,1);
//Print permcnt to know total permutations
return 0;
}

Smallest Snip of givem M words

Yor are given occurrences of 3 words (say, "bangalore", "hyderabad", "google") in a file.
bangalore: 100, 130, 157, ...
hyderabad: 80, 145, 180, ....
google: 60, 139, 197, ...
[Note: occurrences are given in sorted order.]
Now, you need to find the "smallest snip" containing all these three words.
[In this case: 130("hyderabad"), 139("google"), 145("bangalore") - 15 is snippet size].

Can you generalize this for m words and length of occurrences is n.


Algorithm:
Take first element from all list and put in a array.
minsnip = INT_MAX;
while any of list have element.
do
currentsnip = max in array - min in array;
if currentsnip < minsnip
minsnip = currentsnip;
delete the min element from array.
Get second element fron deleted list.
done

Permutation of N letters word with distance 1

Given a dictionary containing four letter words print out all the words which can be formed by changing only character from the word each time.

N closest Points in a plane

There are billions of points find the 10 points which are closest to the origin.

Tuesday, December 22, 2009

Two numbers with minimum difference

Find the two numbers whose difference is minimum among the set of numbers.

For example the sequence is 5, 13, 7, 0, 10, 20, 1, 15, 4, 19

The algorithm should return min diff = 20-19 = 1.

Make an efficient algorithm, yeah best could be O(n).

Not sure if i could use DP here, will post a solution tommorow. Let me know if you find a answer.

Algorithm:MiniMumDiffN
Get the size of array , say n.
Get the range of array, range.
Bucket Sort the above array.
Search the above sorted array for minimum difference.
This will be the minimum difference numbers.

Now question comes where the range of above given array is very big.
Algorithm:DivideArray
Take an random element.
Search for its position in array.
Return the index of element.

Algorithm:MiniMumDiff
if array_range > MAXRANGE
int mid = divideArray (arr,start,end);
d1,max1 = MiniMumDiff( arr,start,mid-1);
d2,max2 = MiniMumDIff(arr,mid+1,end);
d3 = difference max1 and arr[mid]
d4 = difference max2 and arr[mid]
return minimum( d1,d2,d3,d4)
else
return MiniMumDiffN(arr,start,end);


TC MiniMumDiffN - O(n)
TC DivideArray - O(n)
TC MiniMumDIff - O(log(range)n*2n)

And MiniMumDiff will be dividing range n in range 2 power (i) = n/range;
So MiniMumDiff will be if TC O(n)

Largest Square, rectangular

you are given a M x N matrix with 0's and 1's find the matrix-

1. find the largest square matrix with all elements 1's
2. Find the largest rectangular matrix with all elements 1's


Its simple DP problem guys ..just think of extending the solution to sub-problem.
Will post answer soon..till then give it a try.

Okie so recursive expression is
SQ(i,j) = MIN(SQ(i-1,j),SQ(i-1,j-1),SQ(i,j-1))*ARR(i,j)+ARR(i,j);

Idea is that SQ(i,j) will be a 1+ min of its precedents square size.


I am multiplying and adding to avoid if else condition
if ( ARR[i][j] == 1 )
SQ(i,j) = MIN(SQ(i-1,j),SQ(i-1,j-1),SQ(i,j-1))+1;
else
SQ(i,j) = 0;

is same as this SQ(i,j) = MIN(SQ(i-1,j),SQ(i-1,j-1),SQ(i,j-1))*ARR(i,j)+ARR(i,j);

Will post code soon.

Is Binary Tree?

Given a binary tree,write an algorithm to find if the tree is a binary search tree or not.

Simple Recursive call is good..

int check_tree(bst *node)
{
if(!node)
return TRUE;
if(node->left!=NULL && node->infoleft))
return(false);
if(node->right!=NULL && node->inforight))
return(false);
if(!check_tree(node->left) || !check_tree(node->right))
return(false);
return(true);
}

I have already posted better algorithm in my tree sections earlier.
Set Min and Max to INT_MIN and INT_MAX
bool IsBst( node *root, int min, int max)
{
if (!root) return true;
if ( !isBst( root->left,min,root->info) return false;
if ( !isBst(root->right,root->info,max) return false;
return true;
}

Binary Matrix

For a binary matrix of size n x m of 0's and 1's. eg
1 0 0 1
0 0 1 0
0 0 0 0

If a location has 1; make all the elements of that row and column = 1. eg
1 1 1 1
1 1 1 1
1 0 1 1

Solution should be with Time complexity = O(n*m) and space complexity = O(1)

Will post answer in comments. Try till then.

Sunday, December 20, 2009

Median of stream of numbers

Problem: Design a data structure which can perform most efficiently insert and median.


My Solution:
struct node
{
int number;
node *left;
node *right;
int leftTreeNode;
};

struct header
{
int totalNodes;
Int valid;
int median;
node *root;
} myhead ; //myhead ......thats where it will start.

void initialize() { valid = 0, median = 0, root =NULL, totalNodes =0; }
void AddNode ( int n )
{
myhead.totalNodes++;
myhead.valid = 0;
node *prev = NULL;
node *temp = myhead->root;
while ( temp != NULL )
{
if ( n <>number )
{
prev = temp;
temp->leftTreeNodes +=1;
temp = temp->left;
}
else
{
prev = temp;
temp = temp->right;
}
}
if ( prev != NULL )
{
if ( n <>number )
prev->left = createNode(n)
else
prev->right = createNode(n);
}
else
myhead->root = createNode(n);
}

int median ()
{
if (myhead.valid ) return median;
int mid = myhead.totalNodes/2;
node *prev = NULL;
node *temp = myhead.root;
while ( mid )
{
if ( mid > temp->leftTreeNodes )
{
mid = mid - (temp->leftTreeNodes)-1;//1 for root node
prev = temp;
temp = temp->right;
}
else
{
prev = temp;
temp = temp->left;
}
}
myhead.median = prev->number;
myhead.valid = 1;
return myhead.median;
}

Blood Relation

There are N persons in a country. N is very big in millions.
Design a efficient data structure and algorithm to find out whether there is blood relations between given two person or say they have a common ancestor .


My solution:
Used a map //UID by Nandan Nilekani :)
struct person
{
struct person *father;
struct person *mother;
list child; //However may not be needed for this problem
string name ...i.e. //Add more
}

struct person * findAncestor ( struct person *a, struct person *b)
{
Take first node in stack.
While ( stack is not null )
{
Mark Node.
Push Its ancestor in stack;
}

Take second node in stack.
while ( stack is not null )
{
If marked return Node,
push ancestor in stack.
}
return NULL;
}

It has a drawback, i need to clear the flagged node before i apply the search algorithm again.
But till now the best i know.

Maximum Gain Stock Market

Given an array which have samples of stock price at different timestamps.
You have to find best timings when we can buy and sell and make maximum benifit by it.
No need to say u can sell only after you buy.


Its simple DP problem, just need to form a equation

MaxGain(i) = Max(MaxGain(i-1), DIff(i,min))

Min is the index of element having min value till now. Diff will return the value(i)-value(min).

Hope its clear.

Finding frequency of numbers

Given an array of size n and value from 1-n. Find the number of times each value occured in array inplace. and O(n).

Easy one: Lets say array is a[].
size is N
while ( i < n)
a[a[i]%N] += N

Google Minimum Distance Pipeline

In a city there are n number of gas stations. A gas pipleline from government has to pass right
through (vertically only) the city. You have to create an algorithm which tells you the best place
the pipe line should pass and cost to government is minimum. Cost is always propotional to the distance
from gas station to pipeline.

Silly me, it took so much time to answer this one.

Okie i am posting my answer....

Sort the points for X axis...take a median of them. That will be the line x=c.

Lets say there are n points.
case 1: n is odd. So there will be a single point for median. say i.
Distance between a point from pipeline is abs(x1-xi).
As there are odd points so except the median, all the points will form a pair.
Between a pair of points if we move the pipeline between them, effective
distance from pipeline will remain constant.
So if median of x-axis value our pipeline is passing then effective distance
will be same till for all the pair of points on its two different sides.

P1 . P2
P1 . P2
P1 . P2

See for the above case total distance will be same pipeline passing between them
As we took median so for all the points that will make it constanst distance and minimum too.

Case 2: if n is even.
SO we can take any point in between the two median points and distance will be still same. Above appiles here again and make it minimum distance.

Sunday, December 13, 2009

Car Parking Problem

There is n parking slots and n-1 car already parked.
Lets say car parked with initial arrangement and we want to make the car to be parked
to some other arrangement.

Lets say n = 5, inital = free, 3, 4, 1, 2
desired = 1, free, 2, 4 ,3

Give an algorithm with minimum steps needed to get desired arrangement.
Told by one of my friend and after a lot of search i really got a nice solution.
I will post solution in comment part

Visit this nice blog

A great site for math and physics puzzles

http://www.blogcatalog.com/blog/physically-incorrect/f5ae796cc31d8af0b3ea6df7945e569b

Puzzle

what next?
1
11
21
1211
111221

See pronunciation? You will get the answer.

Saturday, December 12, 2009

Median of Five Numbers

U have 5 NOs , X1,X2,X3,X4,X5

With minimum no. of comparisons we have to find a median.

SWAP(X,Y) function is available to u .

I have a answer of six comparisons and eight swaps....wait for people to find out by themselves.

Wednesday, December 9, 2009

Google Questions (Plenty coming )

Given n distinct points prove that for all k,0
divide points into n-k and k points by drawing a line segment....



Proof given on a site
There are n points, so max n(n-1)/2 different directions of the line segments joining two points among these n points.

Now draw any line which has direction different than above at most n(n-1)/2 values.
By choosing a different direction you are making sure that no two points can lie on the line.

Now you can 'drag' the line as much as you want and get as many points on it's one of the sides as you want.

Wednesday, November 25, 2009

Multiple Template definion with C++

file.h
template

void tfunc( T a)
{
.........
}

file1.cpp
#include"file.h"
void myfunc1()
{
tfunc(123);
}
file2.cpp
#include"file.h"
void myfunc2()
{
tfunc(456);
}

main.cpp
extern void myfunc1();
extern void myfunc2();

int main()
{
myfunc1();
myfunc2();
return 0;
}


Compile with:
g++ -o main.exe file1.cpp file2.cpp main.cpp


Before you compile, just try answering below questions:
1. Will this compile?
If Yes then Why and how?

If no then you are on right track. Same thing happens with normal function definition. But hold on, c++ template handles this multiple definition problem very smoothly. It means above files will compile and execute properly.
Thats special handling with multiple template instantiation done by linker.

Now you know that this answer of above questions is yes, so you may want to know how and why?
Will post in next post. This question was asked to my friend in NetApp.

Thursday, November 12, 2009

DEShaw Interview Questions

ther are N numbers frm 1 to N and starting from index 1 we will keep deleting every alternate going in cyclic order with array. Only one element will be left at the end.
Tell us the index of element in array we started.

e.g.
there are 5 nums
1 2 3 4 5
then after 1st iteration 1 3 5 will be remained.
.. then 1 will be next to be elliminated and then 5
3 will remain alone...

give sum efficient algorithm to calculate which numer will remain at the end

Answer: 2*(n-2^p)+1
where p=floor(log2 n)

Wednesday, November 11, 2009

Wednesday, June 3, 2009

Debugging multithreaded programs

Q: In a Multi Threaded System .... how to know which thread lead to Core-Dump?

Answer: Do these steps ..

1. gdb -c core.
2. info threads
See which one has called kill procedure.
3. thread


I got these information from here:
http://wiki.davincidsp.com/index.php?title=Multithreaded_Debugging_Made_Easier_by_Forcing_Core_Dumps

Sunday, May 24, 2009

Answer for link list

9. Find whether a list is even or odd.
a) Keep counting.
b) Use a bool for flag
c) Without any variable
int isOdd ( struct node *head )
{
Head = head->next;
While ( head)
{
If ( head->next == NULL )
Return 1;
Head = head->next->next;
}
}
10. Reverse a link list with/without recursion.
Void reverselist( struct node *head )
{
Struct node *prev, *current, *temp;
Prev = NULL;
Current = head->next;
While ( current )
{
Temp = current->next;
Current->next = prev;
Prev = current;
Current = temp;
}
Head->next = prev;
}

11. Shuffle two link list of same size. If p and q are head pointers.
Struct node *newhead = p;
While (q )
{
Swap(&p->next, &q);
P = p->next;
}
12. Merge two sorted link list.
13. Find whether two list are intersecting or not.
a) Use negation technique. Traverse list 1 and negate elements. Traverse list 2 and return first negated element.
b) Hashtable: insert node in hashtable. If found collision return element.
c) Length of list 1 = m length of list 2 = n. Traverse |m-n| element and then start comparing.
14. Detect a loop in link list.
a) Maintain a flag for each node visited. If you see any node already visited then a loop.
b) use hashtable for nodes.
c) Take two pointers. Increment first by one and another by two.
Note: Application kernel programming and random number generator.

15. Remove loop from link list.
Use the loop detection approach and as soon as you know node->next is repeated, make it null.
16. Find the length of loop.
Use any of the above three approach and keep a counter until a node repeated.
17. Find the kth element from end.
a) Bruteforce: count the list nodes once and go for the (n-k) node next time.
b) Maintain two pointer, both pointing to I and i-k node. So when pointer 1 point at n second one will point to n-k.

Answer for doubly link list

18. Reverse the doubly link list.
For ( p = head; p->next != head; p = p->prev )
Swap (&p->next,&p->prev);

19. Doubly link list a single pointer.
While storing the address store address as xor of the previous and next.

20. Reverse the link list with ‘k’ nodes.
Take the k+1 the element pointer and put as the next for first element . Reverse the K sized list .
21. Find a list in palindrome or not.
a) Find the middle node, reverse link list after that. Start comparing from head and the node after the middle node.

Answer for Stack Q

22. No of permutations with n numbers. (1/(n+1)2ncn).
a) No of permutations are 1/(n+1) (2n)cn.
b) No of stack permutation possible.
c) No of binary trees possible with n nodes.
d) No of ways to parenthesise with n data element.

23. A string with a’s and b’s and with one special character ‘x’. Find out whether its palindrome or not.
a) Take two pointer one from start and another from end. Start comparing till pointers don’t cross each other.

24. Implement queue by stack with enque and deque of order O(1);
Pop all the element and push in second stack2. The top2 will point to the beginning of
Deque and top1 will be at end. Maintain size1 and size2 for the bottom removing with both the cases.
Add at beg: push in stack2, size1 and size2 incremented.
Add at end: push in stack1, size1 and size2 incremented.
Delete at beg: pop in stack2 and decrement size1 and size2.
Delete at end: pop in stack2 and decrement size1 and size2.

25. Convert infix expression to postfix.
While ( ch )
{
If ( ch is alphanumeric ) push (ch);
If ( ch is ‘)’ ) pop from operatorstack and push(ch);
If ( ch is operator) pushoperator(ch);
}

Answers for MISC questions

39. Find first non repeating character in a string.
a) Bruteforce: TC: o(n2) SC: o(1)
b) use another array or use hashtable

40. Find whether two arrays of same size have same values.
Go through first array, hash every element and increment the count if repeated.
Go through second and decrement count for every element and at the lost every index should be having zero.

41. Given a minheap find the max element.
Sol) max element will always be at leaf, take the last element in heap and find its parent which will be always the last non leaf node. Find the max element after the last non leaf node and last node.

42. Convert an array to heap.
a) Sort the array and sorted array is always min heap.
b) Add the first element in heap and then second. Now particulate for heap property. Keep adding element and managing heap property.
c) Bottom up heap building ( I really did not understand this concept. Please google).
43. Kth element in a Min heap.
a) Bruteforce: Call delete min () k times. TC (nlog n);
b) Can there could be a better approach? I am sure there will be, if you know please post.

44. implement a stack using heap.
Stack : push, pop and top
Heap: insert, delete and Findmin.
a) Maintain extra index key in the heap.
Push ( O(log n)), pop (O (long n) ) top (O(1))
45. Implement queue using heap.
Use the same approach as stack, use the negative index for stack and positive for queue.

46. Find union of k sorted list.
a) Create the min heap from the first elements of all arrays.
Delete the first element and put the deleted element in a new array.
Insert a new element from the deleted array. Maintain separate index for every array, so that we can figure out which array to take next element.
b) Use divide and conquer, merge sort.
c) Bruteforce: merging first two array and then resulting array with next one.
47. Merge the two heap.
a) take element from one heap and insert in second heap. O(min(m log m+n, n log m+n)).
b) Append first array to second and then convert array to heap. O(m+n).

48. Fibonocci with memorization/ Dynamic programming.
Int f ( int n)
{
If ( n<= 1) return n;
If ( fib[n] != -1 ) return fib[n];
Fib[n] = f ( n-1) + f (n-2);
Return fib[n];
}

49. Find no of BST can be formed with n nodes.
BST(n) = 1 if n == 0
= 1 if n == 1
= i=1 to n BST(i-1) * BST(n-i) for n >2
Int BST(int n)
{
Int count = 0;
If ( n <= 1 ) return 1;
For ( I =1;i<= n;i++)
Count += BST(i-1)*BST(n-i);
Return count;
}
Not optimized, use memozation technique.
50. Find no of legal path between x and y which does not include ‘+’
A
- + - - +
- - - - -
+ - + + -
- - - - -
B

For ( int I =0; i<= m ;i++) p[i][0] =0;
For ( int j = 0; j <= n; j++) p[0][j] = 0;
For ( I = 1; i<= m;i++ )
{
For ( j = 1;j<=n ;j++ )
{
If ( a[i][j] == ‘.’ ) p[i][j] = p[i-1][j]+p[i][j-1];
Else p[i][j] = 0;
}
}
Return p[m][n];

51. Find the largest common subsequence between two given strings.
LCS(I,j) = max (LCS(I,j-1), LCS(i-1,j)) if s1[i] != s2[j].
LCS(I,j) = 1+ LCS(I-1,j-1) if s1[i] == s2[j].
LCS(I,j) = 0 if i==0 or j == 0.

52. Find the shortest common super sequence.
SCS(I,j) = 1+ min (LCS(I,j-1), LCS(i-1,j)) if s1[i] != s2[j].
SCS(I,j) = 1+ SCS(I-1,j-1) if s1[i] == s2[j].
SCS(I,j) = max(I,j) if i==0 or j == 0.

53. In a string, find the longest substring which is palindrome.
a) Reverse the first string and find the longest common substring.
b)
54. Find the maximum sum subarray without selecting two consecutive number.
S[i] = max (a[0], a[1]) if I == 1
S[i] = max (a[i]+s[i-2], s[i-1]) if I > 1
Int maximalsum ( int a[], int n)
{
S[0] = a[0];
S[1] = max (a[0],a[1])’;
For ( i= 2; i< n; i++)
S[i] = max(s[i-1],s[i-2]+a[i]);
Return s[n-1];
}

55. optimal matrix chain multiplication.
M[I,j] = 0 if i==j
M[I,j] = min ( m(I,k)+m(k+1,i)+ri*ck*cj) if I <= k < j.

56. Generate binary sequence of constant ‘N’.
Void binary ( int a[], int n)
{
If ( n == 2 )print(a), return;
a[i] =0;
binary(a,n+1);
a[i] =1;
binary(a,n+1);
return;
}
57. Given an array generate all the possibilities of array.
Void generate( int in[], int out[], int I, int n)
{
Int j;
If ( I == n ) print(out), return;
For ( j = 0; j < n; j++)
{
Out[i] = in[j];
Generate(in,out,i+1,n);
}
}

58. Given an array generate the permutation of array.
Void permute( int in[], int out[],int used, int I, int n)
{
Int j;
If ( I == n ) print(out), return;
For ( j = 0; j < n; j++)
{
If ( used[j] ) continue;
Used[j] = true;
Out[i] = in[j];
permute(in, out, used, i+1,n);
used[j] = false;
}
}

59. Given an array generate the combination of array.
Void combination ( int in[], int out[], int n, int k, int I, int start )
{
If ( I == k ) printf(out,k),return;
For ( j = start; j < n-k+start;j++ )
{
Out[i] = in[j];
Combination(in,out,n,k,i+1,j+1);
}
}
60. Find distinct partitions of a number i.e. for 3(1,1,1)(1,2)

61. In a matrix find the largest square with all 1’s
0 0 0 0 1
0 1 1 0 1
0 0 1 0 1
1 1 0 0 1
0 1 1 1 0
A[I,j] = 0 if I == 0 or j == 0
A[I,j] = 0 if c[i][j] == 0
A[I,j] = min(A[i-1][j],A[i-1][j-1], A[i][j-1]+1)

Answers for Binary Tree Questions

26. Find height of a tree with or without recursion.
Int FindHeight ( struct node *root)
{
If ( !root) return 0;
Return ( 1+max (findHeight(root->left),findheight(root->right)));
}

Note: For a tree height and depth is same, but for an individual node its same. Root’s height is 1 while depth is 0.
Reader: Can any one post the algorithm for finding tree height without recursion.

27. Find the levels in tree and no of node at every level.
Use BFS.
Void levelorder( struct binarynode * root)
{
Enque(root);
While ( !emptyQ())
{
Temp = deque(q);
// Process node
If ( temp->left) enque(q,temp->left);
If ( temp->right) enque(q,temp->right);
}
}
Use the BFS and put the NULL after every deque give you a null.

28. No of leaves on tree.
Int countleaves( struct binarynode * root)
{
If ( !root) return 0;
If ( !root->left && !root->right) return 1;
Return ( countleaves(root->left) + countleaves(root->right));
}
Can anyone write the algorithm without recursion.

29. Find the diameter of tree. Longest distance between two same level nodes.
Need state management, can be solved by:
Static : multithreading problem
Global: data hiding problem
Pass as argument or use functor.
Int treeDiameter ( struct binarynode *root, int *pd)
{
Int left, right;
If ( !root) return 0;
Left = treeDiameter(root->left,pd);
right = treeDiameter(root->right,pd);
if ( left + right > *pd) * pd = left+right;
return max (left, right) +1;
}

30. Write pre/in/post order traversal with and without recursion.
Void preorder ( struct binarynode * root )
{
If ( root)
{
Processnode(root); //1
Preorder(root->left);//2
Preorder(root->right);//3
}
}
For preorder (1->2->3), inorder(2->1->3) and postorder ( 2->3->1).

31. Serialization of binary tree. Storing data/object in a file and then retrieving it back.
Sol: Store inorder and preorder traversal in file and retrieve the same and you can always build tree from preorder and inorder.
Int I = 0; int l =0; int r = n-1;
Struct binarynode *temp = new struct binarynode ();

Struct binarynode * buildtree( int in[], int pre[], int l, int r)
{
If ( l > r) return null;
Temp->element = pre[l];
Int p = search (in,l,r,pre[l++]);
Temp->left = buildtree(in,pre,l,p-1);
Temp->right = buildtree(in,pre,p+1,r);
Return temp;
}

32. Find the least common ancestor for any two given nodes from tree.
a) Get an inorder and preorder traversal. Find all element between two given nodes, and search for the first element in preorder
b) Struct binarynode * LCA ( struct binarynode *root, struct binarynode *p, struct binarynode * q)
{
If ( !root) return 0;
If ( root == p || root == q ) return root;
Left = LCA(root->left, p,q);
Right = LCA( root->right,p,q);
If ( left && right ) return root;
Else return( left?left”right);
}

33. Threaded binary tree and link inversion tree.

34. Find whether a given tree is BST or not.
a) Do a inorder traversal, and if elements are sorted then its binary tree.
b) int IsBST( struct BSTnode *root, int min, int max )
{
If ( !root) return 1;
Return ( root->element >min && root->element IsBST(root->left, min,root->element) &&
IsBST(root->right,root->element, max));
}

35. Write code for inorder successor. Link to parent node is available.
Struct BSTnode * inordersuccessor ( struct BSTnode *p )
{
If ( !p->right )
{
If ( p->parent->left == p ) return p->parent;
While ( p->parent->right == p ) p = p->parent;
Return p->parent;
}
Else
{
P = p->parent;
While ( p ->left)
P = p->left;
Return p;
}
}


36. Find the kth smallest element of BST.
a) Int count = 0;
Struct BSTnode *kthsmallest ( struct BSTNode *root, int k )
{
If ( !root) return NULL;
Left = kthSmallest ( root->left, k);
If ( left != NULL ) return left;
If ( ++count == K ) return root;
Return kthsmallest(root->right, k );
}
b) Without global variable : pass as an argument.
c) With augmented binary tree, store size of binary subtree with each node.

37. Convert BST to doubly link list.
Struct node * append ( struct node *first, struct node *last )
{
If ( first == NULL )
{
Last->left = last->right = last;
Return last;
}
Last->right = first;
Last->left = first->left;
First->left->right = last;
First->left = last;
Return first;
}
Void BSTtoDLL ( struct node *root, BSTnode *prev )
{
BSTnode *tmp;
If ( !root ) return;
BSTtoDLL( root->left,prev);
Temp = root->right;
*prev = append (*prev,root);
BSTtoDLL(tmp,prev);
}
Without prev variable
Struct node * BSTtoDLL( BSTNode * root )
{
If ( !root) return NULL;
Left = BSTtoDLL(root->left);
Right = BSTtoDLL(root->right);
Return append(left, right, root );
}

38. Is the given BST is AVL or not?
Int isbalance ( struct BSTnode *root )
{
Int left, right;
If ( !root ) return 0;
Left = isbalanced(root->left);
If ( left == -1 ) return -1;
Right = isbalanced(root->right);
If ( right == -1 ) return -1;
Return ( max(left,right)+1);
}

Sunday, May 3, 2009

Trie

62. Find largest word in dictionary.
63. display all word in dictionary with starting char “ab”.
64. Find a element in an array with indefinite length.
65. Find the size of indefinite length array. Note all elements are initialized with @.
66. Find which rows is having maximum zeroes.
1 1 1 1 0
1 0 0 0 0
1 1 0 0 0
1 0 0 0 0

Once a rows got a zero there wont be any more 1’s.

67. In a matrix where each row and each column is sorted, find a number in o(1).
68. Find a element in bitonic array. Bitonic array first increase and decrese or vice versa.
69. Find a element in a rotated sorted array.
70. Find whether X is majority element in an array.

Misc

39. Find first non repeating character in a string.
40. Find whether two arrays of same size have same values.
41. Given a minheap find the max element.
42. Convert an array to heap.
43. Kth element in a Min heap.
44. implement a stack using heap.
45. Implement queue using heap.
46. Find union of k sorted list.
47. Merge the two heap.
48. Fibonocci with memorization/ Dynamic programming.
49. Find no of BST can be formed with n nodes.
50. Find no of legeal path between x and y which does not include ‘+’
A
- + - - +
- - - - -
+ - + + -
- - - - -
B

51. Find the largest common subsequence between two given strings.
52. Find the shortest common super sequence.
53. In a string, find the longest substring which is palindrome.
54. Find the maximum sum subarray without selecting two consecutive number.
55. optimal matrix chain multiplication.
56. Generate binary sequence of constant ‘N’.
57. Given an array generate all the possibilities of array.
58. Given an array generate the permutation of array.
59. Given an array generate the combination of array.
60. Find distinct partitions of a number i.e. for 3(1,1,1)(1,2)
61. In a matrix find the largest square with all 1’s
0 0 0 0 1
0 1 1 0 1
0 0 1 0 1
1 1 0 0 1
0 1 1 1 0

Binary Tree

26. Find height of a tree with or without recursion.
27. Find the levels in tree and no of node at every level.
28. No of leaves on tree.
29. Find the diameter of tree. Longest distance between two same level nodes.
30. Write pre/in/post order traversal with and without recursion.
31. Serialization of binary tree. Storing data/object in a file and then retrieving it back.
32. Find the least common ancestor for any two given nodes from tree.
33. Threaded binary tree and link inversion tree.
34. Find whether a given tree is BST or not.
35. Write code for inorder successor.
36. Find the kth smallest element of BST.
37. Convert BST to doubly link list.
38. Is the given BST is AVL or not?

Binary Tree

26. Find height of a tree with or without recursion.
27. Find the levels in tree and no of node at every level.
28. No of leaves on tree.
29. Find the diameter of tree. Longest distance between two same level nodes.
30. Write pre/in/post order traversal with and without recursion.
31. Serialization of binary tree. Storing data/object in a file and then retrieving it back.
32. Find the least common ancestor for any two given nodes from tree.
33. Threaded binary tree and link inversion tree.
34. Find whether a given tree is BST or not.
35. Write code for inorder successor.
36. Find the kth smallest element of BST.
37. Convert BST to doubly link list.
38. Is the given BST is AVL or not?

Stack

22. No of permutations with n numbers. (1/(n+1)2ncn).
23. A string with a’s and b’s and with one special character ‘x’. Find out whether its palindrome or not.
24. Implement queue by stack with enque and deque of order O(1);
25. Convert infix expression to postfix.

Doubly Link List

18. Reverse the doubly link list.
19. Doubly link list a single pointer.
20. Reverse the link list with ‘k’ nodes.
21. Find a list in palindrome or not.

Link List

9. Find whether a list is even or odd.
10. Reverse a link list with/without recursion.
11. Shuffle two link list of same size.
12. Merge two sorted link list.
13. Find whether two list are intersecting or not.
14. Detect a loop in link list.
15. Remove loop from link list.
16. Find the length of loop.
17. Find the kth element from end.

Array

1. Given a arrary return an element not in array.
2. Previous problem with number will be in range of 0- (n-1).
3. Find the number repeating most number of times in a n size array with no in the range of 0-(n-1).
4. Find whether a[i]+a[j]=x in a sorted and unsorted array.
5. Maximum of two number without if statement.
6. Print 1-100 without loop, if, goto etc.
7. Find the only non-repeating number in a array.
8. Find the two number which is non-repeating in a array

I am posting questions here only. I will shortly update with answer to them.
Till then keep trying.