[algogeeks] amazon interview
Hi all, I've interviews for SDE-1 in amazon bangalore this weekend. Can any one tell me the recent questions they are focusing on ? or if anyone have the recent experience with them please share it. Thanks -- 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
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.
[algogeeks] Amazon interview Questions
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.
[algogeeks] Amazon interview question
A = {5, 3, 8, 9, 16} After one iteration A = {3-5,8-3,9-8,16-9}={-2,5,1,7} After second iteration A = {5-(-2),1-5,7-1} sum =7+(-4)+6=9 Given an array, return sum after n iterations my sol/ void abc(int arr[],n) { for(i=0;in;i++) arr[i]=arr[i+1]-arr[i]; abc(arr,n-1); } I wana ask that the complexity is o(n) or o(n)2..as loop is executed n times..say n is 10...so fxn is called 10 timesi.e 10 n..and ignoring n it comes out to be...n..but if we implemeted with 2 loops then complexity is n2 ...and both sol are taking same no of iterations...please tell whether complexity is n or n2 for above codeif it is n2 then how??? -- 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.
Re: [algogeeks] Amazon interview question
Your solution fails for a number of reasons: 1. If your array is size 1 or 0. 2. The last digit in the array is found by arr[n-1] - [n-2] not arr[i+1]-arr[i] 3. Recursion here creates unnecessary overheard How many times are you calling abc? Draw the recursion tree. On Tue, Apr 9, 2013 at 11:29 AM, rahul sharma rahul23111...@gmail.comwrote: A = {5, 3, 8, 9, 16} After one iteration A = {3-5,8-3,9-8,16-9}={-2,5,1,7} After second iteration A = {5-(-2),1-5,7-1} sum =7+(-4)+6=9 Given an array, return sum after n iterations my sol/ void abc(int arr[],n) { for(i=0;in;i++) arr[i]=arr[i+1]-arr[i]; abc(arr,n-1); } I wana ask that the complexity is o(n) or o(n)2..as loop is executed n times..say n is 10...so fxn is called 10 timesi.e 10 n..and ignoring n it comes out to be...n..but if we implemeted with 2 loops then complexity is n2 ...and both sol are taking same no of iterations...please tell whether complexity is n or n2 for above codeif it is n2 then how??? -- 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. For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Amazon interview Question
@Rashmi: I did not get your approach. I do not get emails from the group just in case you have posted a solution :( What do you mean by keeping a count? Also, are you using a hashmap? If yes, whats ur K,V? #Pralay On Tue, Feb 12, 2013 at 10:00 AM, rashmi i rash...@gmail.com wrote: Hey Pralay, Sorry, if I have missed any point.Why would we need to map the frequencies when the second problem can be solved by simply keeping a count and comparing the index values that have been already mapped. On Fri, Feb 8, 2013 at 11:19 AM, sourabh jain wsour...@gmail.com wrote: One solution for the 2nd question can be LinkedHashMap (linked list + hashmap) . Store the integer in linked list in the order of occurrence in stream and make an entry in hashmap on first occurence. Delete the integer entry from linked list on 2nd occurence and replace the reference with some special value so for 3rd time no need to touch the linked list. while printing the result print first k integers from linked list. On Fri, Feb 8, 2013 at 9:46 AM, bharat b bagana.bharatku...@gmail.comwrote: @sourabh : how do u find whether the element in stream gets repeated in heap.-- O(n) time...totally its O(nk) algo .. If we maintain max-heap with BST property on index, then it would be O(nlogk). On Wed, Feb 6, 2013 at 12:25 PM, sourabh jain wsour...@gmail.comwrote: for 2nd question you can make a heap with their index as a factor to heapify them. whenever a integer in stream gets repeated you just nead to remove it from heap and heapify it. On Wed, Feb 6, 2013 at 10:00 AM, navneet singh gaur navneet.singhg...@gmail.com wrote: nice algo ankit, so it will be nlogn using O (n) space only. What abt 2nd Q., which have a big online stream. On Mon, Feb 4, 2013 at 9:30 PM, kumar ankit k.anki...@gmail.com wrote: For 1: i think you can use sorting, sort the array and keep the indices of the numbers in the sorted list. Now traverse the sorted list and in the sorted list you need to find the unique number with the minimum index which is easy to find. Eg: Array:5 3 1 2 4 1 4 Indices: 0 1 2 3 4 5 6 After sorting : Array:1 1 2 3 4 4 5 Indices: 2 5 3 1 4 6 1 Now you can see the unique number with lowest index is 3(index=1). So , you have your answer. On Mon, Feb 4, 2013 at 3:45 PM, navneet singh gaur navneet.singhg...@gmail.com wrote: 1. Given a array,find a first unique integer. 2. Integers are coming as online stream,have to find a kth unique integer till now. For 1. Even we cannot use sorting for solving this as if we sort it than our first number which is non-repetitive changes. The best I am able to do is nlogn using a space of O( n ). For 2. No idea -- 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. -- Kumar Ankit Senior Undergraduate Department of Computer Engineering Institute of Technology Banaras Hindu University Varanasi Ph: +91 9473629892 -- 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. -- navneet singh gaur -- 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. -- 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 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. For more options, visit https://groups.google.com/groups/opt_out. -- 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 stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- R@$!-! DoN'T LimIt Ur cHaLlEngeS, ChAlLenGe uR LImItS. -- You received this
Re: [algogeeks] Amazon interview Question
Guys, Why can't we simply use a hashset for both the questions. hash the arr[i] and the frequencies in the hash map in the first pass. Then iterate over the array to find the first arr[i] whose freq is 1 in the hash map. For second part, keep a count and find the kth element in the array whose freq in the hashmap is 1. *Pralay MS-Comp Sci* *Univ of California* On Thu, Feb 7, 2013 at 8:16 PM, bharat b bagana.bharatku...@gmail.comwrote: @sourabh : how do u find whether the element in stream gets repeated in heap.-- O(n) time...totally its O(nk) algo .. If we maintain max-heap with BST property on index, then it would be O(nlogk). On Wed, Feb 6, 2013 at 12:25 PM, sourabh jain wsour...@gmail.com wrote: for 2nd question you can make a heap with their index as a factor to heapify them. whenever a integer in stream gets repeated you just nead to remove it from heap and heapify it. On Wed, Feb 6, 2013 at 10:00 AM, navneet singh gaur navneet.singhg...@gmail.com wrote: nice algo ankit, so it will be nlogn using O (n) space only. What abt 2nd Q., which have a big online stream. On Mon, Feb 4, 2013 at 9:30 PM, kumar ankit k.anki...@gmail.com wrote: For 1: i think you can use sorting, sort the array and keep the indices of the numbers in the sorted list. Now traverse the sorted list and in the sorted list you need to find the unique number with the minimum index which is easy to find. Eg: Array:5 3 1 2 4 1 4 Indices: 0 1 2 3 4 5 6 After sorting : Array:1 1 2 3 4 4 5 Indices: 2 5 3 1 4 6 1 Now you can see the unique number with lowest index is 3(index=1). So , you have your answer. On Mon, Feb 4, 2013 at 3:45 PM, navneet singh gaur navneet.singhg...@gmail.com wrote: 1. Given a array,find a first unique integer. 2. Integers are coming as online stream,have to find a kth unique integer till now. For 1. Even we cannot use sorting for solving this as if we sort it than our first number which is non-repetitive changes. The best I am able to do is nlogn using a space of O( n ). For 2. No idea -- 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. -- Kumar Ankit Senior Undergraduate Department of Computer Engineering Institute of Technology Banaras Hindu University Varanasi Ph: +91 9473629892 -- 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. -- navneet singh gaur -- 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. -- 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 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. 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. For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Amazon interview Question
first problem can be solved using a fixed sized array if we know the range of numbers or a hash table with an appropriate hash function and it is O(N) for time and space as some solutions above already mentioned this. for the second problem, I don't think heap is the right data structure which is only good for getting min(max) element in logN time. A possible solution would be to use a combination of linked list and a hash table. For every incoming number num(i) of the stream, check if the number exists in the hash table and: 1. if it does not exist, add an entry in hash table and insert a node in linked list. HashTbl row is key,val pair of num,Node* where Node* points to the corresponding node entry in the linked list. linked list node should contain pointer(index) to the corresponding HashTblRow. It is like hash table entry pointing to corresponding node in the list and list node pointing to hash table entry.O(1) adding to hash table and list. 2. if it does exist, delete the node from hash table and find the list node address, and delete it from the list. O(1) operation To find the k-th unique number: just walk the list, O(k) On Thu, Feb 7, 2013 at 11:16 PM, bharat b bagana.bharatku...@gmail.com wrote: @sourabh : how do u find whether the element in stream gets repeated in heap.-- O(n) time...totally its O(nk) algo .. If we maintain max-heap with BST property on index, then it would be O(nlogk). On Wed, Feb 6, 2013 at 12:25 PM, sourabh jain wsour...@gmail.com wrote: for 2nd question you can make a heap with their index as a factor to heapify them. whenever a integer in stream gets repeated you just nead to remove it from heap and heapify it. On Wed, Feb 6, 2013 at 10:00 AM, navneet singh gaur navneet.singhg...@gmail.com wrote: nice algo ankit, so it will be nlogn using O (n) space only. What abt 2nd Q., which have a big online stream. On Mon, Feb 4, 2013 at 9:30 PM, kumar ankit k.anki...@gmail.com wrote: For 1: i think you can use sorting, sort the array and keep the indices of the numbers in the sorted list. Now traverse the sorted list and in the sorted list you need to find the unique number with the minimum index which is easy to find. Eg: Array:5 3 1 2 4 1 4 Indices: 0 1 2 3 4 5 6 After sorting : Array:1 1 2 3 4 4 5 Indices: 2 5 3 1 4 6 1 Now you can see the unique number with lowest index is 3(index=1). So , you have your answer. On Mon, Feb 4, 2013 at 3:45 PM, navneet singh gaur navneet.singhg...@gmail.com wrote: 1. Given a array,find a first unique integer. 2. Integers are coming as online stream,have to find a kth unique integer till now. For 1. Even we cannot use sorting for solving this as if we sort it than our first number which is non-repetitive changes. The best I am able to do is nlogn using a space of O( n ). For 2. No idea -- 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. -- Kumar Ankit Senior Undergraduate Department of Computer Engineering Institute of Technology Banaras Hindu University Varanasi Ph: +91 9473629892 -- 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. -- navneet singh gaur -- 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. -- 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 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. 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. For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Amazon interview Question
One solution for the 2nd question can be LinkedHashMap (linked list + hashmap) . Store the integer in linked list in the order of occurrence in stream and make an entry in hashmap on first occurence. Delete the integer entry from linked list on 2nd occurence and replace the reference with some special value so for 3rd time no need to touch the linked list. while printing the result print first k integers from linked list. On Fri, Feb 8, 2013 at 9:46 AM, bharat b bagana.bharatku...@gmail.comwrote: @sourabh : how do u find whether the element in stream gets repeated in heap.-- O(n) time...totally its O(nk) algo .. If we maintain max-heap with BST property on index, then it would be O(nlogk). On Wed, Feb 6, 2013 at 12:25 PM, sourabh jain wsour...@gmail.com wrote: for 2nd question you can make a heap with their index as a factor to heapify them. whenever a integer in stream gets repeated you just nead to remove it from heap and heapify it. On Wed, Feb 6, 2013 at 10:00 AM, navneet singh gaur navneet.singhg...@gmail.com wrote: nice algo ankit, so it will be nlogn using O (n) space only. What abt 2nd Q., which have a big online stream. On Mon, Feb 4, 2013 at 9:30 PM, kumar ankit k.anki...@gmail.com wrote: For 1: i think you can use sorting, sort the array and keep the indices of the numbers in the sorted list. Now traverse the sorted list and in the sorted list you need to find the unique number with the minimum index which is easy to find. Eg: Array:5 3 1 2 4 1 4 Indices: 0 1 2 3 4 5 6 After sorting : Array:1 1 2 3 4 4 5 Indices: 2 5 3 1 4 6 1 Now you can see the unique number with lowest index is 3(index=1). So , you have your answer. On Mon, Feb 4, 2013 at 3:45 PM, navneet singh gaur navneet.singhg...@gmail.com wrote: 1. Given a array,find a first unique integer. 2. Integers are coming as online stream,have to find a kth unique integer till now. For 1. Even we cannot use sorting for solving this as if we sort it than our first number which is non-repetitive changes. The best I am able to do is nlogn using a space of O( n ). For 2. No idea -- 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. -- Kumar Ankit Senior Undergraduate Department of Computer Engineering Institute of Technology Banaras Hindu University Varanasi Ph: +91 9473629892 -- 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. -- navneet singh gaur -- 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. -- 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 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. For more options, visit https://groups.google.com/groups/opt_out. -- 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 stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
[algogeeks] Amazon Interview Questions
Hi All, I need ur help in solving few questions. Would you please help me out *BY GIVING THE ALGORITHM AND THE LOGIC BEHIND IT and it's DEEP EXPLANATION IF POSSIBLE?* * * *a. Kadane’s Algo.* * * *b. Linked-list intersection point.* * [A tree with only parent pointer, how to find LCA?] * * * * c. Design a stack which can perform findMax in O(1). * * * *d. Set of stocks for each day have been given. Need to find the days on which I buy and sell share to earn max profit, alongwith finding the max profit.* * e. Find top k searched elements from a continuous stream of data. * * * *f. Given a linked-list and 2 integers k m. Reverse the linked-list till k elements and then traverse till m elements and repeat.* *Write production quality code.* * * *g. An array of elements have been given. Find for each element, first max element to its right.* * * *h. Boundary traversal of a tree. Write the code.* Please help me out... Thanks in advance... Thanks Regards, Pratik Mayur Mehta. -- 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.
Re: [algogeeks] Amazon interview Question
Hey Pralay, Sorry, if I have missed any point.Why would we need to map the frequencies when the second problem can be solved by simply keeping a count and comparing the index values that have been already mapped. On Fri, Feb 8, 2013 at 11:19 AM, sourabh jain wsour...@gmail.com wrote: One solution for the 2nd question can be LinkedHashMap (linked list + hashmap) . Store the integer in linked list in the order of occurrence in stream and make an entry in hashmap on first occurence. Delete the integer entry from linked list on 2nd occurence and replace the reference with some special value so for 3rd time no need to touch the linked list. while printing the result print first k integers from linked list. On Fri, Feb 8, 2013 at 9:46 AM, bharat b bagana.bharatku...@gmail.comwrote: @sourabh : how do u find whether the element in stream gets repeated in heap.-- O(n) time...totally its O(nk) algo .. If we maintain max-heap with BST property on index, then it would be O(nlogk). On Wed, Feb 6, 2013 at 12:25 PM, sourabh jain wsour...@gmail.com wrote: for 2nd question you can make a heap with their index as a factor to heapify them. whenever a integer in stream gets repeated you just nead to remove it from heap and heapify it. On Wed, Feb 6, 2013 at 10:00 AM, navneet singh gaur navneet.singhg...@gmail.com wrote: nice algo ankit, so it will be nlogn using O (n) space only. What abt 2nd Q., which have a big online stream. On Mon, Feb 4, 2013 at 9:30 PM, kumar ankit k.anki...@gmail.com wrote: For 1: i think you can use sorting, sort the array and keep the indices of the numbers in the sorted list. Now traverse the sorted list and in the sorted list you need to find the unique number with the minimum index which is easy to find. Eg: Array:5 3 1 2 4 1 4 Indices: 0 1 2 3 4 5 6 After sorting : Array:1 1 2 3 4 4 5 Indices: 2 5 3 1 4 6 1 Now you can see the unique number with lowest index is 3(index=1). So , you have your answer. On Mon, Feb 4, 2013 at 3:45 PM, navneet singh gaur navneet.singhg...@gmail.com wrote: 1. Given a array,find a first unique integer. 2. Integers are coming as online stream,have to find a kth unique integer till now. For 1. Even we cannot use sorting for solving this as if we sort it than our first number which is non-repetitive changes. The best I am able to do is nlogn using a space of O( n ). For 2. No idea -- 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. -- Kumar Ankit Senior Undergraduate Department of Computer Engineering Institute of Technology Banaras Hindu University Varanasi Ph: +91 9473629892 -- 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. -- navneet singh gaur -- 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. -- 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 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. For more options, visit https://groups.google.com/groups/opt_out. -- 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 stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- R@$!-! DoN'T LimIt Ur cHaLlEngeS, ChAlLenGe uR LImItS. -- 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.
Re: [algogeeks] Amazon interview Question
was trying to do something clever. Knew it couldnt be that simple. Missed some cases. I still feel with some hacks and handling some special cases this approach would work. But considering it still takes O(n) time I am not thrilled. I am still ok with my algo taking Space for time. But probably not the other way unless there are some special constraints. Hashtable it is. Srikar On Thursday, February 7, 2013 12:35:21 PM UTC+5:30, bharat wrote: @srikar : approach2 is wrong. ex: [1, 5, 7, 66, 7, 1, 77] first window [1,5,7] all are unique.oops On Wed, Feb 6, 2013 at 11:31 PM, Srikar srika...@gmail.com javascript:wrote: *APPROACH 1:* use a hashtable for both the questions ? Insert the integers as they are given in the array into a hashtable. The structure I am thinking is key (the integer) - [index]. Once all elements are inserted. Run through the hashtable and select the one which has len(value) == 1 and is least, since we want the first unique integer. for the second Q, its a more general Q of the first one. In first k=1. space: 2O(n) time: 2O(n) *APPROACH2: * When we say unique, we will have a pattern. Eg: [5, 5, 66, 66, 7, 1, 1, 77]. In this lets have moving window of 3. first consider (5,5,66). we can easily estab. that there is duplicate here. So move the window by 1 element so we get (5,66,66). Same here. move to next (66,66,7). Again dups here. next (66,7,1). No dups here! take the middle element as this has to be the first unique in the set. The left element belongs to the dup so could 1. Hence 7 is the first unique element. space: O(1) time: O(n) For seond Q I still think hashtable is best. As the numbers are streamed, keep inserting. Srikar On Wed, Feb 6, 2013 at 10:00 AM, navneet singh gaur navneet@gmail.com javascript: wrote: nice algo ankit, so it will be nlogn using O (n) space only. What abt 2nd Q., which have a big online stream. On Mon, Feb 4, 2013 at 9:30 PM, kumar ankit k.an...@gmail.comjavascript: wrote: For 1: i think you can use sorting, sort the array and keep the indices of the numbers in the sorted list. Now traverse the sorted list and in the sorted list you need to find the unique number with the minimum index which is easy to find. Eg: Array:5 3 1 2 4 1 4 Indices: 0 1 2 3 4 5 6 After sorting : Array:1 1 2 3 4 4 5 Indices: 2 5 3 1 4 6 1 Now you can see the unique number with lowest index is 3(index=1). So , you have your answer. On Mon, Feb 4, 2013 at 3:45 PM, navneet singh gaur navneet@gmail.com javascript: wrote: 1. Given a array,find a first unique integer. 2. Integers are coming as online stream,have to find a kth unique integer till now. For 1. Even we cannot use sorting for solving this as if we sort it than our first number which is non-repetitive changes. The best I am able to do is nlogn using a space of O( n ). For 2. No idea -- 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+...@googlegroups.com javascript:. For more options, visit https://groups.google.com/groups/opt_out. -- Kumar Ankit Senior Undergraduate Department of Computer Engineering Institute of Technology Banaras Hindu University Varanasi Ph: +91 9473629892 -- 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+...@googlegroups.com javascript:. For more options, visit https://groups.google.com/groups/opt_out. -- navneet singh gaur -- 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+...@googlegroups.com javascript:. 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+...@googlegroups.com javascript:. 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. For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Amazon interview Question
I guess the part 1 can be solved in O(n) time and space both. Here is my approach. Assume: Array given is arr[] = {2,3,1,2,3,2,4,1,5,6} 1. Given an array, scan thru it, element by element and hash it on a hashmap with key as the arr[i] as the key and i+1 as the index. 2. There would be two cases a) arr[i] is already there in the hash map, if so, check if the hashmap.get(arr[i]) is a negative or not. If it is negative , do nothing. If its is not negative, negate it. b) arr[i] is a new element, in such a case, hash key as arr[i] and i+1 as the value. 3. Scan thru the value set, the key corresponding to minimum of positive values is the answer. Example. For {2,3,1,2,3,2,4,1, 5,6} 2 = not seen, hash 2,1 (arr[i], i+1) 3 = not seen, hash 3, 2 1 = not seen, hash 1,3 2 = seen - is the value corresponding to key 2 negative = No. So negate it- hash entry now becomes 2,-1 3 = similar to above - Hash entry is 3,-2 2 = seen, is the value negative = yes, do nothing 4 = not seen, hash 4,8 1 = seen, is the value corresponding to key 1 -ve? No, negate it, hashentry = 1,-3 5 = not seen, hash 5,10 6= not seen, hash 6,11 Hasmap ready. Whats the value set (the values only) ? -1,-2,-3,8,10,11 Whats the *least minimum of positive values*? 8 Whats the key corresponding to value 8? Its 4. *4 is the first unique number!* Please let me know if you need the code, shall send you ova :) Cheers, *Pralay* *MS,Comp Sci, * *University of California, Irvine* On Tue, Feb 5, 2013 at 8:30 PM, navneet singh gaur navneet.singhg...@gmail.com wrote: nice algo ankit, so it will be nlogn using O (n) space only. What abt 2nd Q., which have a big online stream. On Mon, Feb 4, 2013 at 9:30 PM, kumar ankit k.anki...@gmail.com wrote: For 1: i think you can use sorting, sort the array and keep the indices of the numbers in the sorted list. Now traverse the sorted list and in the sorted list you need to find the unique number with the minimum index which is easy to find. Eg: Array:5 3 1 2 4 1 4 Indices: 0 1 2 3 4 5 6 After sorting : Array:1 1 2 3 4 4 5 Indices: 2 5 3 1 4 6 1 Now you can see the unique number with lowest index is 3(index=1). So , you have your answer. On Mon, Feb 4, 2013 at 3:45 PM, navneet singh gaur navneet.singhg...@gmail.com wrote: 1. Given a array,find a first unique integer. 2. Integers are coming as online stream,have to find a kth unique integer till now. For 1. Even we cannot use sorting for solving this as if we sort it than our first number which is non-repetitive changes. The best I am able to do is nlogn using a space of O( n ). For 2. No idea -- 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. -- Kumar Ankit Senior Undergraduate Department of Computer Engineering Institute of Technology Banaras Hindu University Varanasi Ph: +91 9473629892 -- 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. -- navneet singh gaur -- 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. For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Amazon interview Question
Navneet, For 2nd problem, i need a clarification, whether the Kth number is wrt mathematical ordering of numbers or the kth number is wrt to the order in which the number are input ? On Wed, Feb 6, 2013 at 10:00 AM, navneet singh gaur navneet.singhg...@gmail.com wrote: nice algo ankit, so it will be nlogn using O (n) space only. What abt 2nd Q., which have a big online stream. On Mon, Feb 4, 2013 at 9:30 PM, kumar ankit k.anki...@gmail.com wrote: For 1: i think you can use sorting, sort the array and keep the indices of the numbers in the sorted list. Now traverse the sorted list and in the sorted list you need to find the unique number with the minimum index which is easy to find. Eg: Array:5 3 1 2 4 1 4 Indices: 0 1 2 3 4 5 6 After sorting : Array:1 1 2 3 4 4 5 Indices: 2 5 3 1 4 6 1 Now you can see the unique number with lowest index is 3(index=1). So , you have your answer. On Mon, Feb 4, 2013 at 3:45 PM, navneet singh gaur navneet.singhg...@gmail.com wrote: 1. Given a array,find a first unique integer. 2. Integers are coming as online stream,have to find a kth unique integer till now. For 1. Even we cannot use sorting for solving this as if we sort it than our first number which is non-repetitive changes. The best I am able to do is nlogn using a space of O( n ). For 2. No idea -- 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. -- Kumar Ankit Senior Undergraduate Department of Computer Engineering Institute of Technology Banaras Hindu University Varanasi Ph: +91 9473629892 -- 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. -- navneet singh gaur -- 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. -- Kumar Ankit Senior Undergraduate Department of Computer Engineering Institute of Technology Banaras Hindu University Varanasi Ph: +91 9473629892 -- 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.
Re: [algogeeks] Amazon interview Question
what would happen of the input is like this : 5, 5, 66, 66, 7, 1, 1, 77,7 i think in this case the moment window reaches to point (66,7,1) it will take 7 as unique number but that too window will not move any futhur , but 7 is not unique . Please comment if i misunderstood ur explanation . On Wed, Feb 6, 2013 at 11:31 PM, Srikar srikar2...@gmail.com wrote: *APPROACH 1:* use a hashtable for both the questions ? Insert the integers as they are given in the array into a hashtable. The structure I am thinking is key (the integer) - [index]. Once all elements are inserted. Run through the hashtable and select the one which has len(value) == 1 and is least, since we want the first unique integer. for the second Q, its a more general Q of the first one. In first k=1. space: 2O(n) time: 2O(n) *APPROACH2: * When we say unique, we will have a pattern. Eg: [5, 5, 66, 66, 7, 1, 1, 77]. In this lets have moving window of 3. first consider (5,5,66). we can easily estab. that there is duplicate here. So move the window by 1 element so we get (5,66,66). Same here. move to next (66,66,7). Again dups here. next (66,7,1). No dups here! take the middle element as this has to be the first unique in the set. The left element belongs to the dup so could 1. Hence 7 is the first unique element. space: O(1) time: O(n) For seond Q I still think hashtable is best. As the numbers are streamed, keep inserting. Srikar On Wed, Feb 6, 2013 at 10:00 AM, navneet singh gaur navneet.singhg...@gmail.com wrote: nice algo ankit, so it will be nlogn using O (n) space only. What abt 2nd Q., which have a big online stream. On Mon, Feb 4, 2013 at 9:30 PM, kumar ankit k.anki...@gmail.com wrote: For 1: i think you can use sorting, sort the array and keep the indices of the numbers in the sorted list. Now traverse the sorted list and in the sorted list you need to find the unique number with the minimum index which is easy to find. Eg: Array:5 3 1 2 4 1 4 Indices: 0 1 2 3 4 5 6 After sorting : Array:1 1 2 3 4 4 5 Indices: 2 5 3 1 4 6 1 Now you can see the unique number with lowest index is 3(index=1). So , you have your answer. On Mon, Feb 4, 2013 at 3:45 PM, navneet singh gaur navneet.singhg...@gmail.com wrote: 1. Given a array,find a first unique integer. 2. Integers are coming as online stream,have to find a kth unique integer till now. For 1. Even we cannot use sorting for solving this as if we sort it than our first number which is non-repetitive changes. The best I am able to do is nlogn using a space of O( n ). For 2. No idea -- 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. -- Kumar Ankit Senior Undergraduate Department of Computer Engineering Institute of Technology Banaras Hindu University Varanasi Ph: +91 9473629892 -- 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. -- navneet singh gaur -- 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. 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. For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Amazon interview Question
Also, for the part two of the question, you can simply go in for the *kth largest positive index *in the same hashmap (described earlier for part 1). That solves the part two of the problem :) Hth, *Pralay Biswas* *MS,Comp Sci, * *University of California, Irvine* On Tue, Feb 5, 2013 at 8:46 PM, Pralay Biswas pralaybiswas2...@gmail.comwrote: I guess the part 1 can be solved in O(n) time and space both. Here is my approach. Assume: Array given is arr[] = {2,3,1,2,3,2,4,1,5,6} 1. Given an array, scan thru it, element by element and hash it on a hashmap with key as the arr[i] as the key and i+1 as the index. 2. There would be two cases a) arr[i] is already there in the hash map, if so, check if the hashmap.get(arr[i]) is a negative or not. If it is negative , do nothing. If its is not negative, negate it. b) arr[i] is a new element, in such a case, hash key as arr[i] and i+1 as the value. 3. Scan thru the value set, the key corresponding to minimum of positive values is the answer. Example. For {2,3,1,2,3,2,4,1, 5,6} 2 = not seen, hash 2,1 (arr[i], i+1) 3 = not seen, hash 3, 2 1 = not seen, hash 1,3 2 = seen - is the value corresponding to key 2 negative = No. So negate it- hash entry now becomes 2,-1 3 = similar to above - Hash entry is 3,-2 2 = seen, is the value negative = yes, do nothing 4 = not seen, hash 4,8 1 = seen, is the value corresponding to key 1 -ve? No, negate it, hashentry = 1,-3 5 = not seen, hash 5,10 6= not seen, hash 6,11 Hasmap ready. Whats the value set (the values only) ? -1,-2,-3,8,10,11 Whats the *least minimum of positive values*? 8 Whats the key corresponding to value 8? Its 4. *4 is the first unique number!* Please let me know if you need the code, shall send you ova :) Cheers, *Pralay* *MS,Comp Sci, * *University of California, Irvine* On Tue, Feb 5, 2013 at 8:30 PM, navneet singh gaur navneet.singhg...@gmail.com wrote: nice algo ankit, so it will be nlogn using O (n) space only. What abt 2nd Q., which have a big online stream. On Mon, Feb 4, 2013 at 9:30 PM, kumar ankit k.anki...@gmail.com wrote: For 1: i think you can use sorting, sort the array and keep the indices of the numbers in the sorted list. Now traverse the sorted list and in the sorted list you need to find the unique number with the minimum index which is easy to find. Eg: Array:5 3 1 2 4 1 4 Indices: 0 1 2 3 4 5 6 After sorting : Array:1 1 2 3 4 4 5 Indices: 2 5 3 1 4 6 1 Now you can see the unique number with lowest index is 3(index=1). So , you have your answer. On Mon, Feb 4, 2013 at 3:45 PM, navneet singh gaur navneet.singhg...@gmail.com wrote: 1. Given a array,find a first unique integer. 2. Integers are coming as online stream,have to find a kth unique integer till now. For 1. Even we cannot use sorting for solving this as if we sort it than our first number which is non-repetitive changes. The best I am able to do is nlogn using a space of O( n ). For 2. No idea -- 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. -- Kumar Ankit Senior Undergraduate Department of Computer Engineering Institute of Technology Banaras Hindu University Varanasi Ph: +91 9473629892 -- 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. -- navneet singh gaur -- 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. For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Amazon interview Question
for 2nd question you can make a heap with their index as a factor to heapify them. whenever a integer in stream gets repeated you just nead to remove it from heap and heapify it. On Wed, Feb 6, 2013 at 10:00 AM, navneet singh gaur navneet.singhg...@gmail.com wrote: nice algo ankit, so it will be nlogn using O (n) space only. What abt 2nd Q., which have a big online stream. On Mon, Feb 4, 2013 at 9:30 PM, kumar ankit k.anki...@gmail.com wrote: For 1: i think you can use sorting, sort the array and keep the indices of the numbers in the sorted list. Now traverse the sorted list and in the sorted list you need to find the unique number with the minimum index which is easy to find. Eg: Array:5 3 1 2 4 1 4 Indices: 0 1 2 3 4 5 6 After sorting : Array:1 1 2 3 4 4 5 Indices: 2 5 3 1 4 6 1 Now you can see the unique number with lowest index is 3(index=1). So , you have your answer. On Mon, Feb 4, 2013 at 3:45 PM, navneet singh gaur navneet.singhg...@gmail.com wrote: 1. Given a array,find a first unique integer. 2. Integers are coming as online stream,have to find a kth unique integer till now. For 1. Even we cannot use sorting for solving this as if we sort it than our first number which is non-repetitive changes. The best I am able to do is nlogn using a space of O( n ). For 2. No idea -- 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. -- Kumar Ankit Senior Undergraduate Department of Computer Engineering Institute of Technology Banaras Hindu University Varanasi Ph: +91 9473629892 -- 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. -- navneet singh gaur -- 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. -- 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 stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Amazon interview Question
@sourabh : how do u find whether the element in stream gets repeated in heap.-- O(n) time...totally its O(nk) algo .. If we maintain max-heap with BST property on index, then it would be O(nlogk). On Wed, Feb 6, 2013 at 12:25 PM, sourabh jain wsour...@gmail.com wrote: for 2nd question you can make a heap with their index as a factor to heapify them. whenever a integer in stream gets repeated you just nead to remove it from heap and heapify it. On Wed, Feb 6, 2013 at 10:00 AM, navneet singh gaur navneet.singhg...@gmail.com wrote: nice algo ankit, so it will be nlogn using O (n) space only. What abt 2nd Q., which have a big online stream. On Mon, Feb 4, 2013 at 9:30 PM, kumar ankit k.anki...@gmail.com wrote: For 1: i think you can use sorting, sort the array and keep the indices of the numbers in the sorted list. Now traverse the sorted list and in the sorted list you need to find the unique number with the minimum index which is easy to find. Eg: Array:5 3 1 2 4 1 4 Indices: 0 1 2 3 4 5 6 After sorting : Array:1 1 2 3 4 4 5 Indices: 2 5 3 1 4 6 1 Now you can see the unique number with lowest index is 3(index=1). So , you have your answer. On Mon, Feb 4, 2013 at 3:45 PM, navneet singh gaur navneet.singhg...@gmail.com wrote: 1. Given a array,find a first unique integer. 2. Integers are coming as online stream,have to find a kth unique integer till now. For 1. Even we cannot use sorting for solving this as if we sort it than our first number which is non-repetitive changes. The best I am able to do is nlogn using a space of O( n ). For 2. No idea -- 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. -- Kumar Ankit Senior Undergraduate Department of Computer Engineering Institute of Technology Banaras Hindu University Varanasi Ph: +91 9473629892 -- 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. -- navneet singh gaur -- 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. -- 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 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. For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Amazon interview Question
*APPROACH 1:* use a hashtable for both the questions ? Insert the integers as they are given in the array into a hashtable. The structure I am thinking is key (the integer) - [index]. Once all elements are inserted. Run through the hashtable and select the one which has len(value) == 1 and is least, since we want the first unique integer. for the second Q, its a more general Q of the first one. In first k=1. space: 2O(n) time: 2O(n) *APPROACH2: * When we say unique, we will have a pattern. Eg: [5, 5, 66, 66, 7, 1, 1, 77]. In this lets have moving window of 3. first consider (5,5,66). we can easily estab. that there is duplicate here. So move the window by 1 element so we get (5,66,66). Same here. move to next (66,66,7). Again dups here. next (66,7,1). No dups here! take the middle element as this has to be the first unique in the set. The left element belongs to the dup so could 1. Hence 7 is the first unique element. space: O(1) time: O(n) For seond Q I still think hashtable is best. As the numbers are streamed, keep inserting. Srikar On Wed, Feb 6, 2013 at 10:00 AM, navneet singh gaur navneet.singhg...@gmail.com wrote: nice algo ankit, so it will be nlogn using O (n) space only. What abt 2nd Q., which have a big online stream. On Mon, Feb 4, 2013 at 9:30 PM, kumar ankit k.anki...@gmail.com wrote: For 1: i think you can use sorting, sort the array and keep the indices of the numbers in the sorted list. Now traverse the sorted list and in the sorted list you need to find the unique number with the minimum index which is easy to find. Eg: Array:5 3 1 2 4 1 4 Indices: 0 1 2 3 4 5 6 After sorting : Array:1 1 2 3 4 4 5 Indices: 2 5 3 1 4 6 1 Now you can see the unique number with lowest index is 3(index=1). So , you have your answer. On Mon, Feb 4, 2013 at 3:45 PM, navneet singh gaur navneet.singhg...@gmail.com wrote: 1. Given a array,find a first unique integer. 2. Integers are coming as online stream,have to find a kth unique integer till now. For 1. Even we cannot use sorting for solving this as if we sort it than our first number which is non-repetitive changes. The best I am able to do is nlogn using a space of O( n ). For 2. No idea -- 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. -- Kumar Ankit Senior Undergraduate Department of Computer Engineering Institute of Technology Banaras Hindu University Varanasi Ph: +91 9473629892 -- 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. -- navneet singh gaur -- 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. For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Amazon interview Question
@srikar : approach2 is wrong. ex: [1, 5, 7, 66, 7, 1, 77] first window [1,5,7] all are unique.oops On Wed, Feb 6, 2013 at 11:31 PM, Srikar srikar2...@gmail.com wrote: *APPROACH 1:* use a hashtable for both the questions ? Insert the integers as they are given in the array into a hashtable. The structure I am thinking is key (the integer) - [index]. Once all elements are inserted. Run through the hashtable and select the one which has len(value) == 1 and is least, since we want the first unique integer. for the second Q, its a more general Q of the first one. In first k=1. space: 2O(n) time: 2O(n) *APPROACH2: * When we say unique, we will have a pattern. Eg: [5, 5, 66, 66, 7, 1, 1, 77]. In this lets have moving window of 3. first consider (5,5,66). we can easily estab. that there is duplicate here. So move the window by 1 element so we get (5,66,66). Same here. move to next (66,66,7). Again dups here. next (66,7,1). No dups here! take the middle element as this has to be the first unique in the set. The left element belongs to the dup so could 1. Hence 7 is the first unique element. space: O(1) time: O(n) For seond Q I still think hashtable is best. As the numbers are streamed, keep inserting. Srikar On Wed, Feb 6, 2013 at 10:00 AM, navneet singh gaur navneet.singhg...@gmail.com wrote: nice algo ankit, so it will be nlogn using O (n) space only. What abt 2nd Q., which have a big online stream. On Mon, Feb 4, 2013 at 9:30 PM, kumar ankit k.anki...@gmail.com wrote: For 1: i think you can use sorting, sort the array and keep the indices of the numbers in the sorted list. Now traverse the sorted list and in the sorted list you need to find the unique number with the minimum index which is easy to find. Eg: Array:5 3 1 2 4 1 4 Indices: 0 1 2 3 4 5 6 After sorting : Array:1 1 2 3 4 4 5 Indices: 2 5 3 1 4 6 1 Now you can see the unique number with lowest index is 3(index=1). So , you have your answer. On Mon, Feb 4, 2013 at 3:45 PM, navneet singh gaur navneet.singhg...@gmail.com wrote: 1. Given a array,find a first unique integer. 2. Integers are coming as online stream,have to find a kth unique integer till now. For 1. Even we cannot use sorting for solving this as if we sort it than our first number which is non-repetitive changes. The best I am able to do is nlogn using a space of O( n ). For 2. No idea -- 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. -- Kumar Ankit Senior Undergraduate Department of Computer Engineering Institute of Technology Banaras Hindu University Varanasi Ph: +91 9473629892 -- 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. -- navneet singh gaur -- 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. 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. For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Amazon interview Question
in above algo primary index is no of times that value is repeated till now -- 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.
Re: [algogeeks] Amazon interview Question
For 1: i think you can use sorting, sort the array and keep the indices of the numbers in the sorted list. Now traverse the sorted list and in the sorted list you need to find the unique number with the minimum index which is easy to find. Eg: Array:5 3 1 2 4 1 4 Indices: 0 1 2 3 4 5 6 After sorting : Array:1 1 2 3 4 4 5 Indices: 2 5 3 1 4 6 1 Now you can see the unique number with lowest index is 3(index=1). So , you have your answer. On Mon, Feb 4, 2013 at 3:45 PM, navneet singh gaur navneet.singhg...@gmail.com wrote: 1. Given a array,find a first unique integer. 2. Integers are coming as online stream,have to find a kth unique integer till now. For 1. Even we cannot use sorting for solving this as if we sort it than our first number which is non-repetitive changes. The best I am able to do is nlogn using a space of O( n ). For 2. No idea -- 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. -- Kumar Ankit Senior Undergraduate Department of Computer Engineering Institute of Technology Banaras Hindu University Varanasi Ph: +91 9473629892 -- 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.
[algogeeks] Amazon interview Question
1. Given a array,find a first unique integer. 2. Integers are coming as online stream,have to find a kth unique integer till now. For 1. Even we cannot use sorting for solving this as if we sort it than our first number which is non-repetitive changes. The best I am able to do is nlogn using a space of O( n ). For 2. No idea -- 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.
Re: [algogeeks] Amazon interview Question
I can think of an o(n^2) algo for 2n question Make a heap formed acctoring to two indexes 1.Primary -value 2.Secondary - index Now for each new incoming value first search in head if exist inc its index else make a new node -- 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.
[algogeeks] Amazon interview Question
For a given number, find the next greatest number which is just greater than previous one and made up of same digits. --
Re: [algogeeks] Amazon interview Question
loop from the end of given number till you get a digit less than the previously scanned digit.Let the index of that number be 'i' . if index = -1,then the given number is the largest one else do the following 1) swap the digit at the index i with the digit just greater than it in the scanned portion 2) sort the remaining scanned digits after index i. Ex:- let the given number be 51432 the digit '1' is the first digit less that its previously scanned digit '4' thus, we swap 2 which is the smallest greater digit the '1' in scanned portion to get 52431 and the we sort the remaining digits after the index to get 52134. --
Re: [algogeeks] amazon Interview
@atul-I think This Should work for n dimension- complexity O(n^no.of dimesions) :- have N-dimension check for which Tile can contain which Tile.i.e (3,3,4) can contain (2,3,4) . Now 1.Take the titles which cannot contain any-other tile set no-of tile if it is base =1; 2.now take tiles which can contain 1 tile only.This tile will contain any of tiles in 1. case ..it cannot be other title..since other tile can contain tiles=1 which means it shud contain =2..which is not true. set with base value=(if it exist)1+1=2; 3.similarly for other Tiles..in increasing order check maximum tile it can contain.. correct me if wrong...complexity is high but its due to no.of dimesion..for n=2 its simply O(n^2).. -- 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.
[algogeeks] amazon Interview
You are given many slabs each with a length and a breadth. A slab i can be put on slab j if both dimensions of i are less than that of j. In this similar manner, you can keep on putting slabs on each other. Find the maximum stack possible which you can create out of the given slabs and for general n-dimesions -- 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.
Re: [algogeeks] amazon Interview
its a LIS problem. need to think for n-dimension... On 8/26/12, Ravi Ranjan ravi.cool2...@gmail.com wrote: You are given many slabs each with a length and a breadth. A slab i can be put on slab j if both dimensions of i are less than that of j. In this similar manner, you can keep on putting slabs on each other. Find the maximum stack possible which you can create out of the given slabs and for general n-dimesions -- 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.
Re: [algogeeks] amazon Interview
Yeah Atul is right. Here is my solution:-- 1) first rearrange the dimensions of slabs i.e. put bigger dimension in y and smaller dimenson in x (rotate the slab) 2) then arrange all slabs in increasing order of x dimension 3) and then find the longest increasing sub-sequence based on y dimension.. Ex:- (2,5),(5,1),(1,3),(1,2),(6,1) Step-1= (2,5),(1,5),(1,3),(1,2),(1,6) Step-2= (1,2),(1,3),(1,5),(1,6),(2,5) Step-3= LIS=4 { (1,2),(1,3),(1,5),(1,6) OR (1,2),(1,3),(1,5),(2,5) } Correct me if i wrong... On Sun, Aug 26, 2012 at 3:54 PM, atul anand atul.87fri...@gmail.com wrote: its a LIS problem. need to think for n-dimension... On 8/26/12, Ravi Ranjan ravi.cool2...@gmail.com wrote: You are given many slabs each with a length and a breadth. A slab i can be put on slab j if both dimensions of i are less than that of j. In this similar manner, you can keep on putting slabs on each other. Find the maximum stack possible which you can create out of the given slabs and for general n-dimesions -- 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. -- -- ‘Kailash Bagaria’ B-tech 4th year Computer Science Engineering Indian Institute of Technology, Roorkee Roorkee, India (247667) -- 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.
Re: [algogeeks] amazon Interview
@kailash : you can simply find area of each slab area=x*y ,,,store it; then just run LIS on this area. On 8/26/12, Kailash Bagaria kbkailashbaga...@gmail.com wrote: Yeah Atul is right. Here is my solution:-- 1) first rearrange the dimensions of slabs i.e. put bigger dimension in y and smaller dimenson in x (rotate the slab) 2) then arrange all slabs in increasing order of x dimension 3) and then find the longest increasing sub-sequence based on y dimension.. Ex:- (2,5),(5,1),(1,3),(1,2),(6,1) Step-1= (2,5),(1,5),(1,3),(1,2),(1,6) Step-2= (1,2),(1,3),(1,5),(1,6),(2,5) Step-3= LIS=4 { (1,2),(1,3),(1,5),(1,6) OR (1,2),(1,3),(1,5),(2,5) } Correct me if i wrong... On Sun, Aug 26, 2012 at 3:54 PM, atul anand atul.87fri...@gmail.com wrote: its a LIS problem. need to think for n-dimension... On 8/26/12, Ravi Ranjan ravi.cool2...@gmail.com wrote: You are given many slabs each with a length and a breadth. A slab i can be put on slab j if both dimensions of i are less than that of j. In this similar manner, you can keep on putting slabs on each other. Find the maximum stack possible which you can create out of the given slabs and for general n-dimesions -- 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. -- -- ‘Kailash Bagaria’ B-tech 4th year Computer Science Engineering Indian Institute of Technology, Roorkee Roorkee, India (247667) -- 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.
Re: [algogeeks] amazon Interview
@Atul007: No, because a (1,4) tile will not fit on a (2,3) tile. Dave On Sunday, August 26, 2012 7:45:27 AM UTC-5, atul007 wrote: @kailash : you can simply find area of each slab area=x*y ,,,store it; then just run LIS on this area. On 8/26/12, Kailash Bagaria kbkailas...@gmail.com javascript: wrote: Yeah Atul is right. Here is my solution:-- 1) first rearrange the dimensions of slabs i.e. put bigger dimension in y and smaller dimenson in x (rotate the slab) 2) then arrange all slabs in increasing order of x dimension 3) and then find the longest increasing sub-sequence based on y dimension.. Ex:- (2,5),(5,1),(1,3),(1,2),(6,1) Step-1= (2,5),(1,5),(1,3),(1,2),(1,6) Step-2= (1,2),(1,3),(1,5),(1,6),(2,5) Step-3= LIS=4 { (1,2),(1,3),(1,5),(1,6) OR (1,2),(1,3),(1,5),(2,5) } Correct me if i wrong... On Sun, Aug 26, 2012 at 3:54 PM, atul anand atul.8...@gmail.comjavascript: wrote: its a LIS problem. need to think for n-dimension... On 8/26/12, Ravi Ranjan ravi.c...@gmail.com javascript: wrote: You are given many slabs each with a length and a breadth. A slab i can be put on slab j if both dimensions of i are less than that of j. In this similar manner, you can keep on putting slabs on each other. Find the maximum stack possible which you can create out of the given slabs and for general n-dimesions -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algo...@googlegroups.comjavascript:. To unsubscribe from this group, send email to algogeeks+...@googlegroups.com javascript:. 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 algo...@googlegroups.comjavascript:. To unsubscribe from this group, send email to algogeeks+...@googlegroups.com javascript:. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- -- ‘Kailash Bagaria’ B-tech 4th year Computer Science Engineering Indian Institute of Technology, Roorkee Roorkee, India (247667) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algo...@googlegroups.comjavascript:. To unsubscribe from this group, send email to algogeeks+...@googlegroups.com javascript:. 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 view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/ABJAgG77YhkJ. 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.
Re: [algogeeks] amazon Interview
@dave : correct.. i guess this will work :- sort in decreasing area. then run LIS such that for i j , length( i ) length( j ) width( i ) width( j ) On 8/26/12, Dave dave_and_da...@juno.com wrote: @Atul007: No, because a (1,4) tile will not fit on a (2,3) tile. Dave On Sunday, August 26, 2012 7:45:27 AM UTC-5, atul007 wrote: @kailash : you can simply find area of each slab area=x*y ,,,store it; then just run LIS on this area. On 8/26/12, Kailash Bagaria kbkailas...@gmail.com javascript: wrote: Yeah Atul is right. Here is my solution:-- 1) first rearrange the dimensions of slabs i.e. put bigger dimension in y and smaller dimenson in x (rotate the slab) 2) then arrange all slabs in increasing order of x dimension 3) and then find the longest increasing sub-sequence based on y dimension.. Ex:- (2,5),(5,1),(1,3),(1,2),(6,1) Step-1= (2,5),(1,5),(1,3),(1,2),(1,6) Step-2= (1,2),(1,3),(1,5),(1,6),(2,5) Step-3= LIS=4 { (1,2),(1,3),(1,5),(1,6) OR (1,2),(1,3),(1,5),(2,5) } Correct me if i wrong... On Sun, Aug 26, 2012 at 3:54 PM, atul anand atul.8...@gmail.comjavascript: wrote: its a LIS problem. need to think for n-dimension... On 8/26/12, Ravi Ranjan ravi.c...@gmail.com javascript: wrote: You are given many slabs each with a length and a breadth. A slab i can be put on slab j if both dimensions of i are less than that of j. In this similar manner, you can keep on putting slabs on each other. Find the maximum stack possible which you can create out of the given slabs and for general n-dimesions -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algo...@googlegroups.comjavascript:. To unsubscribe from this group, send email to algogeeks+...@googlegroups.com javascript:. 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 algo...@googlegroups.comjavascript:. To unsubscribe from this group, send email to algogeeks+...@googlegroups.com javascript:. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- -- ‘Kailash Bagaria’ B-tech 4th year Computer Science Engineering Indian Institute of Technology, Roorkee Roorkee, India (247667) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algo...@googlegroups.comjavascript:. To unsubscribe from this group, send email to algogeeks+...@googlegroups.com javascript:. 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 view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/ABJAgG77YhkJ. 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.
Re: [algogeeks] amazon Interview
but how to solve this problem for with n-dimension ?? On Sun, Aug 26, 2012 at 6:47 PM, atul anand atul.87fri...@gmail.com wrote: @dave : correct.. i guess this will work :- sort in decreasing area. then run LIS such that for i j , length( i ) length( j ) width( i ) width( j ) On 8/26/12, Dave dave_and_da...@juno.com wrote: @Atul007: No, because a (1,4) tile will not fit on a (2,3) tile. Dave On Sunday, August 26, 2012 7:45:27 AM UTC-5, atul007 wrote: @kailash : you can simply find area of each slab area=x*y ,,,store it; then just run LIS on this area. On 8/26/12, Kailash Bagaria kbkailas...@gmail.com javascript: wrote: Yeah Atul is right. Here is my solution:-- 1) first rearrange the dimensions of slabs i.e. put bigger dimension in y and smaller dimenson in x (rotate the slab) 2) then arrange all slabs in increasing order of x dimension 3) and then find the longest increasing sub-sequence based on y dimension.. Ex:- (2,5),(5,1),(1,3),(1,2),(6,1) Step-1= (2,5),(1,5),(1,3),(1,2),(1,6) Step-2= (1,2),(1,3),(1,5),(1,6),(2,5) Step-3= LIS=4 { (1,2),(1,3),(1,5),(1,6) OR (1,2),(1,3),(1,5),(2,5) } Correct me if i wrong... On Sun, Aug 26, 2012 at 3:54 PM, atul anand atul.8...@gmail.comjavascript: wrote: its a LIS problem. need to think for n-dimension... On 8/26/12, Ravi Ranjan ravi.c...@gmail.com javascript: wrote: You are given many slabs each with a length and a breadth. A slab i can be put on slab j if both dimensions of i are less than that of j. In this similar manner, you can keep on putting slabs on each other. Find the maximum stack possible which you can create out of the given slabs and for general n-dimesions -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algo...@googlegroups.comjavascript:. To unsubscribe from this group, send email to algogeeks+...@googlegroups.com javascript:. 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 algo...@googlegroups.comjavascript:. To unsubscribe from this group, send email to algogeeks+...@googlegroups.com javascript:. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- -- ‘Kailash Bagaria’ B-tech 4th year Computer Science Engineering Indian Institute of Technology, Roorkee Roorkee, India (247667) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algo...@googlegroups.comjavascript:. To unsubscribe from this group, send email to algogeeks+...@googlegroups.com javascript:. 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 view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/ABJAgG77YhkJ. 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.
[algogeeks] Amazon Interview Question
Given an array of integers where some numbers repeat once, some numbers repeat twice and only one number repeats thrice, how do you find the number that gets repeated 3 times? Does this problem have an O(n) time and O(1) space solution? No hashmaps please! -- 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.
Re: [algogeeks] Amazon Interview Question
@ashgoel - Could you please explain what exactly are you doing here ? On Wednesday, 4 July 2012 16:16:38 UTC+5:30, ashgoel wrote: Q4 vectorString prefix; prefix[0]=NULL; prefixCount =1; for (int i=0;in;i++) for (int j=0;jn;j++) for (int k=0; kprefixCount;k++) { if (visited[i][j]) continue; visited[i][j] = true; String s=prefix[k]+a[i][j]; if (isWord(s) { printWord(s); prefix[k]=s; continue;} else if isPrefix(s) prefix[prefixCount++] = s; else removePrefix(prefix[k], prefixCount); prefix[prefixCount++] = String(a[i][j]; } Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Wed, Jul 4, 2012 at 4:13 PM, Ashish Goel ashg...@gmail.com wrote: 1. inverted hasp map 2. not clear 3. VLR, how do you identify end of L and start of R, question incomplete 4. One problem: consider ... a b... c d... ... if ab is a prefix, can aba be another prefix, i would assume so. But if that is true, i am not sure if this program will come to an end. vectorString prefix; prefix[0]=NULL; prefixCount =1; for (int i=0;in;i++) for (int j=0;jn;j++) for (int k=0; kprefixCount;k++) { String s=prefix[k]+a[i][j]; if (isWord(s) { printWord(s); prefix[k]=s; continue;} else if isPrefix(s) prefix[prefixCount++] = s; else removePrefix(prefix[k], prefixCount); prefix[prefixCount++] = String(a[i][j]; } Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Wed, Jul 4, 2012 at 12:22 PM, Decipher ankurseth...@gmail.com wrote: Find the next higher number in set of permutations of a given number -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/Q7xtXJj8lVIJ. 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.
[algogeeks] Amazon Interview Question
Q1) Given a newspaper and a set of ‘l’ words, give an efficient algorithm to find the ‘l’ words in the newspaper. Q2) Find the next higher number in set of permutations of a given number. Q3) Given preorder of a BST, find if each non-leaf node has just one child or not. To be done in linear time. Q4) Given a dictionary of words, two APIs Is_word(string) Is_prefix(string) And a NxN matrix with each postion consisting of a character. If from any position (i,j) you can move in any of the four directions, find out the all the valid words that can be formed in the matrix. (looping is not allowed, i.e. for forming a word position if you start from (i,j) and move to (i-1,j) then from this position you cannot go back to (i,j)) Q5) Given that there are n players and each one of them has played exactly one game with every other player. Also given is an API that tells whether player ‘a’ won or lost to player ‘b’, where ‘a’ and ‘b’ could be any of the players. Arrange the n players in a length n array such that player at position ‘i’ has won from player at ‘i+1’ and lost to player at ‘i-1’. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/LzG-OrtjDmoJ. 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.
Re: [algogeeks] Amazon Interview Question
1. inverted hasp map 2. not clear 3. VLR, how do you identify end of L and start of R, question incomplete 4. One problem: consider ... a b... c d... ... if ab is a prefix, can aba be another prefix, i would assume so. But if that is true, i am not sure if this program will come to an end. vectorString prefix; prefix[0]=NULL; prefixCount =1; for (int i=0;in;i++) for (int j=0;jn;j++) for (int k=0; kprefixCount;k++) { String s=prefix[k]+a[i][j]; if (isWord(s) { printWord(s); prefix[k]=s; continue;} else if isPrefix(s) prefix[prefixCount++] = s; else removePrefix(prefix[k], prefixCount); prefix[prefixCount++] = String(a[i][j]; } Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Wed, Jul 4, 2012 at 12:22 PM, Decipher ankurseth...@gmail.com wrote: Find the next higher number in set of permutations of a given number -- 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.
Re: [algogeeks] Amazon Interview Question
Q5 is sorting problem Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Wed, Jul 4, 2012 at 4:13 PM, Ashish Goel ashg...@gmail.com wrote: 1. inverted hasp map 2. not clear 3. VLR, how do you identify end of L and start of R, question incomplete 4. One problem: consider ... a b... c d... ... if ab is a prefix, can aba be another prefix, i would assume so. But if that is true, i am not sure if this program will come to an end. vectorString prefix; prefix[0]=NULL; prefixCount =1; for (int i=0;in;i++) for (int j=0;jn;j++) for (int k=0; kprefixCount;k++) { String s=prefix[k]+a[i][j]; if (isWord(s) { printWord(s); prefix[k]=s; continue;} else if isPrefix(s) prefix[prefixCount++] = s; else removePrefix(prefix[k], prefixCount); prefix[prefixCount++] = String(a[i][j]; } Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Wed, Jul 4, 2012 at 12:22 PM, Decipher ankurseth...@gmail.com wrote: Find the next higher number in set of permutations of a given number -- 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.
Re: [algogeeks] Amazon Interview Question
Q4 vectorString prefix; prefix[0]=NULL; prefixCount =1; for (int i=0;in;i++) for (int j=0;jn;j++) for (int k=0; kprefixCount;k++) { if (visited[i][j]) continue; visited[i][j] = true; String s=prefix[k]+a[i][j]; if (isWord(s) { printWord(s); prefix[k]=s; continue;} else if isPrefix(s) prefix[prefixCount++] = s; else removePrefix(prefix[k], prefixCount); prefix[prefixCount++] = String(a[i][j]; } Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Wed, Jul 4, 2012 at 4:13 PM, Ashish Goel ashg...@gmail.com wrote: 1. inverted hasp map 2. not clear 3. VLR, how do you identify end of L and start of R, question incomplete 4. One problem: consider ... a b... c d... ... if ab is a prefix, can aba be another prefix, i would assume so. But if that is true, i am not sure if this program will come to an end. vectorString prefix; prefix[0]=NULL; prefixCount =1; for (int i=0;in;i++) for (int j=0;jn;j++) for (int k=0; kprefixCount;k++) { String s=prefix[k]+a[i][j]; if (isWord(s) { printWord(s); prefix[k]=s; continue;} else if isPrefix(s) prefix[prefixCount++] = s; else removePrefix(prefix[k], prefixCount); prefix[prefixCount++] = String(a[i][j]; } Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Wed, Jul 4, 2012 at 12:22 PM, Decipher ankurseth...@gmail.com wrote: Find the next higher number in set of permutations of a given number -- 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.
Re: [algogeeks] Amazon Interview Question
Consider trees: 1 3 2 3 2 1 pre order traversal is same still (1 , 2 ,3) even though ist tree doesn't satisfy the criteria . So I don't think it can be determined. On Wed, Jul 4, 2012 at 4:16 PM, Ashish Goel ashg...@gmail.com wrote: Q4 vectorString prefix; prefix[0]=NULL; prefixCount =1; for (int i=0;in;i++) for (int j=0;jn;j++) for (int k=0; kprefixCount;k++) { if (visited[i][j]) continue; visited[i][j] = true; String s=prefix[k]+a[i][j]; if (isWord(s) { printWord(s); prefix[k]=s; continue;} else if isPrefix(s) prefix[prefixCount++] = s; else removePrefix(prefix[k], prefixCount); prefix[prefixCount++] = String(a[i][j]; } Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Wed, Jul 4, 2012 at 4:13 PM, Ashish Goel ashg...@gmail.com wrote: 1. inverted hasp map 2. not clear 3. VLR, how do you identify end of L and start of R, question incomplete 4. One problem: consider ... a b... c d... ... if ab is a prefix, can aba be another prefix, i would assume so. But if that is true, i am not sure if this program will come to an end. vectorString prefix; prefix[0]=NULL; prefixCount =1; for (int i=0;in;i++) for (int j=0;jn;j++) for (int k=0; kprefixCount;k++) { String s=prefix[k]+a[i][j]; if (isWord(s) { printWord(s); prefix[k]=s; continue;} else if isPrefix(s) prefix[prefixCount++] = s; else removePrefix(prefix[k], prefixCount); prefix[prefixCount++] = String(a[i][j]; } Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Wed, Jul 4, 2012 at 12:22 PM, Decipher ankurseth...@gmail.com wrote: Find the next higher number in set of permutations of a given number -- 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. -- Thanks regards Bhupendra -- 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.
Re: [algogeeks] Amazon Interview Question
1. For first question trie of given word will be best option. Space complexity O(total length of words) (worst case) Time complexity O(T) . T length of input text (Newspaper) 2. consider it to be a 4 digit number ABCD . Find maximum Most significant digit say it is C , and out of these nos find maximum value of next digit say A and so on . Suppose Final no. is CADB Now next highest permutation will be the no. just greater than this and made of these digits . This is easy. On Wed, Jul 4, 2012 at 5:17 PM, Bhupendra Dubey bhupendra@gmail.comwrote: Consider trees: 1 3 2 3 2 1 pre order traversal is same still (1 , 2 ,3) even though ist tree doesn't satisfy the criteria . So I don't think it can be determined. On Wed, Jul 4, 2012 at 4:16 PM, Ashish Goel ashg...@gmail.com wrote: Q4 vectorString prefix; prefix[0]=NULL; prefixCount =1; for (int i=0;in;i++) for (int j=0;jn;j++) for (int k=0; kprefixCount;k++) { if (visited[i][j]) continue; visited[i][j] = true; String s=prefix[k]+a[i][j]; if (isWord(s) { printWord(s); prefix[k]=s; continue;} else if isPrefix(s) prefix[prefixCount++] = s; else removePrefix(prefix[k], prefixCount); prefix[prefixCount++] = String(a[i][j]; } Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Wed, Jul 4, 2012 at 4:13 PM, Ashish Goel ashg...@gmail.com wrote: 1. inverted hasp map 2. not clear 3. VLR, how do you identify end of L and start of R, question incomplete 4. One problem: consider ... a b... c d... ... if ab is a prefix, can aba be another prefix, i would assume so. But if that is true, i am not sure if this program will come to an end. vectorString prefix; prefix[0]=NULL; prefixCount =1; for (int i=0;in;i++) for (int j=0;jn;j++) for (int k=0; kprefixCount;k++) { String s=prefix[k]+a[i][j]; if (isWord(s) { printWord(s); prefix[k]=s; continue;} else if isPrefix(s) prefix[prefixCount++] = s; else removePrefix(prefix[k], prefixCount); prefix[prefixCount++] = String(a[i][j]; } Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Wed, Jul 4, 2012 at 12:22 PM, Decipher ankurseth...@gmail.comwrote: Find the next higher number in set of permutations of a given number -- 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. -- Thanks regards Bhupendra -- Thanks regards Bhupendra -- 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.
Re: [algogeeks] Amazon Interview Question
For question 5. Even this doesn't seems right Consider this scenario Match b/w Winner a vs b a a vs c c b vs c b What will be order ?? acb or bca On Wed, Jul 4, 2012 at 5:38 PM, Bhupendra Dubey bhupendra@gmail.comwrote: 1. For first question trie of given word will be best option. Space complexity O(total length of words) (worst case) Time complexity O(T) . T length of input text (Newspaper) 2. consider it to be a 4 digit number ABCD . Find maximum Most significant digit say it is C , and out of these nos find maximum value of next digit say A and so on . Suppose Final no. is CADB Now next highest permutation will be the no. just greater than this and made of these digits . This is easy. On Wed, Jul 4, 2012 at 5:17 PM, Bhupendra Dubey bhupendra@gmail.comwrote: Consider trees: 1 3 2 3 2 1 pre order traversal is same still (1 , 2 ,3) even though ist tree doesn't satisfy the criteria . So I don't think it can be determined. On Wed, Jul 4, 2012 at 4:16 PM, Ashish Goel ashg...@gmail.com wrote: Q4 vectorString prefix; prefix[0]=NULL; prefixCount =1; for (int i=0;in;i++) for (int j=0;jn;j++) for (int k=0; kprefixCount;k++) { if (visited[i][j]) continue; visited[i][j] = true; String s=prefix[k]+a[i][j]; if (isWord(s) { printWord(s); prefix[k]=s; continue;} else if isPrefix(s) prefix[prefixCount++] = s; else removePrefix(prefix[k], prefixCount); prefix[prefixCount++] = String(a[i][j]; } Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Wed, Jul 4, 2012 at 4:13 PM, Ashish Goel ashg...@gmail.com wrote: 1. inverted hasp map 2. not clear 3. VLR, how do you identify end of L and start of R, question incomplete 4. One problem: consider ... a b... c d... ... if ab is a prefix, can aba be another prefix, i would assume so. But if that is true, i am not sure if this program will come to an end. vectorString prefix; prefix[0]=NULL; prefixCount =1; for (int i=0;in;i++) for (int j=0;jn;j++) for (int k=0; kprefixCount;k++) { String s=prefix[k]+a[i][j]; if (isWord(s) { printWord(s); prefix[k]=s; continue;} else if isPrefix(s) prefix[prefixCount++] = s; else removePrefix(prefix[k], prefixCount); prefix[prefixCount++] = String(a[i][j]; } Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Wed, Jul 4, 2012 at 12:22 PM, Decipher ankurseth...@gmail.comwrote: Find the next higher number in set of permutations of a given number -- 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. -- Thanks regards Bhupendra -- Thanks regards Bhupendra -- Thanks regards Bhupendra -- 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.
Re: [algogeeks] Amazon Interview Question
1 2 3 is not a BST and its pre-order traversal is 1 2 3, pre order of other is 3 2 1 . On Wed, Jul 4, 2012 at 5:17 PM, Bhupendra Dubey bhupendra@gmail.comwrote: Consider trees: 1 3 2 3 2 1 pre order traversal is same still (1 , 2 ,3) even though ist tree doesn't satisfy the criteria . So I don't think it can be determined. On Wed, Jul 4, 2012 at 4:16 PM, Ashish Goel ashg...@gmail.com wrote: Q4 vectorString prefix; prefix[0]=NULL; prefixCount =1; for (int i=0;in;i++) for (int j=0;jn;j++) for (int k=0; kprefixCount;k++) { if (visited[i][j]) continue; visited[i][j] = true; String s=prefix[k]+a[i][j]; if (isWord(s) { printWord(s); prefix[k]=s; continue;} else if isPrefix(s) prefix[prefixCount++] = s; else removePrefix(prefix[k], prefixCount); prefix[prefixCount++] = String(a[i][j]; } Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Wed, Jul 4, 2012 at 4:13 PM, Ashish Goel ashg...@gmail.com wrote: 1. inverted hasp map 2. not clear 3. VLR, how do you identify end of L and start of R, question incomplete 4. One problem: consider ... a b... c d... ... if ab is a prefix, can aba be another prefix, i would assume so. But if that is true, i am not sure if this program will come to an end. vectorString prefix; prefix[0]=NULL; prefixCount =1; for (int i=0;in;i++) for (int j=0;jn;j++) for (int k=0; kprefixCount;k++) { String s=prefix[k]+a[i][j]; if (isWord(s) { printWord(s); prefix[k]=s; continue;} else if isPrefix(s) prefix[prefixCount++] = s; else removePrefix(prefix[k], prefixCount); prefix[prefixCount++] = String(a[i][j]; } Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Wed, Jul 4, 2012 at 12:22 PM, Decipher ankurseth...@gmail.comwrote: Find the next higher number in set of permutations of a given number -- 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. -- Thanks regards Bhupendra -- 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.
Re: [algogeeks] Amazon Interview Question
Sorry i typed wrongly tree is 2 1 3 preorder traversal is 123 and same for other tree as well. Please check ! On Wed, Jul 4, 2012 at 5:24 PM, a g ag20071...@gmail.com wrote: 1 2 3 is not a BST and its pre-order traversal is 1 2 3, pre order of other is 3 2 1 . On Wed, Jul 4, 2012 at 5:17 PM, Bhupendra Dubey bhupendra@gmail.comwrote: Consider trees: 1 3 2 3 2 1 pre order traversal is same still (1 , 2 ,3) even though ist tree doesn't satisfy the criteria . So I don't think it can be determined. On Wed, Jul 4, 2012 at 4:16 PM, Ashish Goel ashg...@gmail.com wrote: Q4 vectorString prefix; prefix[0]=NULL; prefixCount =1; for (int i=0;in;i++) for (int j=0;jn;j++) for (int k=0; kprefixCount;k++) { if (visited[i][j]) continue; visited[i][j] = true; String s=prefix[k]+a[i][j]; if (isWord(s) { printWord(s); prefix[k]=s; continue;} else if isPrefix(s) prefix[prefixCount++] = s; else removePrefix(prefix[k], prefixCount); prefix[prefixCount++] = String(a[i][j]; } Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Wed, Jul 4, 2012 at 4:13 PM, Ashish Goel ashg...@gmail.com wrote: 1. inverted hasp map 2. not clear 3. VLR, how do you identify end of L and start of R, question incomplete 4. One problem: consider ... a b... c d... ... if ab is a prefix, can aba be another prefix, i would assume so. But if that is true, i am not sure if this program will come to an end. vectorString prefix; prefix[0]=NULL; prefixCount =1; for (int i=0;in;i++) for (int j=0;jn;j++) for (int k=0; kprefixCount;k++) { String s=prefix[k]+a[i][j]; if (isWord(s) { printWord(s); prefix[k]=s; continue;} else if isPrefix(s) prefix[prefixCount++] = s; else removePrefix(prefix[k], prefixCount); prefix[prefixCount++] = String(a[i][j]; } Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Wed, Jul 4, 2012 at 12:22 PM, Decipher ankurseth...@gmail.comwrote: Find the next higher number in set of permutations of a given number -- 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. -- Thanks regards Bhupendra -- 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. -- Thanks regards Bhupendra -- 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.
[algogeeks] Amazon Interview Question
Hi, *There are two arrays of length 100 each. Each of these has initially n (n=100) elements. First array contains names and the second array contains numbers such that ith name in array1 corresponds to ith number in array2. Write a program which asks the user to enter a name, finds it in array1,* *a. if it exists, then print the corresponding number in array2, b. else ask the user to input its associated number and add the number and name to array2 and array1 respectively, and update the size of list* I can think of solving it through linear walk to the array. Anyone with more optimized algorithm like BST or HashTable? comments are welcome Thanks -- 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.
Re: [algogeeks] Amazon Interview Question
example pls... On Thu, Jun 14, 2012 at 1:01 PM, Mohit Rathi mohit08...@iiitd.ac.in wrote: Hi, *There are two arrays of length 100 each. Each of these has initially n (n=100) elements. First array contains names and the second array contains numbers such that ith name in array1 corresponds to ith number in array2. Write a program which asks the user to enter a name, finds it in array1,* *a. if it exists, then print the corresponding number in array2, b. else ask the user to input its associated number and add the number and name to array2 and array1 respectively, and update the size of list* I can think of solving it through linear walk to the array. Anyone with more optimized algorithm like BST or HashTable? comments are welcome Thanks -- 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. -- Utsav Sharma, NIT Allahabad -- 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.
Re: [algogeeks] Amazon Interview Question
arr1 = [abc,xyz,lmn,def] arr2 = [3,6,2,8] if user enters xyz then 6 will be printed else if xyz doesn't exist in arr1 then ask for a number and add them in respective arrays(name in arr1 and number in arr2). Hope it helps On Thu, Jun 14, 2012 at 3:58 PM, utsav sharma utsav.sharm...@gmail.comwrote: example pls... On Thu, Jun 14, 2012 at 1:01 PM, Mohit Rathi mohit08...@iiitd.ac.inwrote: Hi, *There are two arrays of length 100 each. Each of these has initially n (n=100) elements. First array contains names and the second array contains numbers such that ith name in array1 corresponds to ith number in array2. Write a program which asks the user to enter a name, finds it in array1,* *a. if it exists, then print the corresponding number in array2, b. else ask the user to input its associated number and add the number and name to array2 and array1 respectively, and update the size of list* I can think of solving it through linear walk to the array. Anyone with more optimized algorithm like BST or HashTable? comments are welcome Thanks -- 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. -- Utsav Sharma, NIT Allahabad -- 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. -- Mohit Rathi 4th year, B.Tech (IT) IIIT-Delhi -- 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.
Re: [algogeeks] Amazon Interview Question
it can be done using map in c++ On Thu, Jun 14, 2012 at 4:23 PM, Mohit Rathi mohit08...@iiitd.ac.in wrote: arr1 = [abc,xyz,lmn,def] arr2 = [3,6,2,8] if user enters xyz then 6 will be printed else if xyz doesn't exist in arr1 then ask for a number and add them in respective arrays(name in arr1 and number in arr2). Hope it helps On Thu, Jun 14, 2012 at 3:58 PM, utsav sharma utsav.sharm...@gmail.comwrote: example pls... On Thu, Jun 14, 2012 at 1:01 PM, Mohit Rathi mohit08...@iiitd.ac.inwrote: Hi, *There are two arrays of length 100 each. Each of these has initially n (n=100) elements. First array contains names and the second array contains numbers such that ith name in array1 corresponds to ith number in array2. Write a program which asks the user to enter a name, finds it in array1, * *a. if it exists, then print the corresponding number in array2, b. else ask the user to input its associated number and add the number and name to array2 and array1 respectively, and update the size of list* I can think of solving it through linear walk to the array. Anyone with more optimized algorithm like BST or HashTable? comments are welcome Thanks -- 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. -- Utsav Sharma, NIT Allahabad -- 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. -- Mohit Rathi 4th year, B.Tech (IT) IIIT-Delhi -- 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. -- Utsav Sharma, NIT Allahabad -- 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.
Re: [algogeeks] Amazon Interview Question
Since the size of array is very less I think Hashmap is the best. Use name as the hash key and number as its value. On Thursday, June 14, 2012 6:46:34 PM UTC+5:30, utsav sharma wrote: it can be done using map in c++ On Thu, Jun 14, 2012 at 4:23 PM, Mohit Rathi mohit08...@iiitd.ac.inwrote: arr1 = [abc,xyz,lmn,def] arr2 = [3,6,2,8] if user enters xyz then 6 will be printed else if xyz doesn't exist in arr1 then ask for a number and add them in respective arrays(name in arr1 and number in arr2). Hope it helps On Thu, Jun 14, 2012 at 3:58 PM, utsav sharma utsav.sharm...@gmail.comwrote: example pls... On Thu, Jun 14, 2012 at 1:01 PM, Mohit Rathi mohit08...@iiitd.ac.inwrote: Hi, *There are two arrays of length 100 each. Each of these has initially n (n=100) elements. First array contains names and the second array contains numbers such that ith name in array1 corresponds to ith number in array2. Write a program which asks the user to enter a name, finds it in array1, * *a. if it exists, then print the corresponding number in array2, b. else ask the user to input its associated number and add the number and name to array2 and array1 respectively, and update the size of list* I can think of solving it through linear walk to the array. Anyone with more optimized algorithm like BST or HashTable? comments are welcome Thanks -- 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. -- Utsav Sharma, NIT Allahabad -- 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. -- Mohit Rathi 4th year, B.Tech (IT) IIIT-Delhi -- 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. -- Utsav Sharma, NIT Allahabad -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/wF1ZUNLZV4UJ. 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.
Re: [algogeeks] Amazon Interview Question
Hashmap can be used for effective retreival.. On Thu, Jun 14, 2012 at 4:23 PM, Mohit Rathi mohit08...@iiitd.ac.in wrote: arr1 = [abc,xyz,lmn,def] arr2 = [3,6,2,8] if user enters xyz then 6 will be printed else if xyz doesn't exist in arr1 then ask for a number and add them in respective arrays(name in arr1 and number in arr2). Hope it helps On Thu, Jun 14, 2012 at 3:58 PM, utsav sharma utsav.sharm...@gmail.comwrote: example pls... On Thu, Jun 14, 2012 at 1:01 PM, Mohit Rathi mohit08...@iiitd.ac.inwrote: Hi, *There are two arrays of length 100 each. Each of these has initially n (n=100) elements. First array contains names and the second array contains numbers such that ith name in array1 corresponds to ith number in array2. Write a program which asks the user to enter a name, finds it in array1, * *a. if it exists, then print the corresponding number in array2, b. else ask the user to input its associated number and add the number and name to array2 and array1 respectively, and update the size of list* I can think of solving it through linear walk to the array. Anyone with more optimized algorithm like BST or HashTable? comments are welcome Thanks -- 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. -- Utsav Sharma, NIT Allahabad -- 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. -- Mohit Rathi 4th year, B.Tech (IT) IIIT-Delhi -- 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.
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.
[algogeeks] amazon interview questions
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.
Re: [algogeeks] Amazon interview question
array of bits? if the current integer is present set the bit if else make it zero, searching, insertion and deletion all in O(1) time. On Thu, May 24, 2012 at 4:15 PM, rishabh shukla rockrishabh.mn...@gmail.com wrote: Suggest a data structure for storing million trillion numbers efficiently in very less space. Means space complexity should be as less as possible -- Rishabh Shukla B.Tech Final Year MNNIT Allahabad -- 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.
Re: [algogeeks] Amazon interview question
What is the purpose of these numbers, if the idea is to manage a free pool, then probably 10-ary-tree is the solution. May be Tiger Tree Hash a better answer where it is tree to say level 7 and then for rest three digits it become hash table. This way, the chunks can be kept on different machines too. Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Thu, May 24, 2012 at 4:51 PM, Aman Raj amanka...@gmail.com wrote: array of bits? if the current integer is present set the bit if else make it zero, searching, insertion and deletion all in O(1) time. On Thu, May 24, 2012 at 4:15 PM, rishabh shukla rockrishabh.mn...@gmail.com wrote: Suggest a data structure for storing million trillion numbers efficiently in very less space. Means space complexity should be as less as possible -- Rishabh Shukla B.Tech Final Year MNNIT Allahabad -- 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. -- 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.
Re: [algogeeks] Amazon interview question
refer http://www.cs.bell-labs.com/cm/cs/pearls/sol01.html Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Thu, May 24, 2012 at 6:00 PM, Ashish Goel ashg...@gmail.com wrote: What is the purpose of these numbers, if the idea is to manage a free pool, then probably 10-ary-tree is the solution. May be Tiger Tree Hash a better answer where it is tree to say level 7 and then for rest three digits it become hash table. This way, the chunks can be kept on different machines too. Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Thu, May 24, 2012 at 4:51 PM, Aman Raj amanka...@gmail.com wrote: array of bits? if the current integer is present set the bit if else make it zero, searching, insertion and deletion all in O(1) time. On Thu, May 24, 2012 at 4:15 PM, rishabh shukla rockrishabh.mn...@gmail.com wrote: Suggest a data structure for storing million trillion numbers efficiently in very less space. Means space complexity should be as less as possible -- Rishabh Shukla B.Tech Final Year MNNIT Allahabad -- 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. -- 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.
Re: [algogeeks] Amazon Interview Question
No limit on #nodes and #edges. On Thu, Apr 26, 2012 at 1:06 PM, bharat b bagana.bharatku...@gmail.comwrote: In input, he mentions #nodes and #edges of each nodes has, right? create an array of linked lists.. each index in the array represents the node number and the linked list of that represents edges of that node. Am I right? On Wed, Apr 25, 2012 at 5:40 PM, Radhakrishnan Venkataramani radhakrishnance...@gmail.com wrote: How will you implement a graph data structure ? Give an linked implementation as we do not know how many nodes will be there and how many edges will be there. Make a copy of this graph.. -- 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. -- 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.
Re: [algogeeks] Amazon Interview Question
@bharat: +1 On Thu, Apr 26, 2012 at 1:06 PM, bharat b bagana.bharatku...@gmail.com wrote: create an array of linked lists.. each index in the array represents the node number and the linked list of that represents edges of that node. -- 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.
Re: [algogeeks] Amazon Interview Question
In input, he mentions #nodes and #edges of each nodes has, right? create an array of linked lists.. each index in the array represents the node number and the linked list of that represents edges of that node. Am I right? On Wed, Apr 25, 2012 at 5:40 PM, Radhakrishnan Venkataramani radhakrishnance...@gmail.com wrote: How will you implement a graph data structure ? Give an linked implementation as we do not know how many nodes will be there and how many edges will be there. Make a copy of this graph.. -- 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.
Re: [algogeeks] Amazon Interview Question
What will be the size of the array? You don't know the number of nodes in the graph. Implementing table doubling would be tedious. If they asked for a specific language implementation then for c++ you can use a vector of linked lists. Otherwise a linked list of pointers to head of linked lists would be a good option, I think. Sukun Tarachandani IDD Electrical Engineering(2nd year) IIT Roorkee On Thu, Apr 26, 2012 at 1:06 PM, bharat b bagana.bharatku...@gmail.comwrote: In input, he mentions #nodes and #edges of each nodes has, right? create an array of linked lists.. each index in the array represents the node number and the linked list of that represents edges of that node. Am I right? On Wed, Apr 25, 2012 at 5:40 PM, Radhakrishnan Venkataramani radhakrishnance...@gmail.com wrote: How will you implement a graph data structure ? Give an linked implementation as we do not know how many nodes will be there and how many edges will be there. Make a copy of this graph.. -- 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. -- 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.
[algogeeks] Amazon Interview Question
How will you implement a graph data structure ? Give an linked implementation as we do not know how many nodes will be there and how many edges will be there. Make a copy of this graph.. -- 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.
Re: [algogeeks] Amazon Interview Question
@Neeraj : will u pls explain u'r logic ... On 1/19/12, NEERAJ KODDHAN neerajdc...@gmail.com wrote: int[] a = new int[2*n]; put(a, n); static void put(int[] a,int i){ if(i0){ for(int j=0;ja.length-i-1;j++){ if(a[j]==0 a[j+i+1]==0){ a[j]=i; a[j+i+1]=i; put(a, i-1); a[j]=0; a[j+i+1]=0; } } }else if(i==0){ for (int k : a) { System.out.print(k + ); } System.out.println(); } } On Wed, Jan 18, 2012 at 10:04 PM, Coding Geek codinggee...@gmail.comwrote: Place N number from 1 to N, in 2N positions in such a way so that there are Exactly “n” number of cells between two placed locations of number “n”. Write a program to display numbers placed in this way. Example:- (1) One of the possible placement for 7 numbers in 14 positions is : 5 7 2 3 6 2 5 3 4 7 1 6 1 4 -- To Iterate is Human, To Recurse is Divine -- 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. -- **Regards * * bagana.bharatku...@gmail.com Bharat B | M.Tech II | Computer Science Engineering | IITM * * *Ph: +91 8056127652* -- 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.
Re: [algogeeks] Amazon Interview Question
thats a brute force solution... can u expalin the complexity..i think its O(n^2) and also there exist no solution for n 3 On Thu, Jan 19, 2012 at 3:36 PM, bharat b bagana.bharatku...@gmail.comwrote: @Neeraj : will u pls explain u'r logic ... On 1/19/12, NEERAJ KODDHAN neerajdc...@gmail.com wrote: int[] a = new int[2*n]; put(a, n); static void put(int[] a,int i){ if(i0){ for(int j=0;ja.length-i-1;j++){ if(a[j]==0 a[j+i+1]==0){ a[j]=i; a[j+i+1]=i; put(a, i-1); a[j]=0; a[j+i+1]=0; } } }else if(i==0){ for (int k : a) { System.out.print(k + ); } System.out.println(); } } On Wed, Jan 18, 2012 at 10:04 PM, Coding Geek codinggee...@gmail.com wrote: Place N number from 1 to N, in 2N positions in such a way so that there are Exactly “n” number of cells between two placed locations of number “n”. Write a program to display numbers placed in this way. Example:- (1) One of the possible placement for 7 numbers in 14 positions is : 5 7 2 3 6 2 5 3 4 7 1 6 1 4 -- To Iterate is Human, To Recurse is Divine -- 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. -- **Regards * * bagana.bharatku...@gmail.com Bharat B | M.Tech II | Computer Science Engineering | IITM * * *Ph: +91 8056127652* -- 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. -- Regards Aditya Kumar B-tech IV year Computer Science Engg. MNNIT, Allahabad. -- 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.
Re: [algogeeks] Amazon Interview Question
ignore my last comment.. misunderstood On Thu, Jan 19, 2012 at 1:04 PM, Prakash D cegprak...@gmail.com wrote: why can't u simply place it as 1 2 3 4 5 6 7 1 2 3 4 5 6 7? On Thu, Jan 19, 2012 at 2:05 AM, NEERAJ KODDHAN neerajdc...@gmail.comwrote: int[] a = new int[2*n]; put(a, n); static void put(int[] a,int i){ if(i0){ for(int j=0;ja.length-i-1;j++){ if(a[j]==0 a[j+i+1]==0){ a[j]=i; a[j+i+1]=i; put(a, i-1); a[j]=0; a[j+i+1]=0; } } }else if(i==0){ for (int k : a) { System.out.print(k + ); } System.out.println(); } } On Wed, Jan 18, 2012 at 10:04 PM, Coding Geek codinggee...@gmail.comwrote: Place N number from 1 to N, in 2N positions in such a way so that there are Exactly “n” number of cells between two placed locations of number “n”. Write a program to display numbers placed in this way. Example:- (1) One of the possible placement for 7 numbers in 14 positions is : 5 7 2 3 6 2 5 3 4 7 1 6 1 4 -- To Iterate is Human, To Recurse is Divine -- 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. -- 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.
Re: [algogeeks] Amazon Interview Question
why can't u simply place it as 1 2 3 4 5 6 7 1 2 3 4 5 6 7? On Thu, Jan 19, 2012 at 2:05 AM, NEERAJ KODDHAN neerajdc...@gmail.comwrote: int[] a = new int[2*n]; put(a, n); static void put(int[] a,int i){ if(i0){ for(int j=0;ja.length-i-1;j++){ if(a[j]==0 a[j+i+1]==0){ a[j]=i; a[j+i+1]=i; put(a, i-1); a[j]=0; a[j+i+1]=0; } } }else if(i==0){ for (int k : a) { System.out.print(k + ); } System.out.println(); } } On Wed, Jan 18, 2012 at 10:04 PM, Coding Geek codinggee...@gmail.comwrote: Place N number from 1 to N, in 2N positions in such a way so that there are Exactly “n” number of cells between two placed locations of number “n”. Write a program to display numbers placed in this way. Example:- (1) One of the possible placement for 7 numbers in 14 positions is : 5 7 2 3 6 2 5 3 4 7 1 6 1 4 -- To Iterate is Human, To Recurse is Divine -- 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. -- 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.
Re: [algogeeks] Amazon Interview Question
@Neeraj Thanx for providing the algo On Thu, Jan 19, 2012 at 7:18 PM, rahul patil rahul.deshmukhpa...@gmail.comwrote: Looks like classic example of backtrack !!! On Thu, Jan 19, 2012 at 1:05 PM, Prakash D cegprak...@gmail.com wrote: ignore my last comment.. misunderstood On Thu, Jan 19, 2012 at 1:04 PM, Prakash D cegprak...@gmail.com wrote: why can't u simply place it as 1 2 3 4 5 6 7 1 2 3 4 5 6 7? On Thu, Jan 19, 2012 at 2:05 AM, NEERAJ KODDHAN neerajdc...@gmail.comwrote: int[] a = new int[2*n]; put(a, n); static void put(int[] a,int i){ if(i0){ for(int j=0;ja.length-i-1;j++){ if(a[j]==0 a[j+i+1]==0){ a[j]=i; a[j+i+1]=i; put(a, i-1); a[j]=0; a[j+i+1]=0; } } }else if(i==0){ for (int k : a) { System.out.print(k + ); } System.out.println(); } } On Wed, Jan 18, 2012 at 10:04 PM, Coding Geek codinggee...@gmail.comwrote: Place N number from 1 to N, in 2N positions in such a way so that there are Exactly “n” number of cells between two placed locations of number “n”. Write a program to display numbers placed in this way. Example:- (1) One of the possible placement for 7 numbers in 14 positions is : 5 7 2 3 6 2 5 3 4 7 1 6 1 4 -- To Iterate is Human, To Recurse is Divine -- 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. -- 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. -- Regards, Rahul Patil -- 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.
Re: [algogeeks] Amazon Interview Question
Coding Geek, if you have understood the algo provided by Neeraj, request you to explain the logic please. Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Thu, Jan 19, 2012 at 8:03 PM, Coding Geek codinggee...@gmail.com wrote: @Neeraj Thanx for providing the algo On Thu, Jan 19, 2012 at 7:18 PM, rahul patil rahul.deshmukhpa...@gmail.com wrote: Looks like classic example of backtrack !!! On Thu, Jan 19, 2012 at 1:05 PM, Prakash D cegprak...@gmail.com wrote: ignore my last comment.. misunderstood On Thu, Jan 19, 2012 at 1:04 PM, Prakash D cegprak...@gmail.com wrote: why can't u simply place it as 1 2 3 4 5 6 7 1 2 3 4 5 6 7? On Thu, Jan 19, 2012 at 2:05 AM, NEERAJ KODDHAN neerajdc...@gmail.comwrote: int[] a = new int[2*n]; put(a, n); static void put(int[] a,int i){ if(i0){ for(int j=0;ja.length-i-1;j++){ if(a[j]==0 a[j+i+1]==0){ a[j]=i; a[j+i+1]=i; put(a, i-1); a[j]=0; a[j+i+1]=0; } } }else if(i==0){ for (int k : a) { System.out.print(k + ); } System.out.println(); } } On Wed, Jan 18, 2012 at 10:04 PM, Coding Geek codinggee...@gmail.comwrote: Place N number from 1 to N, in 2N positions in such a way so that there are Exactly “n” number of cells between two placed locations of number “n”. Write a program to display numbers placed in this way. Example:- (1) One of the possible placement for 7 numbers in 14 positions is : 5 7 2 3 6 2 5 3 4 7 1 6 1 4 -- To Iterate is Human, To Recurse is Divine -- 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. -- 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. -- Regards, Rahul Patil -- 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. -- 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.
Re: [algogeeks] Amazon Interview Question
@ Neeraj: Plz explain ur logic. -- Ravi Shankar MCA 2nd Year Department Of Computer Science University Of Delhi -- 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.
Re: [algogeeks] Amazon Interview Question
@all : if see the code closely ...logic is simple. code is just trying many permutation to find an answer. say input = 6 now assuming that 6 will be placed at position arr[i] and arr[j+i+1] . it will put that value and move further to find next possible location for input-1; at any point of time if condition doesnt satify then we backtrack making arr[i] and ar[ j+ i +1 ] to 0 . and find another permulation. add for (int k : a) { System.out.print(k + ); } inside if() condition in the given code and run this prog. you will get an idea how it working. On Fri, Jan 20, 2012 at 1:39 AM, RaviShankar Kushwaha ravishuni...@gmail.com wrote: @ Neeraj: Plz explain ur logic. -- Ravi Shankar MCA 2nd Year Department Of Computer Science University Of Delhi -- 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.
Re: [algogeeks] Amazon Interview Question
@all Please check the Backtracking examples at http://www.geeksforgeeks.org/archives/tag/backtracking. You will understand the logic. In this examples first we fix a no. onto some position. After we check for other no. if any of the no. do not fit according to property we move back and reset all the changes made. Then we move our first fixed no. to some advance position and again check for the same. We repeat until we find a Sol. Thanx, -- To Iterate is Human, To Recurse is Divine -- 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.
[algogeeks] Amazon Interview Question
Place N number from 1 to N, in 2N positions in such a way so that there are Exactly “n” number of cells between two placed locations of number “n”. Write a program to display numbers placed in this way. Example:- (1) One of the possible placement for 7 numbers in 14 positions is : 5 7 2 3 6 2 5 3 4 7 1 6 1 4 -- To Iterate is Human, To Recurse is Divine -- 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.
Re: [algogeeks] Amazon Interview Question
int[] a = new int[2*n]; put(a, n); static void put(int[] a,int i){ if(i0){ for(int j=0;ja.length-i-1;j++){ if(a[j]==0 a[j+i+1]==0){ a[j]=i; a[j+i+1]=i; put(a, i-1); a[j]=0; a[j+i+1]=0; } } }else if(i==0){ for (int k : a) { System.out.print(k + ); } System.out.println(); } } On Wed, Jan 18, 2012 at 10:04 PM, Coding Geek codinggee...@gmail.comwrote: Place N number from 1 to N, in 2N positions in such a way so that there are Exactly “n” number of cells between two placed locations of number “n”. Write a program to display numbers placed in this way. Example:- (1) One of the possible placement for 7 numbers in 14 positions is : 5 7 2 3 6 2 5 3 4 7 1 6 1 4 -- To Iterate is Human, To Recurse is Divine -- 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.
Re: [algogeeks] Amazon Interview Question
@utkarsh: in yr code it shud be two-- after the swap function and not before for case 2 On Thu, Nov 10, 2011 at 1:25 PM, UTKARSH SRIVASTAV usrivastav...@gmail.comwrote: sorry it was incomplete On Fri, Nov 11, 2011 at 2:53 AM, UTKARSH SRIVASTAV usrivastav...@gmail.com wrote: one = zero = 0; two = n-1; //n is length of string while(two=one) { switch(a[one]) { case '0' : swap(a[zero],z[one]); one++;zero++;break; case '1' : one++; break; case '2' : two--; swap(a[one],a[two]); } } On Mon, Oct 24, 2011 at 9:50 PM, praveen raj praveen0...@gmail.comwrote: This can be done in O(n).. first shift all the 2's to the right side in O(n)... then again shift 1to the right shift b efore 2's. in O(n)... With regards, Praveen Raj DCE-IT 3rd yr 735993 praveen0...@gmail.com On Mon, Sep 26, 2011 at 6:23 PM, Naren s sweetna...@gmail.com wrote: dutch national flag problem..search in wiki...classical. On Sat, Sep 24, 2011 at 9:39 AM, VIHARRI viharri@gmail.com wrote: You are given a string (consisting of 0's, 1's or 2's) where 0 represents a blue ball, 1 a red ball, and 2 a black ball. Using only swap operations (counting sort not allowed) rearrange the string such that all blue balls are together on one side, followed by all red balls, and then all black balls. You can iterate through the string only once. Eg 102112011 should produce 00122 -- 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. -- *Narayanan S,* B.E., C.S.E., (final year), College Of Engineering Guindy, Anna University, Chennai-25. -- 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. -- *UTKARSH SRIVASTAV CSE-3 B-Tech 3rd Year @MNNIT ALLAHABAD* -- *UTKARSH SRIVASTAV CSE-3 B-Tech 3rd Year @MNNIT ALLAHABAD* -- 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. -- People often say that motivation doesn't last. Well, neither does bathing - that's why we recommend it daily. -- 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.
Re: [algogeeks] Amazon Interview Question
also I dont think that for case 0 we do not need to have one ++. I guess it fails for this example 2200101 On Mon, Jan 2, 2012 at 5:36 PM, Arun Vishwanathan aaron.nar...@gmail.comwrote: @utkarsh: in yr code it shud be two-- after the swap function and not before for case 2 On Thu, Nov 10, 2011 at 1:25 PM, UTKARSH SRIVASTAV usrivastav...@gmail.com wrote: sorry it was incomplete On Fri, Nov 11, 2011 at 2:53 AM, UTKARSH SRIVASTAV usrivastav...@gmail.com wrote: one = zero = 0; two = n-1; //n is length of string while(two=one) { switch(a[one]) { case '0' : swap(a[zero],z[one]); one++;zero++;break; case '1' : one++; break; case '2' : two--; swap(a[one],a[two]); } } On Mon, Oct 24, 2011 at 9:50 PM, praveen raj praveen0...@gmail.comwrote: This can be done in O(n).. first shift all the 2's to the right side in O(n)... then again shift 1to the right shift b efore 2's. in O(n)... With regards, Praveen Raj DCE-IT 3rd yr 735993 praveen0...@gmail.com On Mon, Sep 26, 2011 at 6:23 PM, Naren s sweetna...@gmail.com wrote: dutch national flag problem..search in wiki...classical. On Sat, Sep 24, 2011 at 9:39 AM, VIHARRI viharri@gmail.comwrote: You are given a string (consisting of 0's, 1's or 2's) where 0 represents a blue ball, 1 a red ball, and 2 a black ball. Using only swap operations (counting sort not allowed) rearrange the string such that all blue balls are together on one side, followed by all red balls, and then all black balls. You can iterate through the string only once. Eg 102112011 should produce 00122 -- 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. -- *Narayanan S,* B.E., C.S.E., (final year), College Of Engineering Guindy, Anna University, Chennai-25. -- 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. -- *UTKARSH SRIVASTAV CSE-3 B-Tech 3rd Year @MNNIT ALLAHABAD* -- *UTKARSH SRIVASTAV CSE-3 B-Tech 3rd Year @MNNIT ALLAHABAD* -- 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. -- People often say that motivation doesn't last. Well, neither does bathing - that's why we recommend it daily. -- People often say that motivation doesn't last. Well, neither does bathing - that's why we recommend it daily. -- 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.
[algogeeks] Amazon interview
Hi Has anyone appeared for interview in Amazon India? Could anyone please suggest how the interview pattern is? What are the best URL's where we can find good material to prepare for the interview? Any sample interview questions would really help. Thanks -- 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.
Re: [algogeeks] Amazon Interview Question
I think smallest will be having just one character . it can be a or b or c. On Sat, Nov 12, 2011 at 3:07 PM, Snoopy Me thesnoop...@gmail.com wrote: Given a string consisting of a,b and c's, we can perform the following operation: Take any two adjacent distinct characters and replace it with the third character. For example, if 'a' and 'c' are adjacent, they can replaced with 'b'. What is the smallest string which can result by applying this operation repeatedly? -- 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.
[algogeeks] Amazon Interview Question
Given a string consisting of a,b and c's, we can perform the following operation: Take any two adjacent distinct characters and replace it with the third character. For example, if 'a' and 'c' are adjacent, they can replaced with 'b'. What is the smallest string which can result by applying this operation repeatedly? -- 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.
Re: [algogeeks] Amazon Interview Question
sorry it was incomplete On Fri, Nov 11, 2011 at 2:53 AM, UTKARSH SRIVASTAV usrivastav...@gmail.comwrote: one = zero = 0; two = n-1; //n is length of string while(two=one) { switch(a[one]) { case '0' : swap(a[zero],z[one]); one++;zero++;break; case '1' : one++; break; case '2' : two--; swap(a[one],a[two]); } } On Mon, Oct 24, 2011 at 9:50 PM, praveen raj praveen0...@gmail.comwrote: This can be done in O(n).. first shift all the 2's to the right side in O(n)... then again shift 1to the right shift b efore 2's. in O(n)... With regards, Praveen Raj DCE-IT 3rd yr 735993 praveen0...@gmail.com On Mon, Sep 26, 2011 at 6:23 PM, Naren s sweetna...@gmail.com wrote: dutch national flag problem..search in wiki...classical. On Sat, Sep 24, 2011 at 9:39 AM, VIHARRI viharri@gmail.com wrote: You are given a string (consisting of 0's, 1's or 2's) where 0 represents a blue ball, 1 a red ball, and 2 a black ball. Using only swap operations (counting sort not allowed) rearrange the string such that all blue balls are together on one side, followed by all red balls, and then all black balls. You can iterate through the string only once. Eg 102112011 should produce 00122 -- 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. -- *Narayanan S,* B.E., C.S.E., (final year), College Of Engineering Guindy, Anna University, Chennai-25. -- 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. -- *UTKARSH SRIVASTAV CSE-3 B-Tech 3rd Year @MNNIT ALLAHABAD* -- *UTKARSH SRIVASTAV CSE-3 B-Tech 3rd Year @MNNIT ALLAHABAD* -- 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.
Re: [algogeeks] Amazon Interview Question
one = zero = 0; two = n-1; //n is length of string while(two=one) { switch(a[one]) On Mon, Oct 24, 2011 at 9:50 PM, praveen raj praveen0...@gmail.com wrote: This can be done in O(n).. first shift all the 2's to the right side in O(n)... then again shift 1to the right shift b efore 2's. in O(n)... With regards, Praveen Raj DCE-IT 3rd yr 735993 praveen0...@gmail.com On Mon, Sep 26, 2011 at 6:23 PM, Naren s sweetna...@gmail.com wrote: dutch national flag problem..search in wiki...classical. On Sat, Sep 24, 2011 at 9:39 AM, VIHARRI viharri@gmail.com wrote: You are given a string (consisting of 0's, 1's or 2's) where 0 represents a blue ball, 1 a red ball, and 2 a black ball. Using only swap operations (counting sort not allowed) rearrange the string such that all blue balls are together on one side, followed by all red balls, and then all black balls. You can iterate through the string only once. Eg 102112011 should produce 00122 -- 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. -- *Narayanan S,* B.E., C.S.E., (final year), College Of Engineering Guindy, Anna University, Chennai-25. -- 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. -- *UTKARSH SRIVASTAV CSE-3 B-Tech 3rd Year @MNNIT ALLAHABAD* -- 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.
Re: [algogeeks] Amazon Interview Question
count the number of 0s 1s 2s.then store os first den 1s followed by 2s On Sat, Sep 24, 2011 at 9:55 AM, Anup Ghatage ghat...@gmail.com wrote: Is this like the segregating all the 1's to the right and the 0's to the left or am i missing something? On Sat, Sep 24, 2011 at 9:39 AM, VIHARRI viharri@gmail.com wrote: You are given a string (consisting of 0's, 1's or 2's) where 0 represents a blue ball, 1 a red ball, and 2 a black ball. Using only swap operations (counting sort not allowed) rearrange the string such that all blue balls are together on one side, followed by all red balls, and then all black balls. You can iterate through the string only once. Eg 102112011 should produce 00122? -- 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. -- Anup Ghatage -- 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.
Re: [algogeeks] Amazon Interview Question
dutch national flag problem..search in wiki...classical. On Sat, Sep 24, 2011 at 9:39 AM, VIHARRI viharri@gmail.com wrote: You are given a string (consisting of 0's, 1's or 2's) where 0 represents a blue ball, 1 a red ball, and 2 a black ball. Using only swap operations (counting sort not allowed) rearrange the string such that all blue balls are together on one side, followed by all red balls, and then all black balls. You can iterate through the string only once. Eg 102112011 should produce 00122 -- 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. -- *Narayanan S,* B.E., C.S.E., (final year), College Of Engineering Guindy, Anna University, Chennai-25. -- 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.
Re: [algogeeks] Amazon Interview Question
we cant traverse the string twice... if there is an error in my logic then plz tell my logic is: we have to take starting and ending indexes for '0','1','2' like below 0 1 2 starting_index ending_index now suppose our string 102112011 so we start from the left and traverse the whole string first character ='1' 0 1 2 starting_index 0 ending_index 0 next character = '0' 0 1 2 starting_index 1 0 ending_index 1 0 ( ending_index0 ending_index1 ) so we swap the numbers according to Starting_index not according to Ending_index So it will become 0 1 2 starting_index 0 1 ending_index 0 1 and string will become 01 next character '2' 0 1 2 starting_index 0 1 2 ending_index 0 1 2 (ending_index0ending_index1ending_index2)so ending indexes in increasing order...so no need to swap so string is now 012 next character '1' 0 1 2 starting_index 0 1 2 ending_index 0 3 2 (ending_index1ending_index2) so we swap the current 1 with starting index of 2 so string will become 0112 0 1 2 starting_index 0 1 3 ending_index 0 2 3 next character '1' 0 1 2 starting_index 0 1 3 ending_index 0 4 3 (ending_index1ending_index2) so we swap the current 1 with starting index of 2 so string will become 01112 0 1 2 starting_index 0 1 4 ending_index 0 3 4 next character '2' 0 1 2 starting_index 0 1 4 ending_index 0 3 5 (ending_index0ending_index1ending_index2) so no swap so string will become 011122 next character '0' 0 1 2 starting_index 0 1 4 ending_index 6 3 5 (ending_index0ending_index1ending_index2) so we swap the current 0 with staring index of 2 first and then with starting index of 1 so string will become 0011122 0 1 2 starting_index 0 2 5 ending_index 1 4 6 and so on i hope its much explained... On Sat, Sep 24, 2011 at 10:30 AM, Dheeraj Sharma dheerajsharma1...@gmail.com wrote: char str[100],t; scanf(%s,str); char ch='0'; int i=0,j=0; while(jstrlen(str)) { if(str[j]==ch) { SWAP(str[i],str[j],t); i++; } j++; } ch='1'; j=i; while(jstrlen(str)) { if(str[j]==ch) { SWAP(str[i],str[j],t); i++; } j++; } printf(%s\n,str); On Sat, Sep 24, 2011 at 9:55 AM, Anup Ghatage ghat...@gmail.com wrote: Is this like the segregating all the 1's to the right and the 0's to the left or am i missing something? On Sat, Sep 24, 2011 at 9:39 AM, VIHARRI viharri@gmail.com wrote: You are given a string (consisting of 0's, 1's or 2's) where 0 represents a blue ball, 1 a red ball, and 2 a black ball. Using only swap operations (counting sort not allowed) rearrange the string such that all blue balls are together on one side, followed by all red balls, and then all black balls. You can iterate through the string only once. Eg 102112011 should produce 00122? -- 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. -- Anup Ghatage -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to
Re: [algogeeks] Amazon Interview Question
i think this travels only once ... correct me if am wrong #includestdio.h #includestring.h #define SWAP(a,b,c) (c)=(a),(a)=(b),(b)=(c) int main() { int t,x; scanf(%d,t); while(t--) { char str[100]; scanf(%s,str); int i=0,j=0,k=strlen(str)-1; while(str[i]=='0') i++; while(str[k]=='2') k--; j=i; while(j=k) { if(str[j]=='2') { SWAP(str[j],str[k],x); k--; } if(str[j]=='0') { SWAP(str[i],str[j],x); i++; } if(str[j]!='2') j++; } printf(%s\n,str); } return 0; } On Sat, Sep 24, 2011 at 11:39 AM, Yogesh Yadav medu...@gmail.com wrote: we cant traverse the string twice... if there is an error in my logic then plz tell my logic is: we have to take starting and ending indexes for '0','1','2' like below 0 1 2 starting_index ending_index now suppose our string 102112011 so we start from the left and traverse the whole string first character ='1' 0 1 2 starting_index 0 ending_index 0 next character = '0' 0 1 2 starting_index 1 0 ending_index 1 0 ( ending_index0 ending_index1 ) so we swap the numbers according to Starting_index not according to Ending_index So it will become 0 1 2 starting_index 0 1 ending_index 0 1 and string will become 01 next character '2' 0 1 2 starting_index 0 1 2 ending_index 0 1 2 (ending_index0ending_index1ending_index2)so ending indexes in increasing order...so no need to swap so string is now 012 next character '1' 0 1 2 starting_index 0 1 2 ending_index 0 3 2 (ending_index1ending_index2) so we swap the current 1 with starting index of 2 so string will become 0112 0 1 2 starting_index 0 1 3 ending_index 0 2 3 next character '1' 0 1 2 starting_index 0 1 3 ending_index 0 4 3 (ending_index1ending_index2) so we swap the current 1 with starting index of 2 so string will become 01112 0 1 2 starting_index 0 1 4 ending_index 0 3 4 next character '2' 0 1 2 starting_index 0 1 4 ending_index 0 3 5 (ending_index0ending_index1ending_index2) so no swap so string will become 011122 next character '0' 0 1 2 starting_index 0 1 4 ending_index 6 3 5 (ending_index0ending_index1ending_index2) so we swap the current 0 with staring index of 2 first and then with starting index of 1 so string will become 0011122 0 1 2 starting_index 0 2 5 ending_index 1 4 6 and so on i hope its much explained... On Sat, Sep 24, 2011 at 10:30 AM, Dheeraj Sharma dheerajsharma1...@gmail.com wrote: char str[100],t; scanf(%s,str); char ch='0'; int i=0,j=0; while(jstrlen(str)) { if(str[j]==ch) { SWAP(str[i],str[j],t); i++; } j++; } ch='1'; j=i; while(jstrlen(str)) { if(str[j]==ch) { SWAP(str[i],str[j],t); i++; } j++; } printf(%s\n,str);
Re: [algogeeks] Amazon Interview Question
dutch national flag problem :) On Sat, Sep 24, 2011 at 3:45 PM, Dheeraj Sharma dheerajsharma1...@gmail.com wrote: i think this travels only once ... correct me if am wrong #includestdio.h #includestring.h #define SWAP(a,b,c) (c)=(a),(a)=(b),(b)=(c) int main() { int t,x; scanf(%d,t); while(t--) { char str[100]; scanf(%s,str); int i=0,j=0,k=strlen(str)-1; while(str[i]=='0') i++; while(str[k]=='2') k--; j=i; while(j=k) { if(str[j]=='2') { SWAP(str[j],str[k],x); k--; } if(str[j]=='0') { SWAP(str[i],str[j],x); i++; } if(str[j]!='2') j++; } printf(%s\n,str); } return 0; } On Sat, Sep 24, 2011 at 11:39 AM, Yogesh Yadav medu...@gmail.com wrote: we cant traverse the string twice... if there is an error in my logic then plz tell my logic is: we have to take starting and ending indexes for '0','1','2' like below 0 1 2 starting_index ending_index now suppose our string 102112011 so we start from the left and traverse the whole string first character ='1' 0 1 2 starting_index 0 ending_index 0 next character = '0' 0 1 2 starting_index 1 0 ending_index 1 0 ( ending_index0 ending_index1 ) so we swap the numbers according to Starting_index not according to Ending_index So it will become 0 1 2 starting_index 0 1 ending_index 0 1 and string will become 01 next character '2' 0 1 2 starting_index 0 1 2 ending_index 0 1 2 (ending_index0ending_index1ending_index2)so ending indexes in increasing order...so no need to swap so string is now 012 next character '1' 0 1 2 starting_index 0 1 2 ending_index 0 3 2 (ending_index1ending_index2) so we swap the current 1 with starting index of 2 so string will become 0112 0 1 2 starting_index 0 1 3 ending_index 0 2 3 next character '1' 0 1 2 starting_index 0 1 3 ending_index 0 4 3 (ending_index1ending_index2) so we swap the current 1 with starting index of 2 so string will become 01112 0 1 2 starting_index 0 1 4 ending_index 0 3 4 next character '2' 0 1 2 starting_index 0 1 4 ending_index 0 3 5 (ending_index0ending_index1ending_index2) so no swap so string will become 011122 next character '0' 0 1 2 starting_index 0 1 4 ending_index 6 3 5 (ending_index0ending_index1ending_index2) so we swap the current 0 with staring index of 2 first and then with starting index of 1 so string will become 0011122 0 1 2 starting_index 0 2 5 ending_index 1 4 6 and so on i hope its much explained... On Sat, Sep 24, 2011 at 10:30 AM, Dheeraj Sharma dheerajsharma1...@gmail.com wrote: char str[100],t; scanf(%s,str); char ch='0'; int i=0,j=0; while(jstrlen(str)) { if(str[j]==ch) { SWAP(str[i],str[j],t); i++; } j++; } ch='1'; j=i; while(jstrlen(str)) { if(str[j]==ch) { SWAP(str[i],str[j],t);
Re: [algogeeks] Amazon Interview Question
I think this will do the same: - #include stdafx.h #include stdlib.h void swap(int *a, int start, int end) { int temp; temp = *(a + start); *(a + start) = *(a + end); *(a + end) = temp; } int _tmain(int argc, _TCHAR* argv[]) { int minIndex=0, maxIndex=8; int i=1; int a[9] ={1,0,2,1,0,2,0,0,1}; while(imaxIndex) { if(a[maxIndex] == 2) maxIndex--; if(a[minIndex] == 0) minIndex++; if(a[i] a[maxIndex]) { swap(a, i, maxIndex); continue; } else if (a[i] a[minIndex]) { swap(a, i, minIndex); continue; } i++; } for (i =0 ; i 9; i++) printf([%d], a[i]); system(PAUSE); return 0; } Please comment. Cheers, Ankit Sinha On Sat, Sep 24, 2011 at 4:10 PM, malay chakrabarti m1234...@gmail.com wrote: dutch national flag problem :) On Sat, Sep 24, 2011 at 3:45 PM, Dheeraj Sharma dheerajsharma1...@gmail.com wrote: i think this travels only once ... correct me if am wrong #includestdio.h #includestring.h #define SWAP(a,b,c) (c)=(a),(a)=(b),(b)=(c) int main() { int t,x; scanf(%d,t); while(t--) { char str[100]; scanf(%s,str); int i=0,j=0,k=strlen(str)-1; while(str[i]=='0') i++; while(str[k]=='2') k--; j=i; while(j=k) { if(str[j]=='2') { SWAP(str[j],str[k],x); k--; } if(str[j]=='0') { SWAP(str[i],str[j],x); i++; } if(str[j]!='2') j++; } printf(%s\n,str); } return 0; } On Sat, Sep 24, 2011 at 11:39 AM, Yogesh Yadav medu...@gmail.com wrote: we cant traverse the string twice... if there is an error in my logic then plz tell my logic is: we have to take starting and ending indexes for '0','1','2' like below 0 1 2 starting_index ending_index now suppose our string 102112011 so we start from the left and traverse the whole string first character ='1' 0 1 2 starting_index 0 ending_index 0 next character = '0' 0 1 2 starting_index 1 0 ending_index 1 0 ( ending_index0 ending_index1 ) so we swap the numbers according to Starting_index not according to Ending_index So it will become 0 1 2 starting_index 0 1 ending_index 0 1 and string will become 01 next character '2' 0 1 2 starting_index 0 1 2 ending_index 0 1 2 (ending_index0ending_index1ending_index2) so ending indexes in increasing order...so no need to swap so string is now 012 next character '1' 0 1 2 starting_index 0 1 2 ending_index 0 3 2 (ending_index1ending_index2) so we swap the current 1 with starting index of 2 so string will become 0112 0 1 2 starting_index 0 1 3 ending_index 0 2 3 next character '1' 0 1 2 starting_index 0 1 3 ending_index 0 4 3 (ending_index1ending_index2) so we swap the current 1 with starting index of 2 so string will become 01112 0 1 2 starting_index 0 1 4 ending_index 0 3 4 next character '2' 0 1 2 starting_index 0 1 4 ending_index 0 3 5 (ending_index0ending_index1ending_index2) so no swap so string will become 011122 next character '0' 0 1 2 starting_index 0 1 4 ending_index 6 3 5 (ending_index0ending_index1ending_index2) so we swap the current 0 with
Re: [algogeeks] Amazon Interview Question
void sort012(int a[],int n){ int i = 0, s = 0, last = n-1; while(i=last){ if(a[i] == 0 i!=s) { swap(a[i], a[s]); s++; } else if(a[i] == 2 i!=last) { swap(a[i], a[last]); last--; } else i++; } } On Sat, Sep 24, 2011 at 5:13 PM, Ankit Sinha akki12...@gmail.com wrote: I think this will do the same: - #include stdafx.h #include stdlib.h void swap(int *a, int start, int end) { int temp; temp = *(a + start); *(a + start) = *(a + end); *(a + end) = temp; } int _tmain(int argc, _TCHAR* argv[]) { int minIndex=0, maxIndex=8; int i=1; int a[9] ={1,0,2,1,0,2,0,0,1}; while(imaxIndex) { if(a[maxIndex] == 2) maxIndex--; if(a[minIndex] == 0) minIndex++; if(a[i] a[maxIndex]) { swap(a, i, maxIndex); continue; } else if (a[i] a[minIndex]) { swap(a, i, minIndex); continue; } i++; } for (i =0 ; i 9; i++) printf([%d], a[i]); system(PAUSE); return 0; } Please comment. Cheers, Ankit Sinha On Sat, Sep 24, 2011 at 4:10 PM, malay chakrabarti m1234...@gmail.com wrote: dutch national flag problem :) On Sat, Sep 24, 2011 at 3:45 PM, Dheeraj Sharma dheerajsharma1...@gmail.com wrote: i think this travels only once ... correct me if am wrong #includestdio.h #includestring.h #define SWAP(a,b,c) (c)=(a),(a)=(b),(b)=(c) int main() { int t,x; scanf(%d,t); while(t--) { char str[100]; scanf(%s,str); int i=0,j=0,k=strlen(str)-1; while(str[i]=='0') i++; while(str[k]=='2') k--; j=i; while(j=k) { if(str[j]=='2') { SWAP(str[j],str[k],x); k--; } if(str[j]=='0') { SWAP(str[i],str[j],x); i++; } if(str[j]!='2') j++; } printf(%s\n,str); } return 0; } On Sat, Sep 24, 2011 at 11:39 AM, Yogesh Yadav medu...@gmail.com wrote: we cant traverse the string twice... if there is an error in my logic then plz tell my logic is: we have to take starting and ending indexes for '0','1','2' like below 0 1 2 starting_index ending_index now suppose our string 102112011 so we start from the left and traverse the whole string first character ='1' 0 1 2 starting_index 0 ending_index 0 next character = '0' 0 1 2 starting_index 1 0 ending_index 1 0 ( ending_index0 ending_index1 ) so we swap the numbers according to Starting_index not according to Ending_index So it will become 0 1 2 starting_index 0 1 ending_index 0 1 and string will become 01 next character '2' 0 1 2 starting_index 0 1 2 ending_index 0 1 2 (ending_index0ending_index1ending_index2)so ending indexes in increasing order...so no need to swap so string is now 012 next character '1' 0 1 2 starting_index 0 1 2 ending_index 0 3 2 (ending_index1ending_index2) so we swap the current 1 with starting index of 2 so string will become 0112 0 1 2 starting_index 0 1 3 ending_index 0 2 3 next character '1' 0 1 2 starting_index 0 1 3 ending_index 0 4 3 (ending_index1ending_index2) so we swap the current 1 with starting index of 2 so string will become 01112 0 1 2 starting_index 0 1 4 ending_index 0 3 4 next character '2'
Re: [algogeeks] Amazon Interview Question
Classic problem http://en.wikipedia.org/wiki/Dutch_national_flag_problem On Sat, Sep 24, 2011 at 5:15 PM, Ankur Garg ankurga...@gmail.com wrote: void sort012(int a[],int n){ int i = 0, s = 0, last = n-1; while(i=last){ if(a[i] == 0 i!=s) { swap(a[i], a[s]); s++; } else if(a[i] == 2 i!=last) { swap(a[i], a[last]); last--; } else i++; } } On Sat, Sep 24, 2011 at 5:13 PM, Ankit Sinha akki12...@gmail.com wrote: I think this will do the same: - #include stdafx.h #include stdlib.h void swap(int *a, int start, int end) { int temp; temp = *(a + start); *(a + start) = *(a + end); *(a + end) = temp; } int _tmain(int argc, _TCHAR* argv[]) { int minIndex=0, maxIndex=8; int i=1; int a[9] ={1,0,2,1,0,2,0,0,1}; while(imaxIndex) { if(a[maxIndex] == 2) maxIndex--; if(a[minIndex] == 0) minIndex++; if(a[i] a[maxIndex]) { swap(a, i, maxIndex); continue; } else if (a[i] a[minIndex]) { swap(a, i, minIndex); continue; } i++; } for (i =0 ; i 9; i++) printf([%d], a[i]); system(PAUSE); return 0; } Please comment. Cheers, Ankit Sinha On Sat, Sep 24, 2011 at 4:10 PM, malay chakrabarti m1234...@gmail.com wrote: dutch national flag problem :) On Sat, Sep 24, 2011 at 3:45 PM, Dheeraj Sharma dheerajsharma1...@gmail.com wrote: i think this travels only once ... correct me if am wrong #includestdio.h #includestring.h #define SWAP(a,b,c) (c)=(a),(a)=(b),(b)=(c) int main() { int t,x; scanf(%d,t); while(t--) { char str[100]; scanf(%s,str); int i=0,j=0,k=strlen(str)-1; while(str[i]=='0') i++; while(str[k]=='2') k--; j=i; while(j=k) { if(str[j]=='2') { SWAP(str[j],str[k],x); k--; } if(str[j]=='0') { SWAP(str[i],str[j],x); i++; } if(str[j]!='2') j++; } printf(%s\n,str); } return 0; } On Sat, Sep 24, 2011 at 11:39 AM, Yogesh Yadav medu...@gmail.com wrote: we cant traverse the string twice... if there is an error in my logic then plz tell my logic is: we have to take starting and ending indexes for '0','1','2' like below 0 1 2 starting_index ending_index now suppose our string 102112011 so we start from the left and traverse the whole string first character ='1' 0 1 2 starting_index 0 ending_index 0 next character = '0' 0 1 2 starting_index 1 0 ending_index 1 0 ( ending_index0 ending_index1 ) so we swap the numbers according to Starting_index not according to Ending_index So it will become 0 1 2 starting_index 0 1 ending_index 0 1 and string will become 01 next character '2' 0 1 2 starting_index 0 1 2 ending_index 0 1 2 (ending_index0ending_index1ending_index2)so ending indexes in increasing order...so no need to swap so string is now 012 next character '1' 0 1 2 starting_index 0 1 2 ending_index 0 3 2 (ending_index1ending_index2) so we swap the current 1 with starting index of 2 so string will become 0112 0 1 2 starting_index 0 1 3 ending_index 0 2 3 next character '1' 0 1 2 starting_index 0 1 3 ending_index 0 4 3 (ending_index1ending_index2) so we swap the current 1 with starting index of 2 so string will become 01112
Re: [algogeeks] Amazon Interview Question
Keep two pointers - p1 and p2 p1 points at the index just after last 0 such that there are all zero's before it. p2 points at the entry just before last 2, and there are all 2's after it. *example*- 0010201201222 p1 = 2; p2 = 9; *Pseudo code - * p1 = 0; p2 = n-1; i = 0; while(in) if(A[i]) ==0) swap(p1,i); p1++; else if (A[i]==1) i++; else if(A[i]==2) swap (p2,i); p2--; On Sat, Sep 24, 2011 at 11:39 AM, Yogesh Yadav medu...@gmail.com wrote: we cant traverse the string twice... if there is an error in my logic then plz tell my logic is: we have to take starting and ending indexes for '0','1','2' like below 0 1 2 starting_index ending_index now suppose our string 102112011 so we start from the left and traverse the whole string first character ='1' 0 1 2 starting_index 0 ending_index 0 next character = '0' 0 1 2 starting_index 1 0 ending_index 1 0 ( ending_index0 ending_index1 ) so we swap the numbers according to Starting_index not according to Ending_index So it will become 0 1 2 starting_index 0 1 ending_index 0 1 and string will become 01 next character '2' 0 1 2 starting_index 0 1 2 ending_index 0 1 2 (ending_index0ending_index1ending_index2)so ending indexes in increasing order...so no need to swap so string is now 012 next character '1' 0 1 2 starting_index 0 1 2 ending_index 0 3 2 (ending_index1ending_index2) so we swap the current 1 with starting index of 2 so string will become 0112 0 1 2 starting_index 0 1 3 ending_index 0 2 3 next character '1' 0 1 2 starting_index 0 1 3 ending_index 0 4 3 (ending_index1ending_index2) so we swap the current 1 with starting index of 2 so string will become 01112 0 1 2 starting_index 0 1 4 ending_index 0 3 4 next character '2' 0 1 2 starting_index 0 1 4 ending_index 0 3 5 (ending_index0ending_index1ending_index2) so no swap so string will become 011122 next character '0' 0 1 2 starting_index 0 1 4 ending_index 6 3 5 (ending_index0ending_index1ending_index2) so we swap the current 0 with staring index of 2 first and then with starting index of 1 so string will become 0011122 0 1 2 starting_index 0 2 5 ending_index 1 4 6 and so on i hope its much explained... On Sat, Sep 24, 2011 at 10:30 AM, Dheeraj Sharma dheerajsharma1...@gmail.com wrote: char str[100],t; scanf(%s,str); char ch='0'; int i=0,j=0; while(jstrlen(str)) { if(str[j]==ch) { SWAP(str[i],str[j],t); i++; } j++; } ch='1'; j=i; while(jstrlen(str)) { if(str[j]==ch) { SWAP(str[i],str[j],t); i++; } j++; } printf(%s\n,str); On Sat, Sep 24, 2011 at 9:55 AM, Anup Ghatage ghat...@gmail.com wrote: Is this like the segregating all the 1's to the right and the 0's to the left or am i missing something? On Sat, Sep 24, 2011 at 9:39 AM, VIHARRI viharri@gmail.com wrote: You are given a string (consisting of 0's, 1's or 2's) where 0 represents a blue ball, 1 a red ball, and 2 a black ball. Using only swap operations (counting sort not allowed) rearrange the string such that all blue balls are together on one side, followed by all red balls, and then all black balls. You can iterate through the string only once. Eg 102112011 should
Re: [algogeeks] Amazon Interview Question
@guarav true @others no point in sending the code describe your logic... anyway link provided by guarav is suffice to solve the problem On Sat, Sep 24, 2011 at 5:26 PM, Gaurav Aggarwal gaurav91.2...@gmail.comwrote: Classic problem http://en.wikipedia.org/wiki/Dutch_national_flag_problem On Sat, Sep 24, 2011 at 5:15 PM, Ankur Garg ankurga...@gmail.com wrote: void sort012(int a[],int n){ int i = 0, s = 0, last = n-1; while(i=last){ if(a[i] == 0 i!=s) { swap(a[i], a[s]); s++; } else if(a[i] == 2 i!=last) { swap(a[i], a[last]); last--; } else i++; } } On Sat, Sep 24, 2011 at 5:13 PM, Ankit Sinha akki12...@gmail.com wrote: I think this will do the same: - #include stdafx.h #include stdlib.h void swap(int *a, int start, int end) { int temp; temp = *(a + start); *(a + start) = *(a + end); *(a + end) = temp; } int _tmain(int argc, _TCHAR* argv[]) { int minIndex=0, maxIndex=8; int i=1; int a[9] ={1,0,2,1,0,2,0,0,1}; while(imaxIndex) { if(a[maxIndex] == 2) maxIndex--; if(a[minIndex] == 0) minIndex++; if(a[i] a[maxIndex]) { swap(a, i, maxIndex); continue; } else if (a[i] a[minIndex]) { swap(a, i, minIndex); continue; } i++; } for (i =0 ; i 9; i++) printf([%d], a[i]); system(PAUSE); return 0; } Please comment. Cheers, Ankit Sinha On Sat, Sep 24, 2011 at 4:10 PM, malay chakrabarti m1234...@gmail.com wrote: dutch national flag problem :) On Sat, Sep 24, 2011 at 3:45 PM, Dheeraj Sharma dheerajsharma1...@gmail.com wrote: i think this travels only once ... correct me if am wrong #includestdio.h #includestring.h #define SWAP(a,b,c) (c)=(a),(a)=(b),(b)=(c) int main() { int t,x; scanf(%d,t); while(t--) { char str[100]; scanf(%s,str); int i=0,j=0,k=strlen(str)-1; while(str[i]=='0') i++; while(str[k]=='2') k--; j=i; while(j=k) { if(str[j]=='2') { SWAP(str[j],str[k],x); k--; } if(str[j]=='0') { SWAP(str[i],str[j],x); i++; } if(str[j]!='2') j++; } printf(%s\n,str); } return 0; } On Sat, Sep 24, 2011 at 11:39 AM, Yogesh Yadav medu...@gmail.com wrote: we cant traverse the string twice... if there is an error in my logic then plz tell my logic is: we have to take starting and ending indexes for '0','1','2' like below 0 1 2 starting_index ending_index now suppose our string 102112011 so we start from the left and traverse the whole string first character ='1' 0 1 2 starting_index 0 ending_index 0 next character = '0' 0 1 2 starting_index 1 0 ending_index 1 0 ( ending_index0 ending_index1 ) so we swap the numbers according to Starting_index not according to Ending_index So it will become 0 1 2 starting_index 0 1 ending_index 0 1 and string will become 01 next character '2' 0 1 2 starting_index 0 1 2 ending_index 0 1 2 (ending_index0ending_index1ending_index2)so ending indexes in increasing order...so no need to swap so string is now 012 next character '1' 0 1 2 starting_index 0 1 2 ending_index 0 3 2 (ending_index1ending_index2) so we swap the current 1 with starting index of 2 so string will become 0112 0 1 2 starting_index 0 1 3 ending_index 0 2 3 next character '1' 0 1
[algogeeks] Amazon Interview Question
You are given a string (consisting of 0's, 1's or 2's) where 0 represents a blue ball, 1 a red ball, and 2 a black ball. Using only swap operations (counting sort not allowed) rearrange the string such that all blue balls are together on one side, followed by all red balls, and then all black balls. You can iterate through the string only once. Eg 102112011 should produce 00122 -- 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.
Re: [algogeeks] Amazon Interview Question
Is this like the segregating all the 1's to the right and the 0's to the left or am i missing something? On Sat, Sep 24, 2011 at 9:39 AM, VIHARRI viharri@gmail.com wrote: You are given a string (consisting of 0's, 1's or 2's) where 0 represents a blue ball, 1 a red ball, and 2 a black ball. Using only swap operations (counting sort not allowed) rearrange the string such that all blue balls are together on one side, followed by all red balls, and then all black balls. You can iterate through the string only once. Eg 102112011 should produce 00122? -- 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. -- Anup Ghatage -- 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.
Re: [algogeeks] Amazon Interview Question
char str[100],t; scanf(%s,str); char ch='0'; int i=0,j=0; while(jstrlen(str)) { if(str[j]==ch) { SWAP(str[i],str[j],t); i++; } j++; } ch='1'; j=i; while(jstrlen(str)) { if(str[j]==ch) { SWAP(str[i],str[j],t); i++; } j++; } printf(%s\n,str); On Sat, Sep 24, 2011 at 9:55 AM, Anup Ghatage ghat...@gmail.com wrote: Is this like the segregating all the 1's to the right and the 0's to the left or am i missing something? On Sat, Sep 24, 2011 at 9:39 AM, VIHARRI viharri@gmail.com wrote: You are given a string (consisting of 0's, 1's or 2's) where 0 represents a blue ball, 1 a red ball, and 2 a black ball. Using only swap operations (counting sort not allowed) rearrange the string such that all blue balls are together on one side, followed by all red balls, and then all black balls. You can iterate through the string only once. Eg 102112011 should produce 00122? -- 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. -- Anup Ghatage -- 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. -- *Dheeraj Sharma* Comp Engg. NIT Kurukshetra -- 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.
[algogeeks] Amazon Interview Question
How much space does a pointer and integer takes? For eg :- int a; int *a; -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/RmPHywrTUbkJ. 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.
Re: [algogeeks] Amazon Interview Question
@Ravi +1 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/E0NIFwY150EJ. 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.
[algogeeks] Amazon Interview
Hi friends, Is there anyone who given the first telephonic round of Amazon recently. Please share the details with us. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/FVYRU6rdxH0J. 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.