Vin
BAN USER 0of 0 votes
AnswerDifference between Trie and Narray tree.
 Vin in India Report Duplicate  Flag  PURGE
Ebay Software Engineer / Developer Algorithm  0of 0 votes
AnswersList of parent and child of a binary tree are given in the format (parent, child) –> (p1,c1) (p2,c2) etc [ie, binary tree represented by adjacency list]
 Vin in India
How to check "loop" exists in this binary tree or not efficiently. Report Duplicate  Flag  PURGE
Amazon SDE2 Algorithm  1of 1 vote
AnswersList of parent and child of a binary tree are given in the format (parent, child) –> (p1,c1) (p2,c2) etc [ie, binary tree represented by adjacency list]
 Vin in India
How to check "loop" exists in this binary tree or not in efficiently. Report Duplicate  Flag  PURGE
Amazon SDE2 Algorithm  2of 2 votes
AnswersThere is a sentence that your friend knows, but while giving it to you, he lost all the spaces. You have a dictionary with you, that will tell you given word exist or not. How would you reconstruct the original sentence using it.
 Vin in India Report Duplicate  Flag  PURGE
Amazon SDE2  0of 0 votes
AnswersGiven a chess board of finite length (NxN), start position of a knight(x, y) and an end position (p, q). 1) Find number of minimum hops required to reach end position.
 Vin in India
2) Check your solution extendable to infinite length chess board ?? Report Duplicate  Flag  PURGE
Amazon SDE1  1of 1 vote
AnswersDesign a DS to perform
 Vin in India
1. Insert
2. Search
3. Delete
4. Get Random
All in O(1). Report Duplicate  Flag  PURGE
Amazon SDE1  4of 4 votes
AnswersA student needs to implement a BST structure to solve a problem, but instead he used a linked list. New value will always be added at beginning of a linked list. So basically at each step after insertion , root of BST and head of link list should point to same node. Then give an example of input sequence, in which his implementation works…
 Vin in India Report Duplicate  Flag  PURGE
Amazon SDE1  0of 2 votes
AnswersGiven an array consisting of both positive and negative numbers, 0 is considered as positive, rearrange the elements such that positive and negative numbers are placed alternatively, constraints are that it should be inplace and order of elements should not change.
 Vin in India Report Duplicate  Flag  PURGE
Amazon SDE1  4of 6 votes
AnswersFind the nearest leaf node from given node in binary tree.
 Vin in India Report Duplicate  Flag  PURGE
Amazon SDE2  1of 7 votes
AnswersFind maximum product of subarray in given array of integers
 Vin in India Report Duplicate  Flag  PURGE
Amazon SDE2  1of 1 vote
AnswersDesign T9 dictionary
 Vin in India Report Duplicate  Flag  PURGE
Amazon SDE2  11of 13 votes
AnswersThere are some glasses with equal volume 1 litre. The glasses kept as follows
1 2 3 4 5 6 7 8 9 10
You can put water to only top glass. If you put more than 1 litre water to 1st glass, water overflow and fill equally both 2nd and 3rd glass. Glass 5 will get water from both 2nd glass and 3rd glass and so on..
 Vin in India
If you have X litre of water and you put that water in top glass, so tell me how much water contained by jth glass in ith row.
Example. If you will put 2 litre on top.
1st – 1 litre
2nd – 1/2 litre
3rd  1/ Report Duplicate  Flag  PURGE
Amazon SDE1  0of 0 votes
AnswersAn array of size N is given. The array contains digits from 0 to 9. Generate the maximum number using the digits in the array such that it is divisible by 2, 3 and 5
 Vin in India
input: {1,8,7,6,0}, output: 8160
input: {7,7,7,6,}, output : none(1) Report Duplicate  Flag  PURGE
General Questions and Comments  0of 0 votes
AnswersThere is a binary tree of size N. All nodes are numbered between 1N(inclusive). There is a N*N integer matrix Arr[N][N], all elements are initialized to zero. So for all the nodes A and B, put Arr[A][B] = 1 if A is an ancestor of B (NOT just the immediate ancestor).
 Vin in India Report Duplicate  Flag  PURGE
