Re: [algogeeks] Amazon interview Questions
Round 1 : Q2: given BST is not correct. correct BST passing this condition will be 7 / 5 / 3 \ 4 in this case the root element of given BST will be the largest if left child exist or will be the smallest if right child exist. so you just need to start checking the last value of given post order. eg: in this case post order will be 4 3 5 7 here last value is 7 so it is greatest among all so left nde exist. next is 5 which is largest of remaining so left node exist for this next is 3 which is smallest of remaining so 4 will come on right node. On Wed, Jun 5, 2013 at 5:14 PM, Ravi Ranjan ravi.cool2...@gmail.com wrote: Can u clear Round3 --- Qstn-3. the language is not cleared On Wed, Jun 5, 2013 at 1:52 PM, sourabh jain wsour...@gmail.com wrote: Round 1: 1.Design a Data Structure supporting 3 queries a)push b)pop c) find minimum Ans : Do it using Two Stacks . in first stack use it as normal stack. second stack use it to find minimun as the value inserted is greater than the top ignore it else push it. if pop operation happens and the value popped is equal to the top(s2) then pop(s2). time complexity push : O(1) , pop O(1) , find Minimum O(1) 2.Given post order of a BST find whether each node of the tree(except leaf) has only 1 child or not. eg5 \ 7 / 3 / 2 is correct as each node has only 1 child. Round 2: 1.Given a sorted array a and a sum k print all pairs of indexes i and j such that a[i]+a[j]=k. put one pointer at index 0 and 2nd at length(ar)-1. while (ij){ if(ar[i]+ar[j]==k) {printpairs; i++; j++;} else if(ar[i])+ar[j] k) i++; else if(ar[i])+ar[j] k) j--; } 2.Given a matrix that is row and column wise sorted give an algo for finding count of the total no of -ve nos. start from (0,n) move towards right if found +ve and increment count of positive in row. else move down . Round 3: 1.Given a matrix consisting of nos you can print the max length of sequence possible where in a sequence each consecutive nos have a diff of +1 or -1. eg 3 5 7 3 4 5 8 1 6 4 5 2 here sequence is 3 4 5 4 5 *you can do it using recursion * 2.Give a data structure that supports following queries a)insert b)delete c)ispresent d)print all elements *BST's ... , if insertionorder needs to be maintained then linked list;* 3.Given a infinite supply of n cylinders where each cylinder is specified by weight of 02,weight of n2,total weight , now u need some minimum quantity of o2 and n2 by selecting cylinders and your aim is make it so that u have min total weight. output the minimum total weight . Round 4: 1.Given 2 sorted arrays find there median .http://www.geeksforgeeks.org/median-of-two-sorted-arrays/ 2.Consider column of ms excel the start with A,BZ,AA Now u r given column no u need to print its name *Ans : Same as number system problem with base 26* 3.Given 2 arrays.Imagine you are making bst from each array.u need to tell whether 2 bsts will be identical or not without actually constructing the tree. eg 1 2 3 1 3 2 will construct the same tree On Mon, Jun 3, 2013 at 10:52 PM, *$* gopi.komand...@gmail.com wrote: these are for which position? and experience? On Thu, May 2, 2013 at 9:27 PM, Guneesh gunees...@gmail.com wrote: Round 1: 1.Design a Data Structure supporting 3 queries a)push b)pop c) find minimum 2.Given post order of a BST find whether each node of the tree(except leaf) has only 1 child or not. eg5 \ 7 / 3 / 2 is correct as each node has only 1 child. Round 2: 1.Given a sorted array a and a sum k print all pairs of indexes i and j such that a[i]+a[j]=k. 2.Given a matrix that is row and column wise sorted give an algo for finding count of the total no of -ve nos. Round 3: 1.Given a matrix consisting of nos you can print the max length of sequence possible where in a sequence each consecutive nos have a diff of +1 or -1. eg 3 5 7 3 4 5 8 1 6 4 5 2 here sequence is 3 4 5 4 5 2.Give a data structure that supports following queries a)insert b)delete c)ispresent d)print all elements 3.Given a infinite supply of n cylinders where each cylinder is specified by weight of 02,weight of n2,total weight , now u need some minimum quantity of o2 and n2 by selecting cylinders
Re: [algogeeks] Amazon interview Questions
Hi ravi , I think he is trying to find the longest possible increasing chain in matrix . he needs to start traversing from first row choosing columns one by one and move in all direction. but he needs to maintain the already visited nodes. On Thu, Jun 6, 2013 at 12:07 AM, sourabh jain wsour...@gmail.com wrote: Round 1 : Q2: given BST is not correct. correct BST passing this condition will be 7 / 5 / 3 \ 4 in this case the root element of given BST will be the largest if left child exist or will be the smallest if right child exist. so you just need to start checking the last value of given post order. eg: in this case post order will be 4 3 5 7 here last value is 7 so it is greatest among all so left nde exist. next is 5 which is largest of remaining so left node exist for this next is 3 which is smallest of remaining so 4 will come on right node. On Wed, Jun 5, 2013 at 5:14 PM, Ravi Ranjan ravi.cool2...@gmail.comwrote: Can u clear Round3 --- Qstn-3. the language is not cleared On Wed, Jun 5, 2013 at 1:52 PM, sourabh jain wsour...@gmail.com wrote: Round 1: 1.Design a Data Structure supporting 3 queries a)push b)pop c) find minimum Ans : Do it using Two Stacks . in first stack use it as normal stack. second stack use it to find minimun as the value inserted is greater than the top ignore it else push it. if pop operation happens and the value popped is equal to the top(s2) then pop(s2). time complexity push : O(1) , pop O(1) , find Minimum O(1) 2.Given post order of a BST find whether each node of the tree(except leaf) has only 1 child or not. eg5 \ 7 / 3 / 2 is correct as each node has only 1 child. Round 2: 1.Given a sorted array a and a sum k print all pairs of indexes i and j such that a[i]+a[j]=k. put one pointer at index 0 and 2nd at length(ar)-1. while (ij){ if(ar[i]+ar[j]==k) {printpairs; i++; j++;} else if(ar[i])+ar[j] k) i++; else if(ar[i])+ar[j] k) j--; } 2.Given a matrix that is row and column wise sorted give an algo for finding count of the total no of -ve nos. start from (0,n) move towards right if found +ve and increment count of positive in row. else move down . Round 3: 1.Given a matrix consisting of nos you can print the max length of sequence possible where in a sequence each consecutive nos have a diff of +1 or -1. eg 3 5 7 3 4 5 8 1 6 4 5 2 here sequence is 3 4 5 4 5 *you can do it using recursion * 2.Give a data structure that supports following queries a)insert b)delete c)ispresent d)print all elements *BST's ... , if insertionorder needs to be maintained then linked list;* 3.Given a infinite supply of n cylinders where each cylinder is specified by weight of 02,weight of n2,total weight , now u need some minimum quantity of o2 and n2 by selecting cylinders and your aim is make it so that u have min total weight. output the minimum total weight . Round 4: 1.Given 2 sorted arrays find there median .http://www.geeksforgeeks.org/median-of-two-sorted-arrays/ 2.Consider column of ms excel the start with A,BZ,AA Now u r given column no u need to print its name *Ans : Same as number system problem with base 26* 3.Given 2 arrays.Imagine you are making bst from each array.u need to tell whether 2 bsts will be identical or not without actually constructing the tree. eg 1 2 3 1 3 2 will construct the same tree On Mon, Jun 3, 2013 at 10:52 PM, *$* gopi.komand...@gmail.com wrote: these are for which position? and experience? On Thu, May 2, 2013 at 9:27 PM, Guneesh gunees...@gmail.com wrote: Round 1: 1.Design a Data Structure supporting 3 queries a)push b)pop c) find minimum 2.Given post order of a BST find whether each node of the tree(except leaf) has only 1 child or not. eg5 \ 7 / 3 / 2 is correct as each node has only 1 child. Round 2: 1.Given a sorted array a and a sum k print all pairs of indexes i and j such that a[i]+a[j]=k. 2.Given a matrix that is row and column wise sorted give an algo for finding count of the total no of -ve nos. Round 3: 1.Given a matrix consisting of nos you can print the max length of sequence possible where in a sequence each consecutive nos have a diff of +1 or -1. eg 3 5 7 3 4 5 8 1 6 4 5 2 here sequence is 3 4 5
Re: [algogeeks] Amazon interview Questions
Round 1: 1.Design a Data Structure supporting 3 queries a)push b)pop c) find minimum Ans : Do it using Two Stacks . in first stack use it as normal stack. second stack use it to find minimun as the value inserted is greater than the top ignore it else push it. if pop operation happens and the value popped is equal to the top(s2) then pop(s2). time complexity push : O(1) , pop O(1) , find Minimum O(1) 2.Given post order of a BST find whether each node of the tree(except leaf) has only 1 child or not. eg5 \ 7 / 3 / 2 is correct as each node has only 1 child. Round 2: 1.Given a sorted array a and a sum k print all pairs of indexes i and j such that a[i]+a[j]=k. put one pointer at index 0 and 2nd at length(ar)-1. while (ij){ if(ar[i]+ar[j]==k) {printpairs; i++; j++;} else if(ar[i])+ar[j] k) i++; else if(ar[i])+ar[j] k) j--; } 2.Given a matrix that is row and column wise sorted give an algo for finding count of the total no of -ve nos. start from (0,n) move towards right if found +ve and increment count of positive in row. else move down . Round 3: 1.Given a matrix consisting of nos you can print the max length of sequence possible where in a sequence each consecutive nos have a diff of +1 or -1. eg 3 5 7 3 4 5 8 1 6 4 5 2 here sequence is 3 4 5 4 5 *you can do it using recursion * 2.Give a data structure that supports following queries a)insert b)delete c)ispresent d)print all elements *BST's ... , if insertionorder needs to be maintained then linked list;* 3.Given a infinite supply of n cylinders where each cylinder is specified by weight of 02,weight of n2,total weight , now u need some minimum quantity of o2 and n2 by selecting cylinders and your aim is make it so that u have min total weight. output the minimum total weight . Round 4: 1.Given 2 sorted arrays find there median .http://www.geeksforgeeks.org/median-of-two-sorted-arrays/ 2.Consider column of ms excel the start with A,BZ,AA Now u r given column no u need to print its name *Ans : Same as number system problem with base 26* 3.Given 2 arrays.Imagine you are making bst from each array.u need to tell whether 2 bsts will be identical or not without actually constructing the tree. eg 1 2 3 1 3 2 will construct the same tree On Mon, Jun 3, 2013 at 10:52 PM, *$* gopi.komand...@gmail.com wrote: these are for which position? and experience? On Thu, May 2, 2013 at 9:27 PM, Guneesh gunees...@gmail.com wrote: Round 1: 1.Design a Data Structure supporting 3 queries a)push b)pop c) find minimum 2.Given post order of a BST find whether each node of the tree(except leaf) has only 1 child or not. eg5 \ 7 / 3 / 2 is correct as each node has only 1 child. Round 2: 1.Given a sorted array a and a sum k print all pairs of indexes i and j such that a[i]+a[j]=k. 2.Given a matrix that is row and column wise sorted give an algo for finding count of the total no of -ve nos. Round 3: 1.Given a matrix consisting of nos you can print the max length of sequence possible where in a sequence each consecutive nos have a diff of +1 or -1. eg 3 5 7 3 4 5 8 1 6 4 5 2 here sequence is 3 4 5 4 5 2.Give a data structure that supports following queries a)insert b)delete c)ispresent d)print all elements 3.Given a infinite supply of n cylinders where each cylinder is specified by weight of 02,weight of n2,total weight , now u need some minimum quantity of o2 and n2 by selecting cylinders and your aim is make it so that u have min total weight. output the minimum total weight . Round 4: 1.Given 2 sorted arrays find there median. 2.Consider column of ms excel the start with A,BZ,AA Now u r given column no u need to print its name 3.Given 2 arrays.Imagine you are making bst from each array.u need to tell whether 2 bsts will be identical or not without actually constructing the tree. eg 1 2 3 1 3 2 will construct the same tree -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- Thx, --Gopi -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- Regards, Sourabh Kumar Jain +91-8971547841 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and
Re: [algogeeks] Amazon interview Questions
Can u clear Round3 --- Qstn-3. the language is not cleared On Wed, Jun 5, 2013 at 1:52 PM, sourabh jain wsour...@gmail.com wrote: Round 1: 1.Design a Data Structure supporting 3 queries a)push b)pop c) find minimum Ans : Do it using Two Stacks . in first stack use it as normal stack. second stack use it to find minimun as the value inserted is greater than the top ignore it else push it. if pop operation happens and the value popped is equal to the top(s2) then pop(s2). time complexity push : O(1) , pop O(1) , find Minimum O(1) 2.Given post order of a BST find whether each node of the tree(except leaf) has only 1 child or not. eg5 \ 7 / 3 / 2 is correct as each node has only 1 child. Round 2: 1.Given a sorted array a and a sum k print all pairs of indexes i and j such that a[i]+a[j]=k. put one pointer at index 0 and 2nd at length(ar)-1. while (ij){ if(ar[i]+ar[j]==k) {printpairs; i++; j++;} else if(ar[i])+ar[j] k) i++; else if(ar[i])+ar[j] k) j--; } 2.Given a matrix that is row and column wise sorted give an algo for finding count of the total no of -ve nos. start from (0,n) move towards right if found +ve and increment count of positive in row. else move down . Round 3: 1.Given a matrix consisting of nos you can print the max length of sequence possible where in a sequence each consecutive nos have a diff of +1 or -1. eg 3 5 7 3 4 5 8 1 6 4 5 2 here sequence is 3 4 5 4 5 *you can do it using recursion * 2.Give a data structure that supports following queries a)insert b)delete c)ispresent d)print all elements *BST's ... , if insertionorder needs to be maintained then linked list;* 3.Given a infinite supply of n cylinders where each cylinder is specified by weight of 02,weight of n2,total weight , now u need some minimum quantity of o2 and n2 by selecting cylinders and your aim is make it so that u have min total weight. output the minimum total weight . Round 4: 1.Given 2 sorted arrays find there median .http://www.geeksforgeeks.org/median-of-two-sorted-arrays/ 2.Consider column of ms excel the start with A,BZ,AA Now u r given column no u need to print its name *Ans : Same as number system problem with base 26* 3.Given 2 arrays.Imagine you are making bst from each array.u need to tell whether 2 bsts will be identical or not without actually constructing the tree. eg 1 2 3 1 3 2 will construct the same tree On Mon, Jun 3, 2013 at 10:52 PM, *$* gopi.komand...@gmail.com wrote: these are for which position? and experience? On Thu, May 2, 2013 at 9:27 PM, Guneesh gunees...@gmail.com wrote: Round 1: 1.Design a Data Structure supporting 3 queries a)push b)pop c) find minimum 2.Given post order of a BST find whether each node of the tree(except leaf) has only 1 child or not. eg5 \ 7 / 3 / 2 is correct as each node has only 1 child. Round 2: 1.Given a sorted array a and a sum k print all pairs of indexes i and j such that a[i]+a[j]=k. 2.Given a matrix that is row and column wise sorted give an algo for finding count of the total no of -ve nos. Round 3: 1.Given a matrix consisting of nos you can print the max length of sequence possible where in a sequence each consecutive nos have a diff of +1 or -1. eg 3 5 7 3 4 5 8 1 6 4 5 2 here sequence is 3 4 5 4 5 2.Give a data structure that supports following queries a)insert b)delete c)ispresent d)print all elements 3.Given a infinite supply of n cylinders where each cylinder is specified by weight of 02,weight of n2,total weight , now u need some minimum quantity of o2 and n2 by selecting cylinders and your aim is make it so that u have min total weight. output the minimum total weight . Round 4: 1.Given 2 sorted arrays find there median. 2.Consider column of ms excel the start with A,BZ,AA Now u r given column no u need to print its name 3.Given 2 arrays.Imagine you are making bst from each array.u need to tell whether 2 bsts will be identical or not without actually constructing the tree. eg 1 2 3 1 3 2 will construct the same tree -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- Thx, --Gopi -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to
Re: [algogeeks] Amazon interview Questions
Can any one give some points on Round 3 : 1st and 3rd question ? On Thu, May 2, 2013 at 9:27 PM, Guneesh gunees...@gmail.com wrote: Round 1: 1.Design a Data Structure supporting 3 queries a)push b)pop c) find minimum 2.Given post order of a BST find whether each node of the tree(except leaf) has only 1 child or not. eg5 \ 7 / 3 / 2 is correct as each node has only 1 child. Round 2: 1.Given a sorted array a and a sum k print all pairs of indexes i and j such that a[i]+a[j]=k. 2.Given a matrix that is row and column wise sorted give an algo for finding count of the total no of -ve nos. Round 3: 1.Given a matrix consisting of nos you can print the max length of sequence possible where in a sequence each consecutive nos have a diff of +1 or -1. eg 3 5 7 3 4 5 8 1 6 4 5 2 here sequence is 3 4 5 4 5 2.Give a data structure that supports following queries a)insert b)delete c)ispresent d)print all elements 3.Given a infinite supply of n cylinders where each cylinder is specified by weight of 02,weight of n2,total weight , now u need some minimum quantity of o2 and n2 by selecting cylinders and your aim is make it so that u have min total weight. output the minimum total weight . Round 4: 1.Given 2 sorted arrays find there median. 2.Consider column of ms excel the start with A,BZ,AA Now u r given column no u need to print its name 3.Given 2 arrays.Imagine you are making bst from each array.u need to tell whether 2 bsts will be identical or not without actually constructing the tree. eg 1 2 3 1 3 2 will construct the same tree -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Amazon interview Questions
these are for which position? and experience? On Thu, May 2, 2013 at 9:27 PM, Guneesh gunees...@gmail.com wrote: Round 1: 1.Design a Data Structure supporting 3 queries a)push b)pop c) find minimum 2.Given post order of a BST find whether each node of the tree(except leaf) has only 1 child or not. eg5 \ 7 / 3 / 2 is correct as each node has only 1 child. Round 2: 1.Given a sorted array a and a sum k print all pairs of indexes i and j such that a[i]+a[j]=k. 2.Given a matrix that is row and column wise sorted give an algo for finding count of the total no of -ve nos. Round 3: 1.Given a matrix consisting of nos you can print the max length of sequence possible where in a sequence each consecutive nos have a diff of +1 or -1. eg 3 5 7 3 4 5 8 1 6 4 5 2 here sequence is 3 4 5 4 5 2.Give a data structure that supports following queries a)insert b)delete c)ispresent d)print all elements 3.Given a infinite supply of n cylinders where each cylinder is specified by weight of 02,weight of n2,total weight , now u need some minimum quantity of o2 and n2 by selecting cylinders and your aim is make it so that u have min total weight. output the minimum total weight . Round 4: 1.Given 2 sorted arrays find there median. 2.Consider column of ms excel the start with A,BZ,AA Now u r given column no u need to print its name 3.Given 2 arrays.Imagine you are making bst from each array.u need to tell whether 2 bsts will be identical or not without actually constructing the tree. eg 1 2 3 1 3 2 will construct the same tree -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- Thx, --Gopi -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] amazon interview questions
can be done with O(n^2) time complexity.. can it be done with O(n) complexity ??? On 6/3/12, utsav sharma utsav.sharm...@gmail.com wrote: given a string tell wether it is valid or not. string is valid if there is no substring which have the same substring following it. these strings are not valid:- stringstring,geek123123rt, abcadabcad,strngstingstrngsting -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.