y2km11
BAN USER 0of 0 votes
AnswersF2F Round4 Q2
 y2km11 in India for KindlePeriodicals
Write code to find Nth last node in a linked list. Report Duplicate  Flag  PURGE
Amazon Software Engineer / Developer  0of 0 votes
AnswersF2F Round4 Q1
 y2km11 in India for KindlePeriodicals
Given two strings str1 and str2, write code to find out if all nonunique elements in str2 are in str1? Report Duplicate  Flag  PURGE
Amazon Software Engineer / Developer  0of 0 votes
AnswersF2F Round3 Q3
 y2km11 in India for KindlePeriodicals
Given a binary tree build a vertical sum array. Report Duplicate  Flag  PURGE
Amazon Software Engineer / Developer  0of 0 votes
AnswersF2F Round3 Q2
 y2km11 in India for KindlePeriodicals
Design a chess game. Report Duplicate  Flag  PURGE
Amazon Software Engineer / Developer  0of 0 votes
AnswersF2F Round3 Computer Fundamentals
 y2km11 in India for KindlePeriodicals
What is the difference between a 32bit and 64processor?
What is the difference between a 1.8Ghz processor and a 2.3GHz processor?
Invent your own tables and write a query to get top 10 mobile numbers with the highest 3G data usage. Report Duplicate  Flag  PURGE
Amazon Software Engineer / Developer  0of 0 votes
AnswersF2F Round2 Q3
 y2km11 in India for KindlePeriodicals
Given a node in a binary tree, how will you find out if left and right subtrees are mirror images of each other? Report Duplicate  Flag  PURGE
Amazon Software Engineer / Developer  0of 0 votes
AnswersF2F Round2 Q2
 y2km11 in India for KindlePeriodicals
Given an array A, build another array B in which each element is the product of all elements in A other than the element at the same position. Write code that does this with and without division. Report Duplicate  Flag  PURGE
Amazon Software Engineer / Developer  0of 0 votes
AnswersF2F Round2 Q2
 y2km11 in India for KindlePeriodicals
Given an unsorted array and a number N, build pairs using the numbers in the array that add up to N. Report Duplicate  Flag  PURGE
Amazon Software Engineer / Developer  0of 0 votes
AnswersF2F Round1 Q4
 y2km11 in India for KindlePeriodicals
Find the biggest BST in a given binary tree. Report Duplicate  Flag  PURGE
Amazon Software Engineer / Developer  0of 0 votes
AnswersF2F Round1 Q3
 y2km11 in India for KindlePeriodicals
How will you find out if a given binary tree is a BST? Report Duplicate  Flag  PURGE
Amazon Software Engineer / Developer  0of 0 votes
AnswersF2F Round1 Q2
 y2km11 in India for KindlePeriodicals
Design a hash table. How do you address collisions? Report Duplicate  Flag  PURGE
Amazon Software Engineer / Developer  0of 0 votes
AnswersF2F Round1 Q1
 y2km11 in India for KindlePeriodicals
Write code that defines a data structure to perform these operations in an optimal way:
InsertAtTail
DeleteNodeAtPosition
GetTail Report Duplicate  Flag  PURGE
Amazon Software Engineer / Developer  0of 0 votes
AnswersWritten test Q2
 y2km11 in India for KindlePeriodicals
Given a binary tree and a number N, print all paths that start from root and add up to N. Report Duplicate  Flag  PURGE
Amazon Software Engineer / Developer  0of 0 votes
AnswersWritten test Q1
 y2km11 in India for KindlePeriodicals
Find the position of first '1' in a sorted array that contains only 0s and 1s. Report Duplicate  Flag  PURGE
Amazon Software Engineer / Developer Algorithm Application / UI Design  0of 0 votes
AnswersSpiral traversal of an array.
 y2km11 in India for Bing Report Duplicate  Flag  PURGE
Microsoft Software Engineer / Developer Coding  0of 0 votes
AnswersConvert a BST to sorted doubly linked list.
 y2km11 in India Report Duplicate  Flag  PURGE
