y2km11
BAN USER- 0of 0 votes
AnswersF2F Round4 Q2
- y2km11 in India for Kindle-Periodicals
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 Kindle-Periodicals
Given two strings str1 and str2, write code to find out if all non-unique elements in str2 are in str1?| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer - 0of 0 votes
AnswersF2F Round3 Q3
- y2km11 in India for Kindle-Periodicals
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 Kindle-Periodicals
Design a chess game.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer - 0of 0 votes
AnswersF2F Round3 Computer Fundamentals
- y2km11 in India for Kindle-Periodicals
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 Kindle-Periodicals
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 Kindle-Periodicals
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 Kindle-Periodicals
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 Kindle-Periodicals
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 Kindle-Periodicals
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 Kindle-Periodicals
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 Kindle-Periodicals
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 Kindle-Periodicals
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 Kindle-Periodicals
Find the position of first '1' in a sorted array that contains only 0-s and 1-s.| 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() );
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+c-1; i++ )
print(a[sr][i]);
for( i = sr; i <= sr+r-1; i++ )
print(a[i][sc+c-1]);
if( r != 1 )
for( i = sc+c-1; i >= sc; i-- )
print(a[sr+r-1][i]);
if( c != 1 )
for( i = sr+r-1; i >= sr+1; i-- )
print(a[i][sc]);
if( r-2 <= 0 || c-2 <= 0 )
return;
else
spiraltraversal( a, r-2, c-2, 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() );
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() );
char* result = new char[2*n];
result[0] = '{';
result[2*n-1] = '}';
for( i = 1; i <= 2*n; i++ )
if( i <= n )
a[i-1] = '{';
else
a[i-1] = '}';
print(result);
while( 1 )
{
if( a[2*n-2] == '{' && a[1] == '{' }
break;
validator = 0;
countopen = 0;
countclose = 0;
i = 2*n-2;
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 != 2n-2 )
{
if( validator+1 <= n && countopen+1 <= n )
validator++;
countopen++;
a[i++] = '{';
else
validator--;
countopen--;
a[i++] = '}';
}
print(result);
}
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] );
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;
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 pre-order 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
}
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;
}
You can write a post-order 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() );
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;
}
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, Rabin-Karp, 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+k-LQ1 = N-LQ2
N = L(Q1-Q2)-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 N-ary 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() );
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 );
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;
}
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++;
}
}
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;
}
}
}
}
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;
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 M-th last element in the stack is the LCA.
- y2km11 July 24, 2019