Doctor.Sai
BAN USER- 0of 0 votes
AnswersYou are given a binary Tree B and pattern p = LLRLR. Let S = ppppp… be a sequence generated from the given pattern p. If ‘L’ denotes left traversal to node from its parent node and ‘R’ denote right traversal to node from its parent node find in B the largest of all such sequences.
- Doctor.Sai in India
Note: Only the Head will have neither 'L' or 'R'
An easy way is to record a path till you reach a NULL node and search for S in the recorded path, but that would be an O(n^2) algorithm, you are expected to give an O(n) algorithm where n denotes the number of nodes in B
Your algorithm should cater to all possible patterns.| Report Duplicate | Flag | PURGE
Amazon Algorithm - 0of 0 votes
AnswersFind the longest Zig-Zag path in a Binary TREE
- Doctor.Sai in India| Report Duplicate | Flag | PURGE
Amazon Algorithm - 0of 0 votes
AnswersGiven a set of n symbols a size k and a combination of length k of non repeating characters from the symbol set write only an ITERATIVE algorithm to print the next unique combination.
- Doctor.Sai in India
Ex: Symbols =[1,2,3,4,5]
size = 3;
given combination = 123, result = 124
given combination = 254, result = 312.| Report Duplicate | Flag | PURGE
Amazon Algorithm - 0of 0 votes
AnswersTwisted linked list problem: Two linked lists merge at some node p,both the head pointers are given find the merging point under
- Doctor.Sai in India
the following restrictions.
1. You should not traverse to the end any of the linked list.
2. Merge node p should be detected by the time you reach at most most k nodes from p.
3. Space should not exceed by k units.
4. No saving of nodes to hard discs.
5. No recursion.| Report Duplicate | Flag | PURGE
Algorithm - 0of 0 votes
AnswersGiven a set of n symbols and a size k write only an ITERATIVE algorithm to print all possible permutations of the given symbols with respect to the size given.
- Doctor.Sai in India
For example: Given symbols ={'A','B', 'C'} and
size = 2;
Solution is {AA,AB,AC,BA,BB,BC,CA,CB,CC} and count = 9.
Do not give recursive algorithm here| Report Duplicate | Flag | PURGE
Algorithm
Let us take a = 976 and b = 13.
Find the first k so that 13^k >=9 76. Equality we are done.
Here k = 3. We have 13^3 = 2197.
13^3 = 13(169).
Note: All division by 2 can done by >> 1.
(1 +169)/2 = 85. So have the following sequence.
13*1, 976, 13*85 = 1105
Find (1+85)/2 = 43 ,
So we have 13*43= 559, 976,13*85=1105.
Find (43+85)/2 = 64 , and 13*64 = 832.
So we have 13*64 = 832, 976, 13*85=1105.
Find (64+85)/2 = 74 and 13*74 = 962.
So we have 13*74=962, 976, 13*85=1105.
(74+85)/2 = 80 = 1040,
So we have 13*74=963,976,13*80=1040
(74+80)/2 = 77 , and 13*77 = 1001.
So we have 13*74=963, 976,13*77=1001
(74+77)/2 = 75, and 13*75 = 975,
So we have 13*75=975, 936,13*77=1001
Since 75 +2 == 77 check 13*76 = 988 and stop.
13*75<976<13*76. 75 is quotient
Solution :
Let S be the symbol array in the increasing order
Let C be the given combination.
For each digit di starting from the left most in C and ask this question:
1. Is there a symbol x in S such that x > di and x does not occur in C for all j<I?
2. If so we are done place the right symbol, get out of this loop and call a function RestIt(…).
3. If not we move to i-1 digit in C and go back to step 1.
4. If we end up consuming C in the process then declare "cannot find number bigger than C".
In RestIt(…) we have the following situation an index j in C is filled (by step 1 and 2) by an x from S.
5. Inside RestIt(...) at j+1 in C we take the first symbol in S and see if occurs in C before j+1
6. If it does not, then fill the j+1th position in C by that element from s and go to step5 with j+2.
7. If it occurs move on to the next symbol in S and go to step 5 with the same j+1.
Example S = [1,2,3,4]
C = 2,4,3
At 3 in C by step 1 we do not have anything so we move on to 4,but this is that last index in S so we move on to 2, finally we have 3 in S so that 3>2 put that in place of 3. We have 343, give this (343) to RestIt(…). Now RestIt(…) will place 1 from S in place of 4in C and 2 from S in place of 3 in C giving us 312.
Is this OK.
1. find x so that b*x < a <b*(x+1). x is quotient and a-b*x = remainder.
Some clarification : 100,70,90 imagine as a BST though the problem is not for a BST.then we have N(100) L(70) R(90).
O(n) means in almost one Tree traversal you should figure out the solution.
(n-2)*(2^n-3)
- Doctor.Sai December 20, 2011Please note it is not permutation but combination (without repetitions of symbols).
- Doctor.Sai December 20, 2011Let L denote a left traversal and R denote a right traversal.
U need to find out the longest LRLRLRLR...
I think having given this explanation the solution is easy.
1. For each node (in the multiple node list) store its path from root to itself say each path in an array. This can be done by pre - order search. Remember this not a BST.
2. Let A,B,C,.. M be such arrays. (count m).
3. Let n be the shortest of the above paths. you can also collect the arrays that yield the shortest paths.
for (i=0; i<n;i++)
{
if( i is not within the range of any one Array Say H)
{
then last element of H is the LCA;
break;
}
if(A[i] == B[i] == ... == M[i]);//great do nothing
else
{
A[i-1] is the LCA.
break;
}
}
In fact Br array lets us know the sequences that yield the solution.
No of solutions is Number of consecutive 0's * Number of consecutive 1's in the Br array.
Here is both proof and algorithm:
Let the original array A be of length n. Build another array B of length n-1 of only 0s and 1s. B[i] = 0 if a[i]-a[i+1] >=0 else B[i] = 1. This can be done in O(n). Now we have an array of only 0s and 1, now the problem is to find alternating continuous 0s and 1s. A continuous sub array array in B of 0s will be represented by any one of its elements. For example:
If B is = [0,0,0,0,0, 1,0,0,0,1,0,1,1,1,0] then we can reduce B to Br which = [0,1,0,1,0,1,0] in O(n) , infact we just need to find the size of Br which can be done by just one iteration. And that my friend is the answer to the given problem. So total complexity is O(n) + O(n) = O(n).
Let me know if this explanation is not enough.
is it not post order traversal and exchanging the left and right nodes
- Doctor.Sai December 18, 2011Agreed, this is also a brilliant technique
- Doctor.Sai December 15, 2011Ooooooooooooops again this is wrong. final and correct space calculation formula.
say n symbols are given and r spaces are allowed.
the space s = 1+n+n^2+n^3 + ... + n^(r-1). Now s will be the size of the array.
Ops one small correction space allocation is n^size not nCsize or nCr
- Doctor.Sai December 15, 2011Brilliant idea, one small development to this idea.Since the tree is going to be a complete n-array Tree(in our case ternary tree), it can be built using only arrays, just like in heap.
1. First allocate nCr array of bytes. and fill the first three places by A,B and C.
2. formula for calculating children is as follows.
3. for any element at an index i, its n children need to be placed at n*i+(n), n*i+(n+2),... n*i+(n+n-1).
4. fill each of its children's indices by the symbol array as long as these indices are within bounds of the array.
5. All that is left to do is Depth first traversal iteratively.
Repeat steps 1 to 5 starting with next elemennt form the Symbol array and so on.
why not 1, 12 and so on
- Doctor.Sai December 14, 2011take a thread of some length m , draw a circle using that string of radius m on the sand. Use the same thread wrap it around the circle find the length , let it be n. n/ 2*m = (approx) PI. since cave man knows basic maths he can divide.
- Doctor.Sai December 14, 2011what is example for a corrupted sum.
- Doctor.Sai December 14, 2011if(p-q) >0 P is the longer list.
else if((p-q)<0 Q is the longer list.
else they both are equal.
is it not max level = max depth, use level order traversal which is an iterative procedure use Q and easily figure out the max level.
- Doctor.Sai December 14, 2011Why not exchange the contents of last node with root node
- Doctor.Sai December 14, 2011Yes Trim tree won't work, Make BST from this array 100 is root {100,80,10,5,11,90,85,95,120,110,108,115,150,145,170}, it resolves to a complete BST of height 4. Trim Tree for all values between 90 and 110 including 90 and 110 does not make sense. 80, and 120 will hang above 90 and 110. We can only return all values between two given numbers.
So Question is ambiguous.
Use iterative inorder traversal and When poping enqueue them into a Q immediately see if size of Q ==2 if so dequeue and make right pointer of the dqueued element point to next element in Q.
- Doctor.Sai December 13, 2011Question not clear, if linked list is singly linked nothing can be done. If it is doubly linked ... cannot think beyond please provide a sample.
- Doctor.Sai December 06, 2011Forgot to mention BST is not balanced
- Doctor.Sai December 06, 2011we can do it in O(k + log(z)) time , where k = number of printed nodes (between n and m) and z = total number of nodes in the BST.
say n<m
Like in order
if currval of the node <= n go right
if(currval of the node is in between n and m print)
if currval of the node > m go left
Take this as a BST (it will be easy to explain)
- Doctor.Sai December 26, 2011100,90,80,10,85,94,91,95,200,300,250.
Let p = LL
So S will be LL, LL, LL, LL, … problems simply reduces to finding longest length of only left traversal.
First get all nodes that occur as only left traversal
1. L1 = 100, 90, 80, 10.
2. L2 = 94, 91.
3. L3 = 300, 250.
Longest is L1,