Amazon Software Engineer / Developer Matrix
1. take an array of size 256 and initialize it to zero.
2. scan the input string from beginning and increment corresponding index of array(ie array[input string[i] ]++ ).
3. scan the input string from beginning and check 1 == array[input string[i] ]. if such exist, input string[i] will be the answer.
Virtual pointers are implemented by virtual table. For each derived class, there will be one virtual table. So this single table will be applicable for all objects created from the same derived class.
virtual table not related to objects, it is related to derived class.
if the LL is read only  there is another way.
1. traverse list form start to middle and put the data to a stack.
2. from middle to end, pop the data from stack and compare to the current node.
Note: needs to take care about even and odd size list.
This will take O(n) space.
Actual question behind this question is do you know how to serialize and de serialize a binary tree.
There are several mechanism available for the same. Do any traversal(pre\in\post) and represent a null child with a special delimiter(a bit or any special character). Do the reverse to de serialize the tree taken care of delimiter.
1. take 2 pointers which points to the beginning and middle element of LL
2. reverse the LL from middle to end of LL
3. now compare the values pointed by beginning and middle elements. is same increment both pointers. else not a palindrome(break)
4. continue step 3 until second pointer reaches the end
5. reverse the second half of the LL to restore the original LL.
1. initialize smallest_range as MAX_INT
2. keep 3 pointers/index p1, p2 and p3 which points to the first elements of lists L1, L2 and L3 respectively.
3. get the sum of minimum difference using pointed/indexed by p1, p2 and p3
4. compare it with smallest_range and update it, if found smaller.
5. increment the pointer/index of min value found in step 3.
6. repeat step 3 to 5 until the pointer/index of min value is in range.
This can be done in 3 steps:
1. covert the BSTs to sorted linked list (this can be done in place with O(m+n) time)
2. Merge this two sorted linked lists to a single list (this can be done in place with O(m+n) time)
3. Convert sorted linked list to balanced BST (this can be done in place with O(m+n) time)
@aka  yes, you are correct, i dint thought of all the possible cases. I think we can consider the same approach after little modifications. for every element we should consider only a window size of n only.
so for 1,2,3,0,6,1,2,3,0,6, if we considers first 0 as the start point, consider elements only up to second zero(window size 5). this will resolve the issue.
i would say, append the input array to the end of input array. Now the input array becomes a bigger array of size is 2n.
5 4 3 2 1 becomes 5 4 3 2 1 5 4 3 2 1.
Now apply LIS algo. it would give the circular LIS 1 5 .
5 6 7 1 2 3 becomes 5 6 7 1 2 3 5 6 7 1 2 3 and gives the result  1 2 3 5 6 7.
your approach is right, but there are potential bug in the code:
if(root == NULL) {
if(!IsEmptyQueue(Q))
EnQueue(Q,NULL);
if(root>left) > root is null, so will crash it here.
print("%d",Q>left); > right node can be the leftmost
}
this should be changed to:
if(root == NULL) {
if(!IsEmptyQueue(Q)) {
print front element of the queue
EnQueue(Q,NULL);
}
}

Vin
August 03, 2013 your solution is correct, here the pit falls is how to map a ve no to the corresponding bit in the bit map.
For each X in the array, you should add 2^(n1) to get the correct bit position in the bit map. Here n is the no of bits used to represent X (ie, 8*sizeof(X))
it can be done by finding all permutation of the given digits without rep, then add each numbers formed. there are totally 4! numbers to add.
Let number = 1234
let sum = 1234.
1. Find the largest index k such that a[k] < a[k + 1]. If no such index exists, the permutation is the last permutation.
2. Find the largest index l such that a[k] < a[l]. Since k + 1 is such an index, l is well defined and satisfies k < l.
3. Swap a[k] with a[l].
4. Reverse the sequence from a[k + 1] up to and including the final element a[n].
5. sum = sum + newly formed number on step 4.
Read this 2 files to 2 linked lists. Each node in the linked list will store a digit of the big number.
Now we have 2 linked lists representing 2 big numbers. Now the problem became, addition of 2 linked lists and store the result in 3rd list. This can be done in O(M+N) complexity.
Pseudo code :
int maxsubsetsum(int* lst, int numItems) {
if (numItems < 1  NULL == lst ) {
return 1;
} else if (numItems == 1) {
return lst[0];
}
else if (numItems == 2) {
return Max(lst[0], lst[1]);
}
else if (numItems == 3) {
return Max(lst[0], lst[1], lst[2], lst[0]+lst[2]);
}
int S[numItems] = {0};
S[0] = lst[0];
S[1] = lst[1];
S[2] = Max(lst[0], lst[2], lst[0]+lst[2]);
for (int i = 3; i < numItems; i++) {
int subMax = Max(S[i2], S[i3])
S[i] = Max(lst[i], subMax, subMax+lst[i]);
}
return Max(S[numItems1], S[numItems2]);
}

Vin
June 05, 2013 Node* kSmallest(Node* curr, int* k){
Node* result = NULL;
if (NULL != curr) {
result = kSmallest(curr>left, k);
if (NULL == result ) {
(*k);
if (k == 0) {
result = curr;
}
else {
result = kSmallest(curr>right, k);
}
}
}
return result;
}
Node* findSmallest(Node* curr, int k) {
int smallest = k;
return kSmallest(curr, &smallest);
}

Vin
June 03, 2013 Logic is simple:
Take 2 pointers which initially points to the start of the array. Here first one represents the end of string without 'b' and 'ac' and first represents the current scan position.
scan the array from the start to end
if the current characters is 'b' or 'ac', increment only second pointer appropriately
if the current characters is not 'b' and 'ac', swap characters pointed by two pointers and then increment both pointers.
result will be the string from the start of the array to the location pointed by first pointer.
void removeBandAC(char *p, int size)
{
int i = 0;
int j = 0;
while( i < size )
{
if (p[i] == 'b')
{
i++;
}
else if ((p[i] == 'a') && (i+1 < size) && (p[i+1] == 'c'))
{
i += 2;
}
else
{
if (i != J) swap(p[i], p[j]);
i++;
j++;
}
}
p[j] = '\0';
}

Vin
May 18, 2013 public void changeTree(BinaryTree root, int rightSum) {
if (root != null) return 0;
int rightValue = changeTree(root.right, rightSum);
root.data += rightValue + rightSum;
changeTree(root.left, root.data);
return root.data;
}
initial call should be changeTree(root, 0);

Vin
April 22, 2013
log(N) time. sorry again.
 Vin April 06, 2014