Amazon Trees and Graphs
In post order traversal, swap left and right subtrees instead of visiting
visited = NULL;
do
{
while( p != NULL )
stack.push(p);
p = p>left;
while( !stack.empty() )
{
temp = stack.top();
if( temp>right == NULL  temp>right == visited )
stack.pop();
swap( temp>left, temp>right ); // swap instead of visit
visited = temp;
continue;
if( temp>right != NULL )
p = temp>right;
break;
}
}while( p != NULL  !stack.empty() );

y2km11
March 14, 2012 Comment from OP
void spiraltraversal( int (*a)[], int r, int c, int startr = 0, int startc = 0 )
{
if( r == 1 && c== 1 )
print(a[sr][sc])
return;
for( i = sc; i <= sc+c1; i++ )
print(a[sr][i]);
for( i = sr; i <= sr+r1; i++ )
print(a[i][sc+c1]);
if( r != 1 )
for( i = sc+c1; i >= sc; i )
print(a[sr+r1][i]);
if( c != 1 )
for( i = sr+r1; i >= sr+1; i )
print(a[i][sc]);
if( r2 <= 0  c2 <= 0 )
return;
else
spiraltraversal( a, r2, c2, startr+1, startc+1 );
return;
}
 y2km11 March 08, 2012Can you please expand on that?
What betterment are you trying to achieve over this:
int *max, *secondmax;
max = secondmax = NULL;
for( i = 0; i < n; i++ )
{
if( max == NULL )
max = new int(a[i]);
else if( *max < a[i] )
if( secondmax == NULL ) secondmax = new int;
*secondmax = *max;
*max = a[i];
else if( *secondmax < a[i] )
*secondmax = a[i];
}
 y2km11 March 03, 2012This changes the data in a node to the recursive sum of its children's data.
NODE* max;
visited = NULL;
do
{
while( p != NULL )
stack.push(p);
p = p>left;
while( !stack.empty() )
{
temp = stack.top();
if( temp>right == NULL  temp>right == visited )
stack.pop();
temp>data += (temp>left)?temp>left>data:0;
temp>data += (temp>right)?temp>right>data:0;
if( max == NULL ) max = temp;
else if( max>data < temp>data ) max = temp;
visited = temp;
continue;
if( temp>right != NULL )
p = temp>right;
break;
}
}while( p != NULL  !stack.empty() );

y2km11
March 01, 2012 k //> given node
visitedK = false;
p = root;
do
{
while( p!=NULL )
stack.push(p);
p = p>left;
while( !stack.empty() ) // while  go to but the left node ladder
{
temp = stack.pop()
visit(temp);
if( visitedK == true )
return temp;
if( temp == k )
visitedK = true;
if( temp>right )
p = temp>right;
break;
}
}while( p!= NULL  !stack.empty() );

y2km11
February 29, 2012 char* result = new char[2*n];
result[0] = '{';
result[2*n1] = '}';
for( i = 1; i <= 2*n; i++ )
if( i <= n )
a[i1] = '{';
else
a[i1] = '}';
print(result);
while( 1 )
{
if( a[2*n2] == '{' && a[1] == '{' }
break;
validator = 0;
countopen = 0;
countclose = 0;
i = 2*n2;
do
{
if( a[i] == '{'
validator++;
countopen++;
else
validator;
countclose++;
i;
}while( a[i] != '{' );
countopen = n  countopen;
countclose = n  countclose;
validator = validator;
a[i++] = '}';
validator = 2;
countopen;
countclose++;
while( i != 2n2 )
{
if( validator+1 <= n && countopen+1 <= n )
validator++;
countopen++;
a[i++] = '{';
else
validator;
countopen;
a[i++] = '}';
}
print(result);
}

y2km11
February 28, 2012 Yes, that will no work if all numbers in the array are negative.
But this one will:
max = secondmax = thirdmax = 0;
min = secondmin = 0;
for( int i = 1; i < n; i++ )
{
candidate = i;
if( a[candidate] >= a[max] )
swap( secondmax, thirdmax );
swap( max, secondmax );
swap( candidate, max );
else if( a[candidate] >= a[secondmax] )
swap( secondmax, thirdmax );
swap( candidate, secondmax );
else if( a[candidate] > a[thirdmax] )
thirdmax = candidate;
candidate = i;
if( a[candidate] <= a[min] )
swap( min, secondmin );
swap( candidate, min );
else if( a[candidate] < a[secondmin] )
secondmin = candidate;
}
if( thirdmax == 0 )
return 0; // there are less than three elements in the array
return( a[max]*a[secondmax]*a[thirdmax], a[max]*a[min]*a[secondmin] );

y2km11
February 28, 2012 Use slow/fast pointers to reach the middle node. While doing this reverse the first half of the linked list inplace. Now you have two linked lists > compare node by node. While doing this reverse the first half again.
p = q = head;
prev = NULL;
while( q != NULL )
{
q = q>next;
if( q>next != NULL )
q = q>next;
break;
// reverse the linked list till p  middle node
temp = p>next;
p>next = prev;
prev = p;
p = temp;
}
forward = temp;
// move p one step backward for linked lists with odd number of elements
if( q == NULL )
temp = p>next;
p>next = forward;
p = temp;
prev = p;
else
prev = temp;
backward = p;
bool palindrome = true;
while( backward != NULL )
{
if( forward>data != backward>data )
palindrome = false; //don't return yet, you have to reverse the list fully
// reverse first half of the linked list again
forward = forward>next;
temp = backward;
backward>next = prev;
backward = temp;
}
return palindrome;

y2km11
February 27, 2012 The recursive solution is straight forward. But to do this non recursively, you need to verify two sets of straight and mirrored traversals are the same  we check preorder and post order here.
bool CheckMirroringRecursive( NODE tree1, NODE tree2 )
{
if( tree1 == NULL && tree2 != NULL )
return false;
if( tree1 != NULL && tree2 == NULL )
return false;
if( tree1>data != tree2>data )
return false;
return CheckMirroringRecursive(tree1>left, tree2>right) && CheckMirroring(tree1>right, tree2>left)
return false;
}
bool CheckMirroringNonRecursive( NODE tree1, NODE tree2 )
{
_stack stack1, stack2;
NODE temp;
NODE nextPreOrderNode = NULL, nextInOrderNode = NULL;
do
{
nextPreOrderNode = NextPreOrderSuccessor(tree1, stack1, true);
nextInOrderNode = NextInOrderSuccessor(tree2, stack2, temp, true);
if( nextPreOrderNode == NULL && nextInOrderNode != NULL )
return false;
if( nextPreOrderNode != NULL && nextInOrderNode == NULL )
return false;
if( nextPreOrderNode>data != nextInOrderNode>data != NULL )
return false;
}while( nextPreOrderNode != NULL && nextInOrderNode =! NULL );
return true;
}
NODE NextPreOrderSuccessor( NODE &p, _stack &stack, bool mirror/*=false*/ )
{
if( p != NULL)
{
stack.push(p);
p = (mirror)?p>right:p>left;
return stack.top();
}
while( !stack.empty() )
{
temp = stack.pop();
if( ((mirror)?temp?left:temp>right) != NULL )
p = mirror?temp>left:temp>right;
break;
}
if( p == NULL  stack.empty() )
return NULL; // end of traversal
}
NODE NextInOrderSuccessor( NODE &p, _stack &stack, NODE &lastVisited, bool mirror/*=false*/ )
{
if( p != lastVisited )
while( p!=NULL )
stack.push(p);
p = mirror?p>right:p>left;
if( !stack.empty() )
{
temp = stack.pop()
lastVisited = temp;
if( mirror?temp>left:temp>right )
p = mirror?temp>left:temp>right;
return temp;
}
if( p == NULL && stack.empty() )
return NULL; // end of traversal
}

y2km11
February 26, 2012 bool AreAllLeavesSame( NODE tree1, NODE tree2 )
{
NODE leafFromTree1, leafFromTree2;
_stack stack1, stack2;
NODE visited1, visited2;
do
{
leafFromTree1 = returnNextLeaf( tree1, stack1, visited1 );
leafFromTree2 = returnNextLeaf( tree2, stack2, visited2 );
if( leafFromTree1 != leafFromTree2 )
return false;
}while( leafFromTree1 != NULL && leafFromTree2 != NULL );
return true;
}
NODE returnNextLeaf( NODE &p, _stack &stack, NODE &visited )
{
do
{
if( visited == p>left )
while( p != NULL )
{
stack.push(p);
p=p>left;
}
if( !empty.stack() )
{
temp = stack.top();
if( temp>right == NULL  visited == temp>right )
visit(temp);
visited = temp;
stack.pop();
else
p = p>right;
}
if( visited>left == NULL && visited>right == NULL )
return visited;
}while( p != NULL  !stack.empty() );
return NULL;
}

y2km11
February 25, 2012 You can write a postorder traversal algo such that when a node is traversed, all parents will be in the stack.
For each node inserted, insert a flag also. This flag will be initially zero.
When the first node to be found is traversed, set StackLengthWhenFirstNodeIsFound to length of stack.
Continue traversing but now for all nodes pushed into the stack, set the flag as 1 not a 0.
When the second node to be found is traversed, stop traversing. find path length as:
pathlength = StackLengthWhenFirstNodeIsFound;
pathlength = stack.NumberofNodesWithFlagSetTo(0);
pathlength += stack.NumberofNodesWithFlagSetTo(1);
f1, f2 // nodes to be found
p = root;
visited = NULL;
bool found = false;
int StackLengthWhenFirstNodeIsFound = 1;
NODE* foundFirst = NULL;
int pathlength;
do
{
while( p != NULL )
{
if( p == f1 )
f1 = NULL;
if( StackLengthWhenFirstNodeIsFound == 1 )
StackLengthWhenFirstNodeIsFound = stack.length();
foundFirst = p1;
if( p == f2 )
// do the same for f2
if( StackLengthWhenFirstNodeIsFound != 1 && p != foundFirst )
found = true;
break;
stack.push(p,StackLengthWhenFirstNodeIsFound==1?0:1);
p=p>left;
}
if( found )
pathlength = StackLengthWhenFirstNodeIsFound;
pathlength = stack.NumberofNodesWithFlagSetTo(0);
pathlength += stack.NumberofNodesWithFlagSetTo(1);
return pathlength;
while( !empty.stack )
{
temp = stack.top();
if( temp>right == NULL  visited == temp>right )
visit(temp);
visited = temp;
stack.pop();
else
p = p>right;
break;
}
}while( p != NULL  !stack.empty() );

y2km11
February 25, 2012 Comment from OP:
NODE* convert( NODE* head )
{
if( head>next == NULL ) // handle lists of length 1
return head;
if( head>next>next ) // handle lists of length 2
head>next>prev = NULL;
return head;
NODE* middle = MIDDLENODE(head);
NODE* middlenext = middle>next;
if( middlenext )
middle>next>prev = NULL;
middle>next = NULL;
convert( head, middle );
convert( middlenext, LASTNODE(head) );
return middle;
}

y2km11
February 25, 2012 Tweak suffix tree(or a trie) and make each leaf to contain a list of starting indexes of individual occurrences of a suffix.
Preprocessing  O(nlogn)
Searching  O(logn)
Space  O(n^2)
So, this is clearly scalable only of very large lengths of the original string and pattern. For smaller lengths, RabinKarp, Naive searching work better.
Comment from OP:
Tweaked inorder traversal and gave the below answer
BST to sorted LL
p = root;
visited = NULL;
do
{
while( p!=NULL )
stack.push(p);
p = p>left;
while( !stack.empty() )
{
temp = stack.pop()
visit(temp);
if( visited != NULL )
visited>right = temp;
temp>left = visited;
visited = temp;
if( temp>right )
p = temp>right;
break;
}
while( p!= NULL  !stack.empty() );
You need to an inorder traversal(which takes up O(n) space) to realize the sortedness of the number. Having said that, is there any way to do this in O(1) space?
 y2km11 February 25, 2012I proved it this way:
N > number of steps the slower node made in the loop before meeting the faster
L > length of the loop
k > number of steps faster was ahead of slower when the slower entered the loop(offset)
When the pointers met, they were at the same displacement(hence the %) from the beginning of the loop.
(2N+k)%L = N%L
2N+kLQ1 = NLQ2
N = L(Q1Q2)k
N is a multiple of L > both pointers met at the starting point
k > k steps before the starting point
This can be easily extended to Nary trees, replace line10 with a loop that goes through all children and of course, push and pop all N operands.
do
{
while( p != NULL )
stack.push(p);
p = p>left;
while( !stack.empty() )
last = stack.pop();
lastbutone = stack.pop()
if( isoperator(lastbutone)
if( isoperand(lastbutone>right) )  // line 10
stack.push(operate(last, lastbutone, lastbutone>right));
else{
push(lastbutone);
push(last);
break;
else
stack.push(operate(last, stack.pop(), lastbutone));
}while( !stack.empty() );

y2km11
February 23, 2012 fast = slow = headbackup = head;
count = 0;
do
{
if( fast>next != NULL )
fast = fast>next>next;
count = count + 2;
else
return ++count;
slow = slow>next
}while( slow != fast );
// the point at which slow and fast meet will be at the same distance from the start of the loop as the distance between head and start of the loop
// count the length of the LL segment that is not in the loop
count = 0;
while( headbackup != slow )
count++;
headbackup = headbackup>next;
slow = slow>next;
// count the length of the LL segment that is in the loop
do
{
count++;
slow = slow>next;
while( slow != headbackup );

y2km11
February 23, 2012 Twist: Handle negative numbers and out of range case
int atoi( char* source )
{
int ret = 0;
int negative = 1;
char* i = source;
if( *i == '' ){
negative = 1;
i++;
}
for( ; *i; i++ )
{
if( *source >= '0' && *source <= '9' ){
int temp = ret*10 + (negative)*(*source'0');
if( temp < MININT  temp > MAXINT )
return 0; // or whatever is your out of range handler
else
ret = temp;
else
return ret;
}
return ret;
}

y2km11
February 23, 2012 You can more form than one binary trees for a given preorder traversal. That means there could be more than one solution preorder sequences. For eg, for the given preorder traversal if you form a binary tree with all left pointers NULL, then the solution sequence is (320, 270, 240, 230, 190, 130, 0) not (270, 50, 0, 0, 130, 0, 0) as mentioned in the question . This is also is the easiest solution sequence that can be formed  cumulative sum.
Can the original poster confirm that he is not missing something?
push( stack0, root );
currentstack = stack0;
otherstack = stack1;
level = 0;
while( !currentstack.empty() )
{
temp = pop(currentstack);
visit(temp);
if( level%2 == 0 )
{
push( otherstack, temp>right ); // assume push doesn't work if data is NULL
push( otherstack, temp>left );
}
else
{
push( otherstack, temp>left );
push( otherstack, temp>right );
}
if( currentstack.empty() )
{
swap( currentstack, otherstack ); // pointer swap
level++;
}
}

y2km11
February 22, 2012 int min, max, contendermin;
min = max = contendermin = 1;
for( int i=0; i<n; i++ )
{
if( min == 1 && max == 1 )
min = i;
else
{
if( a[min] > a[i] )
if( max == 1 )
min = i;
if( contendermin == 1  a[contendermin] > a[i] )
contendermin = i;
else if( max == 1 )
max = i;
else if( a[max] < a[i] )
{
max = i;
if( contendermin != 1 )
{
min = contendermin;
contendermin = 1;
}
}
}
}

y2km11
February 22, 2012 char* prev = 0;
int currentcount = 0;
char* writehere = source;
for( char* i = source; *i; i++ )
{
if( prev == NULL  *prev != *i )
{
if( prev != NULL )
{
*writehere++ = *prev
if( currentcount > 1 ){
char* temp = itoa( currentcount, writehere, 10 );
writehere += strlen(temp);
}
}
prev = i;
currentcount = 1;
}
else
currentcount++;
}
*writehere = 0;

y2km11
February 22, 2012
1) Post order like traversal where all parents are in a stack when a node is visited.
2) When each node in lstpNodes is visited, record the size of the stack. Pick out the smallest among those values. Call it M.
3) When all nodes in lstpNodes have been visited, the Mth last element in the stack is the LCA.
 y2km11 July 24, 2019