Re: [algogeeks] Re: Amazon Interview Question
Counting sort does not run in O(1) space though. Optimally it will run in O(K) space, where A is an array of integer numbers and K = max(A) - min(A) On Saturday, February 9, 2013 9:52:01 PM UTC-5, Mohanabalan wrote: can use counting sort On Sun, Jul 15, 2012 at 6:37 PM, santosh thota santosh...@gmail.comjavascript: wrote: If we can retrieve ith prime efficiently, we can do the following... 1.maintain a prod=1, start from 1st element, say a[0]=n find n th prime 2.check if (prod% (ith_prime * ith_prime )==0) then return i; else prod=prod*ith_prime; 3.repeat it till end On Thursday, 12 July 2012 10:55:02 UTC+5:30, algo bard wrote: 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 view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/TSPSKlD0FDsJ. 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 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] Re: Amazon Interview Question
A bit vector is basically just a sequence of bits such as a word or even an array of words. Here is an example... int x = 5; // 32 bit word size on Intel IA-32 Architecture In C programming language. A variable in C will be either located in a register in memory or in Main Memory. You can even have bit vector data structures reside on the hard disk. It just looks like this 10010101010010101... If I'm interpreting the solution properly you will index into the bit vector based on the number found in the array A that is for j = 1... A.size currentNumber = A[j] // The jth array element bitVector[currentNumber] = ~ bitVector[currentNumber] ; // Toggle the currentNumber bit end for Although this is a big memory save, you're still not using constant memory because the size of your memory is dependent on the size of a word let's say k In worst case the space complexity will be 2*2^k = O(2^(K+1)) On Wednesday, April 3, 2013 9:58:23 AM UTC-8, ashekhar007 wrote: hi sourab please explain what bit vector1 and bit vector 2 really are can you give an example please? On Saturday, February 16, 2013 11:20:59 PM UTC+5:30, sourabh wrote: you can solve this problem using bitvector/bitset. first scan : scan the array set the bit on odd occurrence and unset on even or 0 occurrence. second scan : shift all the odd occurring elements in beginning of array and even towards end. third scan : till end of odd occurring elements. take another bit vector on first occurence :if bit is set in bv1 then unset it and set it in bv2. on second occurence : if bv1 is not set and bv2 is set then these are the array elements occuring 3rd time. On Wed, Feb 13, 2013 at 9:27 PM, prakhar singh prakhars...@gmail.comwrote: Yes, thats a valid point Don. Thats what i meant when i wrote //is that correct? in the comments on the array line in code. int a[] = {2,2,3,3,3,1,1,4,4}; // is this correct? On Wed, Feb 13, 2013 at 9:09 PM, Don dond...@gmail.com wrote: The xor approach only works if there are no values which occur only once. But the problem statement indicates that some numbers occur once, some occur twice, and one occurs three times. So you will end up with prod equal to the xor of all of the values which occur once or three times. Put that in your input array and you'll find that you don't get the desired output. I don't know of a solution better than sorting and scanning the array. Don On Feb 12, 3:14 pm, prakhar singh prakharsngh.1...@gmail.com wrote: #includestdio.h int main() { int a[] = {2,2,3,3,3,1,1,4,4}; // is this correct? int prod=a[0];int i; for(i=1;i(int)sizeof(a)/sizeof(a[0]);i++) { prod ^= a[i]; } printf(%d\n,prod); //outputs 3, algorithm works as Sachin described it; } On Tue, Feb 12, 2013 at 11:44 PM, Sachin Chitale sachinchital...@gmail.comwrote: use ex-or operation for all array elements.. a^a=0 a^a^a=a On Sun, Feb 10, 2013 at 8:22 AM, Mohanabalan D B mohanabala...@gmail.comwrote: can use counting sort On Sun, Jul 15, 2012 at 6:37 PM, santosh thota santoshthot...@gmail.comwrote: If we can retrieve ith prime efficiently, we can do the following... 1.maintain a prod=1, start from 1st element, say a[0]=n find n th prime 2.check if (prod% (ith_prime * ith_prime )==0) then return i; else prod=prod*ith_prime; 3.repeat it till end On Thursday, 12 July 2012 10:55:02 UTC+5:30, algo bard wrote: 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 view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/TSPSKlD0FDsJ. To post to this group, send email to algo...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+...@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 unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+...@googlegroups.com. For more options, visithttps://groups.google.com/groups/opt_out. -- Regards, Sachin Chitale Application Engineer SCJP, SCWCD Contact# : +91 8086284349, 9892159511 Oracle Corporation -- 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. For more options,
Re: [algogeeks] Re: Amazon Interview Question
use XOR On Tue, Apr 30, 2013 at 6:12 AM, Gary Drocella gdroc...@gmail.com wrote: This will only work if each element in the array are relatively prime to one another, that is for any two elements x, y in array A the gcd(x,y) = 1, which is also just another way of saying no number divides another number in the array. Once this rule is broken, then the algorithm will no longer work. Here is a counter example A = { 4,3,4,2,4,2 } = {2^2, 3, 2^2, 2, 2^2, 2} You might be able to see now why this algorithm breaks down. It is because the final product = 2^8*3^1 and of course 2^3 will easily divide this number, but would return the wrong solution. It was of course a very good try! On Thursday, July 12, 2012 11:46:50 PM UTC-8, jatin wrote: 1)Find product of the array and store it in say prod o(n) and o(1) 2)now traverse the array and check if static int i; tag: while(in) if( prod %(ar[i]*arr[i]*arr[i] ) ==0) break; //this may be the required element //e-o-while //now check is this is the element that is occuring three times o(n) if(number is not the required one then) goto tag; On Thursday, 12 July 2012 10:55:02 UTC+5:30, algo bard wrote: 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 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 Parag Khanna -- 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] Re: Amazon interview question
:O the final required sum would be 4C0 * a5 - 4C1 * a4 + 4C2 * a3 - 4C3 * a2 + a1 how ? , did i missed something id yes can you paste the link or explain ? Thanks Shashank On Wednesday, April 10, 2013 5:09:41 AM UTC+5:30, Shachindra A C wrote: Consider n = 5. Naming the array elements as a1,a2,a3,a4,a5 , the final required sum would be 4C0 * a5 - 4C1 * a4 + 4C2 * a3 - 4C3 * a2 + a1. That is nothing but the pattern of a binomial expansion. Using this method, the complexity can be reduced to O(n). Correct me if I'm wrong! On Tue, Apr 9, 2013 at 1:51 PM, Shashwat Kumar shashwa...@gmail.comjavascript: wrote: Recursion and iteration don't differ in this algorithm. But avoid using recursion if same can be done using iteration. In practical cases, system does not allow very large depth in recursion. So for large values of n, there can occur segmentation fault. On Tue, Apr 9, 2013 at 11:43 AM, rahul sharma rahul2...@gmail.comjavascript: wrote: If you have any other solution ..please post that...i thnik recursion is ok with base case...we need to scan again after first iteration...?? On Wed, Apr 10, 2013 at 12:12 AM, rahul sharma rahul2...@gmail.comjavascript: wrote: i forgot to add base case..can add wen 2 elemnts are there then there sum is stored and we reurn from there...i m in hurry,,,sry for that,, On Wed, Apr 10, 2013 at 12:11 AM, Don dond...@gmail.com javascript:wrote: It is O(N^2) because the inner loop takes N steps to execute and that loop will be executed N times. However, I would suggest not using recursion. There is no reason to not do it iteratively. Your recursive solution has no base case so it will recurse until your computer runs out of stack space, at which point it will crash. Don On Apr 9, 2:29 pm, rahul sharma rahul23111...@gmail.com wrote: 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+...@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. -- Shashwat Kumar Third year Undergraduate student Department of Computer Science and Engineering IIT Kharagpur -- 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. -- Regards, Shachindra A C -- 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] Re: Amazon interview question
in this Problem if the array is A[n] = {a0,a1,a(n-1),a(n)} after the second iteration, the value will be {a0 -2*a2+a3, a2 -2*a3 + a4, a3-2*a4+a5,, a(n-2)-2a(n-1)+a(n)} if we add all these terms then all the middle elements will be canceled out so the remaining will be. {a0-a2 - a(n-1)+a(n)} which can be written as a general form solution: - {a(n)-a(n-1)} - {a2-a0} this will solve the problem in time complexity in O(1). example: A = {5, 3, 8, 9, 16} solution : - {16-9}-{3-5} {7} - {-2} 9 On Wed, Apr 10, 2013 at 7:03 AM, Shashwat Anand m...@shashwat.me wrote: On 4/10/13 12:13 AM, rahul sharma wrote: If you have any other solution ..please post that...i thnik recursion is ok with base case...we need to scan again after first iteration...?? First of all, the array size and number of iteration both won't be N or else the answer will always be 0. I take the following assumption, array have K elements and number of iteration is N. Now, if N = K, the return value will always be 0. For rest, we can decompose the array following the rule of adjacent element difference. Solution with O(NK) time complexity follows: int doit (vector int v, int N) { int k = (int) v.size () - 1; if (N k) return 0; int c = 1; while (N--) { for (int i = k; i = c; i--) v [i] -= v [i - 1]; for (int i = 0; i c; i++) v [i] = 0; c++; } return accumulate (v.begin (), v.end (), 0); } int main () int a [] = { 5, 3, 8, 9, 16 }; vector int v (a, a + sizeof (a) / sizeof (a [0])); assert (doit (v, 0) == 41); assert (doit (v, 1) == 11); assert (doit (v, 2) == 9); assert (doit (v, 3) == -1); assert (doit (v, 4) == 21); assert (doit (v, 5) == 0); return 0; } However, I *strongly believe* the solution can be done in *linear time*. To code this with quadratic time complexity is a no-brainer. So, I took the array with K = 6 elements and decomposed. N = 0: [a1, a2, a3, a4, a5, a6] = a1 + a2 + a3 + a4 + a4 + a6 N = 1: [0, a2 - a1, a3 - a2, a4 - a3, a5 - a4, a6 - a5] = a6 - a1 N = 2: [0, 0, a3 - 2a2 + a1, a4 - 2a3 + a2, a5 - 2a4 + a3, a6 - 2a5 + a4] = a6 - a5 - a2 + a1 = (a6 - a5) - (a2 - a1) N = 3: [0, 0, 0, a4 - 3a3 +3a2 - a1, a5 - 3a4 + 3a3 - a2, a6 - 3a5 + 3a4 - a3] = a6 - 2a5 +a4 - a3 + 2a2 - a1 N = 4: [0, 0, 0, 0, a5 - 4a4 + 6a3 - 4a2 + a1, a6 - 4a5 + 6a4 - 4a3 + a2] = a6 - 3a5 + 2a4 + 2a3 - 3a2 + a1 N = 5: [0, 0, 0, 0, 0, a6 - 5a5 + 10a4 - 10a3 + 5a2 - a1] = a6 - 5a5 + 10a4 - 10a3 + 5a2 - a1 N = 6: [0, 0, 0, 0, 0, 0] = 0 The resulting solution does show some property of Binomial coefficient as pointed out by @Don in his hint (Pascal triangle). I suppose this shall be the way to attack this problem. On Wed, Apr 10, 2013 at 12:12 AM, rahul sharma rahul23111...@gmail.comwrote: i forgot to add base case..can add wen 2 elemnts are there then there sum is stored and we reurn from there...i m in hurry,,,sry for that,, On Wed, Apr 10, 2013 at 12:11 AM, Don dondod...@gmail.com wrote: It is O(N^2) because the inner loop takes N steps to execute and that loop will be executed N times. However, I would suggest not using recursion. There is no reason to not do it iteratively. Your recursive solution has no base case so it will recurse until your computer runs out of stack space, at which point it will crash. Don On Apr 9, 2:29 pm, rahul sharma rahul23111...@gmail.com wrote: 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. -- 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
Re: [algogeeks] Re: Amazon interview question
On 4/13/13 10:05 PM, pankaj joshi wrote: in this Problem if the array is A[n] = {a0,a1,a(n-1),a(n)} after the second iteration, the value will be {a0 -2*a2+a3, a2 -2*a3 + a4, a3-2*a4+a5,, a(n-2)-2a(n-1)+a(n)} if we add all these terms then all the middle elements will be canceled out so the remaining will be. {a0-a2 - a(n-1)+a(n)} which can be written as a general form solution: - {a(n)-a(n-1)} - {a2-a0} this will solve the problem in time complexity in O(1). example: A = {5, 3, 8, 9, 16} solution : - {16-9}-{3-5} {7} - {-2} 9 No. Your assertion is valid only for first two iteration. Iteration 1: { a1 - a0, a2 - a1, ... an - an-1 } = an - a0 Iteration 2: { a2 - 2a1 + a0, an - 2an-1 + an-2 } = (an - an-1) - (a1 - a0) Iteration 3: an - 2an-1 +an-1 - a2 + 2a1 - a0, thereby nullifying the above observation. At any state T, we need to find f (n, T) where coefficient of T is 0, to make it O(1) solution. That does not seems to be the case here. Say, for 4th iteration, what will be your answer ? I don't see any closed form here. On Wed, Apr 10, 2013 at 7:03 AM, Shashwat Anand m...@shashwat.me mailto:m...@shashwat.me wrote: On 4/10/13 12:13 AM, rahul sharma wrote: If you have any other solution ..please post that...i thnik recursion is ok with base case...we need to scan again after first iteration...?? First of all, the array size and number of iteration both won't be N or else the answer will always be 0. I take the following assumption, array have K elements and number of iteration is N. Now, if N = K, the return value will always be 0. For rest, we can decompose the array following the rule of adjacent element difference. Solution with O(NK) time complexity follows: int doit (vector int v, int N) { int k = (int) v.size () - 1; if (N k) return 0; int c = 1; while (N--) { for (int i = k; i = c; i--) v [i] -= v [i - 1]; for (int i = 0; i c; i++) v [i] = 0; c++; } return accumulate (v.begin (), v.end (), 0); } int main () int a [] = { 5, 3, 8, 9, 16 }; vector int v (a, a + sizeof (a) / sizeof (a [0])); assert (doit (v, 0) == 41); assert (doit (v, 1) == 11); assert (doit (v, 2) == 9); assert (doit (v, 3) == -1); assert (doit (v, 4) == 21); assert (doit (v, 5) == 0); return 0; } However, I /strongly believe/ the solution can be done in *linear time*. To code this with quadratic time complexity is a no-brainer. So, I took the array with K = 6 elements and decomposed. N = 0: [a1, a2, a3, a4, a5, a6] = a1 + a2 + a3 + a4 + a4 + a6 N = 1: [0, a2 - a1, a3 - a2, a4 - a3, a5 - a4, a6 - a5] = a6 - a1 N = 2: [0, 0, a3 - 2a2 + a1, a4 - 2a3 + a2, a5 - 2a4 + a3, a6 - 2a5 + a4] = a6 - a5 - a2 + a1 = (a6 - a5) - (a2 - a1) N = 3: [0, 0, 0, a4 - 3a3 +3a2 - a1, a5 - 3a4 + 3a3 - a2, a6 - 3a5 + 3a4 - a3] = a6 - 2a5 +a4 - a3 + 2a2 - a1 N = 4: [0, 0, 0, 0, a5 - 4a4 + 6a3 - 4a2 + a1, a6 - 4a5 + 6a4 - 4a3 + a2] = a6 - 3a5 + 2a4 + 2a3 - 3a2 + a1 N = 5: [0, 0, 0, 0, 0, a6 - 5a5 + 10a4 - 10a3 + 5a2 - a1] = a6 - 5a5 + 10a4 - 10a3 + 5a2 - a1 N = 6: [0, 0, 0, 0, 0, 0] = 0 The resulting solution does show some property of Binomial coefficient as pointed out by @Don in his hint (Pascal triangle). I suppose this shall be the way to attack this problem. On Wed, Apr 10, 2013 at 12:12 AM, rahul sharma rahul23111...@gmail.com mailto:rahul23111...@gmail.com wrote: i forgot to add base case..can add wen 2 elemnts are there then there sum is stored and we reurn from there...i m in hurry,,,sry for that,, On Wed, Apr 10, 2013 at 12:11 AM, Don dondod...@gmail.com mailto:dondod...@gmail.com wrote: It is O(N^2) because the inner loop takes N steps to execute and that loop will be executed N times. However, I would suggest not using recursion. There is no reason to not do it iteratively. Your recursive solution has no base case so it will recurse until your computer runs out of stack space, at which point it will crash. Don On Apr 9, 2:29 pm, rahul sharma rahul23111...@gmail.com mailto:rahul23111...@gmail.com wrote: 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); }
Re: [algogeeks] Re: Amazon interview question
i forgot to add base case..can add wen 2 elemnts are there then there sum is stored and we reurn from there...i m in hurry,,,sry for that,, On Wed, Apr 10, 2013 at 12:11 AM, Don dondod...@gmail.com wrote: It is O(N^2) because the inner loop takes N steps to execute and that loop will be executed N times. However, I would suggest not using recursion. There is no reason to not do it iteratively. Your recursive solution has no base case so it will recurse until your computer runs out of stack space, at which point it will crash. Don On Apr 9, 2:29 pm, rahul sharma rahul23111...@gmail.com wrote: 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] Re: Amazon interview question
If you have any other solution ..please post that...i thnik recursion is ok with base case...we need to scan again after first iteration...?? On Wed, Apr 10, 2013 at 12:12 AM, rahul sharma rahul23111...@gmail.comwrote: i forgot to add base case..can add wen 2 elemnts are there then there sum is stored and we reurn from there...i m in hurry,,,sry for that,, On Wed, Apr 10, 2013 at 12:11 AM, Don dondod...@gmail.com wrote: It is O(N^2) because the inner loop takes N steps to execute and that loop will be executed N times. However, I would suggest not using recursion. There is no reason to not do it iteratively. Your recursive solution has no base case so it will recurse until your computer runs out of stack space, at which point it will crash. Don On Apr 9, 2:29 pm, rahul sharma rahul23111...@gmail.com wrote: 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] Re: Amazon interview question
Recursion and iteration don't differ in this algorithm. But avoid using recursion if same can be done using iteration. In practical cases, system does not allow very large depth in recursion. So for large values of n, there can occur segmentation fault. On Tue, Apr 9, 2013 at 11:43 AM, rahul sharma rahul23111...@gmail.comwrote: If you have any other solution ..please post that...i thnik recursion is ok with base case...we need to scan again after first iteration...?? On Wed, Apr 10, 2013 at 12:12 AM, rahul sharma rahul23111...@gmail.comwrote: i forgot to add base case..can add wen 2 elemnts are there then there sum is stored and we reurn from there...i m in hurry,,,sry for that,, On Wed, Apr 10, 2013 at 12:11 AM, Don dondod...@gmail.com wrote: It is O(N^2) because the inner loop takes N steps to execute and that loop will be executed N times. However, I would suggest not using recursion. There is no reason to not do it iteratively. Your recursive solution has no base case so it will recurse until your computer runs out of stack space, at which point it will crash. Don On Apr 9, 2:29 pm, rahul sharma rahul23111...@gmail.com wrote: 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. -- Shashwat Kumar Third year Undergraduate student Department of Computer Science and Engineering IIT Kharagpur -- 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] Re: Amazon interview question
Consider n = 5. Naming the array elements as a1,a2,a3,a4,a5 , the final required sum would be 4C0 * a5 - 4C1 * a4 + 4C2 * a3 - 4C3 * a2 + a1. That is nothing but the pattern of a binomial expansion. Using this method, the complexity can be reduced to O(n). Correct me if I'm wrong! On Tue, Apr 9, 2013 at 1:51 PM, Shashwat Kumar shashwatkmr@gmail.comwrote: Recursion and iteration don't differ in this algorithm. But avoid using recursion if same can be done using iteration. In practical cases, system does not allow very large depth in recursion. So for large values of n, there can occur segmentation fault. On Tue, Apr 9, 2013 at 11:43 AM, rahul sharma rahul23111...@gmail.comwrote: If you have any other solution ..please post that...i thnik recursion is ok with base case...we need to scan again after first iteration...?? On Wed, Apr 10, 2013 at 12:12 AM, rahul sharma rahul23111...@gmail.comwrote: i forgot to add base case..can add wen 2 elemnts are there then there sum is stored and we reurn from there...i m in hurry,,,sry for that,, On Wed, Apr 10, 2013 at 12:11 AM, Don dondod...@gmail.com wrote: It is O(N^2) because the inner loop takes N steps to execute and that loop will be executed N times. However, I would suggest not using recursion. There is no reason to not do it iteratively. Your recursive solution has no base case so it will recurse until your computer runs out of stack space, at which point it will crash. Don On Apr 9, 2:29 pm, rahul sharma rahul23111...@gmail.com wrote: 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. -- Shashwat Kumar Third year Undergraduate student Department of Computer Science and Engineering IIT Kharagpur -- 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, Shachindra A C -- 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] Re: Amazon interview question
On 4/10/13 12:13 AM, rahul sharma wrote: If you have any other solution ..please post that...i thnik recursion is ok with base case...we need to scan again after first iteration...?? First of all, the array size and number of iteration both won't be N or else the answer will always be 0. I take the following assumption, array have K elements and number of iteration is N. Now, if N = K, the return value will always be 0. For rest, we can decompose the array following the rule of adjacent element difference. Solution with O(NK) time complexity follows: int doit (vector int v, int N) { int k = (int) v.size () - 1; if (N k) return 0; int c = 1; while (N--) { for (int i = k; i = c; i--) v [i] -= v [i - 1]; for (int i = 0; i c; i++) v [i] = 0; c++; } return accumulate (v.begin (), v.end (), 0); } int main () int a [] = { 5, 3, 8, 9, 16 }; vector int v (a, a + sizeof (a) / sizeof (a [0])); assert (doit (v, 0) == 41); assert (doit (v, 1) == 11); assert (doit (v, 2) == 9); assert (doit (v, 3) == -1); assert (doit (v, 4) == 21); assert (doit (v, 5) == 0); return 0; } However, I /strongly believe/ the solution can be done in *linear time*. To code this with quadratic time complexity is a no-brainer. So, I took the array with K = 6 elements and decomposed. N = 0: [a1, a2, a3, a4, a5, a6] = a1 + a2 + a3 + a4 + a4 + a6 N = 1: [0, a2 - a1, a3 - a2, a4 - a3, a5 - a4, a6 - a5] = a6 - a1 N = 2: [0, 0, a3 - 2a2 + a1, a4 - 2a3 + a2, a5 - 2a4 + a3, a6 - 2a5 + a4] = a6 - a5 - a2 + a1 = (a6 - a5) - (a2 - a1) N = 3: [0, 0, 0, a4 - 3a3 +3a2 - a1, a5 - 3a4 + 3a3 - a2, a6 - 3a5 + 3a4 - a3] = a6 - 2a5 +a4 - a3 + 2a2 - a1 N = 4: [0, 0, 0, 0, a5 - 4a4 + 6a3 - 4a2 + a1, a6 - 4a5 + 6a4 - 4a3 + a2] = a6 - 3a5 + 2a4 + 2a3 - 3a2 + a1 N = 5: [0, 0, 0, 0, 0, a6 - 5a5 + 10a4 - 10a3 + 5a2 - a1] = a6 - 5a5 + 10a4 - 10a3 + 5a2 - a1 N = 6: [0, 0, 0, 0, 0, 0] = 0 The resulting solution does show some property of Binomial coefficient as pointed out by @Don in his hint (Pascal triangle). I suppose this shall be the way to attack this problem. On Wed, Apr 10, 2013 at 12:12 AM, rahul sharma rahul23111...@gmail.com mailto:rahul23111...@gmail.com wrote: i forgot to add base case..can add wen 2 elemnts are there then there sum is stored and we reurn from there...i m in hurry,,,sry for that,, On Wed, Apr 10, 2013 at 12:11 AM, Don dondod...@gmail.com mailto:dondod...@gmail.com wrote: It is O(N^2) because the inner loop takes N steps to execute and that loop will be executed N times. However, I would suggest not using recursion. There is no reason to not do it iteratively. Your recursive solution has no base case so it will recurse until your computer runs out of stack space, at which point it will crash. Don On Apr 9, 2:29 pm, rahul sharma rahul23111...@gmail.com mailto:rahul23111...@gmail.com wrote: 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 mailto:algogeeks%2bunsubscr...@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] Re: Amazon Interview Question
hi sourab please explain what bit vector1 and bit vector 2 really are can you give an example please? On Saturday, February 16, 2013 11:20:59 PM UTC+5:30, sourabh wrote: you can solve this problem using bitvector/bitset. first scan : scan the array set the bit on odd occurrence and unset on even or 0 occurrence. second scan : shift all the odd occurring elements in beginning of array and even towards end. third scan : till end of odd occurring elements. take another bit vector on first occurence :if bit is set in bv1 then unset it and set it in bv2. on second occurence : if bv1 is not set and bv2 is set then these are the array elements occuring 3rd time. On Wed, Feb 13, 2013 at 9:27 PM, prakhar singh prakhars...@gmail.comjavascript: wrote: Yes, thats a valid point Don. Thats what i meant when i wrote //is that correct? in the comments on the array line in code. int a[] = {2,2,3,3,3,1,1,4,4}; // is this correct? On Wed, Feb 13, 2013 at 9:09 PM, Don dond...@gmail.com javascript:wrote: The xor approach only works if there are no values which occur only once. But the problem statement indicates that some numbers occur once, some occur twice, and one occurs three times. So you will end up with prod equal to the xor of all of the values which occur once or three times. Put that in your input array and you'll find that you don't get the desired output. I don't know of a solution better than sorting and scanning the array. Don On Feb 12, 3:14 pm, prakhar singh prakharsngh.1...@gmail.com wrote: #includestdio.h int main() { int a[] = {2,2,3,3,3,1,1,4,4}; // is this correct? int prod=a[0];int i; for(i=1;i(int)sizeof(a)/sizeof(a[0]);i++) { prod ^= a[i]; } printf(%d\n,prod); //outputs 3, algorithm works as Sachin described it; } On Tue, Feb 12, 2013 at 11:44 PM, Sachin Chitale sachinchital...@gmail.comwrote: use ex-or operation for all array elements.. a^a=0 a^a^a=a On Sun, Feb 10, 2013 at 8:22 AM, Mohanabalan D B mohanabala...@gmail.comwrote: can use counting sort On Sun, Jul 15, 2012 at 6:37 PM, santosh thota santoshthot...@gmail.comwrote: If we can retrieve ith prime efficiently, we can do the following... 1.maintain a prod=1, start from 1st element, say a[0]=n find n th prime 2.check if (prod% (ith_prime * ith_prime )==0) then return i; else prod=prod*ith_prime; 3.repeat it till end On Thursday, 12 July 2012 10:55:02 UTC+5:30, algo bard wrote: 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 view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/TSPSKlD0FDsJ. 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 unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+...@googlegroups.com javascript:. For more options, visithttps://groups.google.com/groups/opt_out. -- Regards, Sachin Chitale Application Engineer SCJP, SCWCD Contact# : +91 8086284349, 9892159511 Oracle Corporation -- 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, visithttps://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+...@googlegroups.com javascript:. 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
Re: [algogeeks] Re: Amazon Interview Question
@sandeep he is talking about constant space. On Tue, Mar 19, 2013 at 5:31 PM, sandeep kumar sandeepkumar1...@gmail.comwrote: Hey what if while scanning through the array we create a BST n check simultaneously that : current node == current node's parent current node == current node's left or right child -- 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] Re: Amazon Interview Question
Hey what if while scanning through the array we create a BST n check simultaneously that : current node == current node's parent current node == current node's left or right child -- 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] Re: Amazon Interview Question
Yes, thats a valid point Don. Thats what i meant when i wrote //is that correct? in the comments on the array line in code. int a[] = {2,2,3,3,3,1,1,4,4}; // is this correct? On Wed, Feb 13, 2013 at 9:09 PM, Don dondod...@gmail.com wrote: The xor approach only works if there are no values which occur only once. But the problem statement indicates that some numbers occur once, some occur twice, and one occurs three times. So you will end up with prod equal to the xor of all of the values which occur once or three times. Put that in your input array and you'll find that you don't get the desired output. I don't know of a solution better than sorting and scanning the array. Don On Feb 12, 3:14 pm, prakhar singh prakharsngh.1...@gmail.com wrote: #includestdio.h int main() { int a[] = {2,2,3,3,3,1,1,4,4}; // is this correct? int prod=a[0];int i; for(i=1;i(int)sizeof(a)/sizeof(a[0]);i++) { prod ^= a[i]; } printf(%d\n,prod); //outputs 3, algorithm works as Sachin described it; } On Tue, Feb 12, 2013 at 11:44 PM, Sachin Chitale sachinchital...@gmail.comwrote: use ex-or operation for all array elements.. a^a=0 a^a^a=a On Sun, Feb 10, 2013 at 8:22 AM, Mohanabalan D B mohanabala...@gmail.comwrote: can use counting sort On Sun, Jul 15, 2012 at 6:37 PM, santosh thota santoshthot...@gmail.comwrote: If we can retrieve ith prime efficiently, we can do the following... 1.maintain a prod=1, start from 1st element, say a[0]=n find n th prime 2.check if (prod% (ith_prime * ith_prime )==0) then return i; else prod=prod*ith_prime; 3.repeat it till end On Thursday, 12 July 2012 10:55:02 UTC+5:30, algo bard wrote: 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 view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/TSPSKlD0FDsJ. 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 unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visithttps://groups.google.com/groups/opt_out. -- Regards, Sachin Chitale Application Engineer SCJP, SCWCD Contact# : +91 8086284349, 9892159511 Oracle Corporation -- 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, visithttps://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] Re: Amazon Interview Question
you can solve this problem using bitvector/bitset. first scan : scan the array set the bit on odd occurrence and unset on even or 0 occurrence. second scan : shift all the odd occurring elements in beginning of array and even towards end. third scan : till end of odd occurring elements. take another bit vector on first occurence :if bit is set in bv1 then unset it and set it in bv2. on second occurence : if bv1 is not set and bv2 is set then these are the array elements occuring 3rd time. On Wed, Feb 13, 2013 at 9:27 PM, prakhar singh prakharsngh.1...@gmail.comwrote: Yes, thats a valid point Don. Thats what i meant when i wrote //is that correct? in the comments on the array line in code. int a[] = {2,2,3,3,3,1,1,4,4}; // is this correct? On Wed, Feb 13, 2013 at 9:09 PM, Don dondod...@gmail.com wrote: The xor approach only works if there are no values which occur only once. But the problem statement indicates that some numbers occur once, some occur twice, and one occurs three times. So you will end up with prod equal to the xor of all of the values which occur once or three times. Put that in your input array and you'll find that you don't get the desired output. I don't know of a solution better than sorting and scanning the array. Don On Feb 12, 3:14 pm, prakhar singh prakharsngh.1...@gmail.com wrote: #includestdio.h int main() { int a[] = {2,2,3,3,3,1,1,4,4}; // is this correct? int prod=a[0];int i; for(i=1;i(int)sizeof(a)/sizeof(a[0]);i++) { prod ^= a[i]; } printf(%d\n,prod); //outputs 3, algorithm works as Sachin described it; } On Tue, Feb 12, 2013 at 11:44 PM, Sachin Chitale sachinchital...@gmail.comwrote: use ex-or operation for all array elements.. a^a=0 a^a^a=a On Sun, Feb 10, 2013 at 8:22 AM, Mohanabalan D B mohanabala...@gmail.comwrote: can use counting sort On Sun, Jul 15, 2012 at 6:37 PM, santosh thota santoshthot...@gmail.comwrote: If we can retrieve ith prime efficiently, we can do the following... 1.maintain a prod=1, start from 1st element, say a[0]=n find n th prime 2.check if (prod% (ith_prime * ith_prime )==0) then return i; else prod=prod*ith_prime; 3.repeat it till end On Thursday, 12 July 2012 10:55:02 UTC+5:30, algo bard wrote: 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 view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/TSPSKlD0FDsJ. 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 unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visithttps://groups.google.com/groups/opt_out. -- Regards, Sachin Chitale Application Engineer SCJP, SCWCD Contact# : +91 8086284349, 9892159511 Oracle Corporation -- 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, visithttps://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. -- 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] Re: Amazon Interview Question
Sachin Chitale, Dude the xoring operation will give us xor of numbers with freq 1 and 3 respectively. How do you filter out the number with the frequency 3?? On Tuesday, February 12, 2013 11:44:08 PM UTC+5:30, Sachin Chitale wrote: use ex-or operation for all array elements.. a^a=0 a^a^a=a On Sun, Feb 10, 2013 at 8:22 AM, Mohanabalan D B mohana...@gmail.comjavascript: wrote: can use counting sort On Sun, Jul 15, 2012 at 6:37 PM, santosh thota santosh...@gmail.comjavascript: wrote: If we can retrieve ith prime efficiently, we can do the following... 1.maintain a prod=1, start from 1st element, say a[0]=n find n th prime 2.check if (prod% (ith_prime * ith_prime )==0) then return i; else prod=prod*ith_prime; 3.repeat it till end On Thursday, 12 July 2012 10:55:02 UTC+5:30, algo bard wrote: 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 view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/TSPSKlD0FDsJ. 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 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. -- Regards, Sachin Chitale Application Engineer SCJP, SCWCD Contact# : +91 8086284349, 9892159511 Oracle Corporation -- 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] Re: Amazon Interview Question
Search for BitSet/BitVector in java . On Tue, Feb 12, 2013 at 11:44 PM, Sachin Chitale sachinchital...@gmail.comwrote: use ex-or operation for all array elements.. a^a=0 a^a^a=a On Sun, Feb 10, 2013 at 8:22 AM, Mohanabalan D B mohanabala...@gmail.comwrote: can use counting sort On Sun, Jul 15, 2012 at 6:37 PM, santosh thota santoshthot...@gmail.comwrote: If we can retrieve ith prime efficiently, we can do the following... 1.maintain a prod=1, start from 1st element, say a[0]=n find n th prime 2.check if (prod% (ith_prime * ith_prime )==0) then return i; else prod=prod*ith_prime; 3.repeat it till end On Thursday, 12 July 2012 10:55:02 UTC+5:30, algo bard wrote: 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 view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/TSPSKlD0FDsJ. 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 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, Sachin Chitale Application Engineer SCJP, SCWCD Contact# : +91 8086284349, 9892159511 Oracle Corporation -- 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] Re: Amazon Interview Question
@Sachin Chitale : Very good approach dude . thumbs up +1 -- Arun Singh Chauhan Engineer (RnD 2), Samsung Electronics Software Engineering Lab, Noida On Tuesday, February 12, 2013 11:44:08 PM UTC+5:30, Sachin Chitale wrote: use ex-or operation for all array elements.. a^a=0 a^a^a=a On Sun, Feb 10, 2013 at 8:22 AM, Mohanabalan D B mohana...@gmail.comjavascript: wrote: can use counting sort On Sun, Jul 15, 2012 at 6:37 PM, santosh thota santosh...@gmail.comjavascript: wrote: If we can retrieve ith prime efficiently, we can do the following... 1.maintain a prod=1, start from 1st element, say a[0]=n find n th prime 2.check if (prod% (ith_prime * ith_prime )==0) then return i; else prod=prod*ith_prime; 3.repeat it till end On Thursday, 12 July 2012 10:55:02 UTC+5:30, algo bard wrote: 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 view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/TSPSKlD0FDsJ. 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 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. -- Regards, Sachin Chitale Application Engineer SCJP, SCWCD Contact# : +91 8086284349, 9892159511 Oracle Corporation -- 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] Re: Amazon Interview Question
can use counting sort On Sun, Jul 15, 2012 at 6:37 PM, santosh thota santoshthot...@gmail.comwrote: If we can retrieve ith prime efficiently, we can do the following... 1.maintain a prod=1, start from 1st element, say a[0]=n find n th prime 2.check if (prod% (ith_prime * ith_prime )==0) then return i; else prod=prod*ith_prime; 3.repeat it till end On Thursday, 12 July 2012 10:55:02 UTC+5:30, algo bard wrote: 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 view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/TSPSKlD0FDsJ. 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 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] Re: Amazon interview Question
@anurag : there is no need to SORT. as it will increase complexity O(n) to O(n log n). here is the correct code.. please look over it and notify me if i'm wrong . T.C. = O( n ) // ex: 1 4 3 2 0 i'm explaining on behalf of it. bool permute (int *arr , int N ) { if ( N=1 ) return false; for ( int i = N-2 ; i = 0 ; i-- ) { if ( arr[i+1] arr[i]) // now i points to 1 { for ( int j = N-1 ; j i ; j--) { if ( arr[i] arr[j]) // now j points to 2(just greater than 1 ) { swap(arr[i],arr[j]) ;//this will generate 2 4 3 1 0 since 4310 are already sorted in reverse //thus no need to sort again in inc order rather than reversing i++ ; j = N-1; while(ij) swap(arr[i++],arr[j--]) ; // reversing the seq 4..0 to 0..4 return true ; } } } } return false ; } Regards, Ritesh Kumar Mishra Information Technology Third Year Undergraduate MNNIT Allahabad On Mon, Dec 24, 2012 at 7:56 PM, marti amritsa...@gmail.com wrote: I REPEAT, THERE is no need to SORT; http://en.wikipedia.org/wiki/Permutation#Lexicographical%5Forder%5Fgeneration On Friday, December 14, 2012 11:56:16 AM UTC+5:30, tapan rathi wrote: For a given number, find the next greatest number which is just greater than previous one and made up of same digits. -- --
Re: [algogeeks] Re: Amazon interview Question
Can anyone give me some idea if the given no is small like 12 then the next one is 17 On Mon, Dec 24, 2012 at 7:56 PM, marti amritsa...@gmail.com wrote: I REPEAT, THERE is no need to SORT; http://en.wikipedia.org/wiki/Permutation#Lexicographical%5Forder%5Fgeneration On Friday, December 14, 2012 11:56:16 AM UTC+5:30, tapan rathi wrote: For a given number, find the next greatest number which is just greater than previous one and made up of same digits. -- --
Re: [algogeeks] Re: Amazon interview Question
Hi Ritesh Yeah, you are right. we do not need to sort. my bad Thank you for explaining clearly On Thu, Dec 27, 2012 at 4:29 AM, Ritesh Mishra rforr...@gmail.com wrote: @anurag : there is no need to SORT. as it will increase complexity O(n) to O(n log n). here is the correct code.. please look over it and notify me if i'm wrong . T.C. = O( n ) // ex: 1 4 3 2 0 i'm explaining on behalf of it. bool permute (int *arr , int N ) { if ( N=1 ) return false; for ( int i = N-2 ; i = 0 ; i-- ) { if ( arr[i+1] arr[i]) // now i points to 1 { for ( int j = N-1 ; j i ; j--) { if ( arr[i] arr[j]) // now j points to 2(just greater than 1 ) { swap(arr[i],arr[j]) ;//this will generate 2 4 3 1 0 since 4310 are already sorted in reverse //thus no need to sort again in inc order rather than reversing i++ ; j = N-1; while(ij) swap(arr[i++],arr[j--]) ; // reversing the seq 4..0 to 0..4 return true ; } } } } return false ; } Regards, Ritesh Kumar Mishra Information Technology Third Year Undergraduate MNNIT Allahabad On Mon, Dec 24, 2012 at 7:56 PM, marti amritsa...@gmail.com wrote: I REPEAT, THERE is no need to SORT; http://en.wikipedia.org/wiki/Permutation#Lexicographical%5Forder%5Fgeneration On Friday, December 14, 2012 11:56:16 AM UTC+5:30, tapan rathi wrote: For a given number, find the next greatest number which is just greater than previous one and made up of same digits. -- -- -- Regards Anurag Gupta IV Year Computer Engineering Delhi Technological University (Formerly Delhi College of Engineering) --
Re: [algogeeks] Re: Amazon interview Question
@marti your answer is completely wrong (check for 234987156221 ans is 2349871*61225 * whereas your answer would be 2349871*65225*) and we do need to sort On Mon, Dec 17, 2012 at 9:10 AM, marti amritsa...@gmail.com wrote: Yeah thanks Sandeep, theres an error in example...it should be 5436827.However there is no need to sort. On Friday, December 14, 2012 11:56:16 AM UTC+5:30, tapan rathi wrote: For a given number, find the next greatest number which is just greater than previous one and made up of same digits. -- -- Regards Anurag Gupta IV Year Computer Engineering Delhi Technological University (Formerly Delhi College of Engineering) --
Re: [algogeeks] Re: Amazon interview Question
hello all... anwer to previous example would be 5436827 instead of 5436872please correct it :) On Sun, Dec 16, 2012 at 11:48 PM, marti amritsa...@gmail.com wrote: Here is what you do EG: 5436782 ans is 5436872 how did we arrive? FInd least index i, such that a[i-1] = a[i] starting from rigthmost 5436782 (8) Now , Find least index j such that a[j-1] = a[i-1]: 5436782 (7) swap them = 5436872 Now swap all values between i and j. Pseudocode in Python: *def get_next(a):* *N = len(a)* *i = len(a)-1* * * *while a[i-1] = a[i]:* *i -= 1* * * *j = N* * * *while a[j-1] = a[i-1]:* *j -= 1* * * *a[i-1], a[j-1] = a[j-1], a[i-1]* * * *i += 1* *j = N* * * *while i j:* *a[i-1], a[j-1] = a[j-1], a[i-1]* *i+=1* *j-=1* * * *return a* Source: http://nicolas-lara.blogspot.in/2009/01/permutations.html On Friday, December 14, 2012 11:56:16 AM UTC+5:30, tapan rathi wrote: For a given number, find the next greatest number which is just greater than previous one and made up of same digits. -- -- Regards, SHUBHAM SANDEEP IT 3rd yr. NIT ALD. --
Re: [algogeeks] Re: Amazon interview Question
Let the number is stored in an array a[n] with MSB at index 0... 1. i = n-1; reduce i till a[i]=a[i-1] i 0. If here i =0 means give number is largest possible number made out of digits otherwise i is pointing to a digit such that a[i]a[i+1] 2. find smallest digit from a[i+1 to n-1] just larger than a[i]. lets assume it come out as a digit of index j. 3. swap a[i] and a[j]. Finally sort a[i+1 to n-1] in increasing order... suppose a=5436782 so after step 1, i=4 after step 2, j=5 after step 4, a=5436872 finally after sorting a=5436827 -- Ram Chandra Sankhala | 3rd Year | Computer Science Engineering | IIT Roorkee --
Re: [algogeeks] Re: Amazon Interview Question
ya that's right :( any other solution.. On Saturday, 14 July 2012 03:24:41 UTC+5:30, Dave wrote: @Jatin: Take the array {1, 2, 4, 8, ..., x, 2, 4, 8, ..., x, x}, where x is the largest power of two that will fit in your integer data type. Here 1 occurs once, 2, 4, 8, ... each occur twice, and x occurs three times. Ignoring that you can't calculate the product of the numbers due to overflow, the cube of each number in the array will be a factor of the product, so you will have to check every number to see if it occurs three times. Those checks will be O(n), so the whole algorithm will be O(n^2). Correct me if I am wrong. As another example, just include a zero in the array and see if your algorithm still works as written. Dave On Friday, July 13, 2012 9:59:31 AM UTC-5, jatin sethi wrote: as long as we are using goto with proper comments to ensure that it won't decrease the readability we can use them and ther's no harm in it! Secondly the worst case for my algo is o(n) .?..correct me if i am wrong On Friday, 13 July 2012 18:12:41 UTC+5:30, adarsh kumar wrote: Ya I didn't see that part, sorry. And in general, using goto is not advisable. Plus this will exceed O(n) in the worst case, as we may keep visiting the goto again and again. Not sure of its exact time complexity. -- From: vindhya chhabra Sent: 13-07-2012 17:46 To: algogeeks@googlegroups.com Subject: Re: [algogeeks] Re: Amazon Interview Question @adarsh But i think jatin has asked to check for the number( we achieved in step 1) occuring thrice or not..and in this check 27 will rule out.but i doubt the algo given by Jatin runs in O(n) time. please comment. On Fri, Jul 13, 2012 at 5:17 PM, adarsh kumar algog...@gmail.comwrote: @jatin: Your first method may be proved wrong. Here is a counter test case: Suppose the array is: 27 729 19683 2 3 3 27 3 81 729 Here, 81 occurs once, 19683 occurs once, 2 occurs once,729 occurs twice, 27 occurs twice, and 3 occurs thrice. You are supposed to return 3 But as per your method, the product will be computed as 729*19683*2*3*3*27*3*81*729=product(say) Upon traversing the second time, it will return 27, as product%(27*27*27) is equal to zero! regards. On Fri, Jul 13, 2012 at 1:29 PM, @jatin jatinseth...@gmail.com wrote: Or we can make a BST from array list in o(n) then traverse it inorder-o(logn) but this solution requires o(logn) space though. On Friday, 13 July 2012 13:16:50 UTC+5:30, jatin sethi wrote: 1)Find product of the array and store it in say prod o(n) and o(1) 2)now traverse the array and check if static int i; tag: while(in) if( prod %(ar[i]*arr[i]*arr[i] ) ==0) break; //this may be the required element //e-o-while //now check is this is the element that is occuring three times o(n) if(number is not the required one then) goto tag; On Thursday, 12 July 2012 10:55:02 UTC+5:30, algo bard wrote: 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 view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/lmzhJ-GSdigJ. 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. -- Vindhya Chhabra -- 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 view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/r8KWdIC96ckJ. 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] Re: Amazon Interview Question
@jatin: Your first method may be proved wrong. Here is a counter test case: Suppose the array is: 27 729 19683 2 3 3 27 3 81 729 Here, 81 occurs once, 19683 occurs once, 2 occurs once,729 occurs twice, 27 occurs twice, and 3 occurs thrice. You are supposed to return 3 But as per your method, the product will be computed as 729*19683*2*3*3*27*3*81*729=product(say) Upon traversing the second time, it will return 27, as product%(27*27*27) is equal to zero! regards. On Fri, Jul 13, 2012 at 1:29 PM, @jatin jatinseth...@gmail.com wrote: Or we can make a BST from array list in o(n) then traverse it inorder-o(logn) but this solution requires o(logn) space though. On Friday, 13 July 2012 13:16:50 UTC+5:30, jatin sethi wrote: 1)Find product of the array and store it in say prod o(n) and o(1) 2)now traverse the array and check if static int i; tag: while(in) if( prod %(ar[i]*arr[i]*arr[i] ) ==0) break; //this may be the required element //e-o-while //now check is this is the element that is occuring three times o(n) if(number is not the required one then) goto tag; On Thursday, 12 July 2012 10:55:02 UTC+5:30, algo bard wrote: 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 view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/lmzhJ-GSdigJ. 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] Re: Amazon Interview Question
@adarsh But i think jatin has asked to check for the number( we achieved in step 1) occuring thrice or not..and in this check 27 will rule out.but i doubt the algo given by Jatin runs in O(n) time. please comment. On Fri, Jul 13, 2012 at 5:17 PM, adarsh kumar algog...@gmail.com wrote: @jatin: Your first method may be proved wrong. Here is a counter test case: Suppose the array is: 27 729 19683 2 3 3 27 3 81 729 Here, 81 occurs once, 19683 occurs once, 2 occurs once,729 occurs twice, 27 occurs twice, and 3 occurs thrice. You are supposed to return 3 But as per your method, the product will be computed as 729*19683*2*3*3*27*3*81*729=product(say) Upon traversing the second time, it will return 27, as product%(27*27*27) is equal to zero! regards. On Fri, Jul 13, 2012 at 1:29 PM, @jatin jatinseth...@gmail.com wrote: Or we can make a BST from array list in o(n) then traverse it inorder-o(logn) but this solution requires o(logn) space though. On Friday, 13 July 2012 13:16:50 UTC+5:30, jatin sethi wrote: 1)Find product of the array and store it in say prod o(n) and o(1) 2)now traverse the array and check if static int i; tag: while(in) if( prod %(ar[i]*arr[i]*arr[i] ) ==0) break; //this may be the required element //e-o-while //now check is this is the element that is occuring three times o(n) if(number is not the required one then) goto tag; On Thursday, 12 July 2012 10:55:02 UTC+5:30, algo bard wrote: 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 view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/lmzhJ-GSdigJ. 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. -- Vindhya Chhabra -- 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] Re: Amazon Interview Question
Ya I didn't see that part, sorry. And in general, using goto is not advisable. Plus this will exceed O(n) in the worst case, as we may keep visiting the goto again and again. Not sure of its exact time complexity. -- From: vindhya chhabra Sent: 13-07-2012 17:46 To: algogeeks@googlegroups.com Subject: Re: [algogeeks] Re: Amazon Interview Question @adarsh But i think jatin has asked to check for the number( we achieved in step 1) occuring thrice or not..and in this check 27 will rule out.but i doubt the algo given by Jatin runs in O(n) time. please comment. On Fri, Jul 13, 2012 at 5:17 PM, adarsh kumar algog...@gmail.com wrote: @jatin: Your first method may be proved wrong. Here is a counter test case: Suppose the array is: 27 729 19683 2 3 3 27 3 81 729 Here, 81 occurs once, 19683 occurs once, 2 occurs once,729 occurs twice, 27 occurs twice, and 3 occurs thrice. You are supposed to return 3 But as per your method, the product will be computed as 729*19683*2*3*3*27*3*81*729=product(say) Upon traversing the second time, it will return 27, as product%(27*27*27) is equal to zero! regards. On Fri, Jul 13, 2012 at 1:29 PM, @jatin jatinseth...@gmail.com wrote: Or we can make a BST from array list in o(n) then traverse it inorder-o(logn) but this solution requires o(logn) space though. On Friday, 13 July 2012 13:16:50 UTC+5:30, jatin sethi wrote: 1)Find product of the array and store it in say prod o(n) and o(1) 2)now traverse the array and check if static int i; tag: while(in) if( prod %(ar[i]*arr[i]*arr[i] ) ==0) break; //this may be the required element //e-o-while //now check is this is the element that is occuring three times o(n) if(number is not the required one then) goto tag; On Thursday, 12 July 2012 10:55:02 UTC+5:30, algo bard wrote: 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 view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/lmzhJ-GSdigJ. 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. -- Vindhya Chhabra -- 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] Re: Amazon Interview Question
as long as we are using goto with proper comments to ensure that it won't decrease the readability we can use them and ther's no harm in it! Secondly the worst case for my algo is o(n) .?..correct me if i am wrong On Friday, 13 July 2012 18:12:41 UTC+5:30, adarsh kumar wrote: Ya I didn't see that part, sorry. And in general, using goto is not advisable. Plus this will exceed O(n) in the worst case, as we may keep visiting the goto again and again. Not sure of its exact time complexity. -- From: vindhya chhabra Sent: 13-07-2012 17:46 To: algogeeks@googlegroups.com Subject: Re: [algogeeks] Re: Amazon Interview Question @adarsh But i think jatin has asked to check for the number( we achieved in step 1) occuring thrice or not..and in this check 27 will rule out.but i doubt the algo given by Jatin runs in O(n) time. please comment. On Fri, Jul 13, 2012 at 5:17 PM, adarsh kumar algog...@gmail.com wrote: @jatin: Your first method may be proved wrong. Here is a counter test case: Suppose the array is: 27 729 19683 2 3 3 27 3 81 729 Here, 81 occurs once, 19683 occurs once, 2 occurs once,729 occurs twice, 27 occurs twice, and 3 occurs thrice. You are supposed to return 3 But as per your method, the product will be computed as 729*19683*2*3*3*27*3*81*729=product(say) Upon traversing the second time, it will return 27, as product%(27*27*27) is equal to zero! regards. On Fri, Jul 13, 2012 at 1:29 PM, @jatin jatinseth...@gmail.com wrote: Or we can make a BST from array list in o(n) then traverse it inorder-o(logn) but this solution requires o(logn) space though. On Friday, 13 July 2012 13:16:50 UTC+5:30, jatin sethi wrote: 1)Find product of the array and store it in say prod o(n) and o(1) 2)now traverse the array and check if static int i; tag: while(in) if( prod %(ar[i]*arr[i]*arr[i] ) ==0) break; //this may be the required element //e-o-while //now check is this is the element that is occuring three times o(n) if(number is not the required one then) goto tag; On Thursday, 12 July 2012 10:55:02 UTC+5:30, algo bard wrote: 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 view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/lmzhJ-GSdigJ. 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. -- Vindhya Chhabra -- 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 view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/wYWXoPmf9_MJ. 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] Re: Amazon Interview Question
@Jatin: Take the array {1, 2, 4, 8, ..., x, 2, 4, 8, ..., x, x}, where x is the largest power of two that will fit in your integer data type. Here 1 occurs once, 2, 4, 8, ... each occur twice, and x occurs three times. Ignoring that you can't calculate the product of the numbers due to overflow, the cube of each number in the array will be a factor of the product, so you will have to check every number to see if it occurs three times. Those checks will be O(n), so the whole algorithm will be O(n^2). Correct me if I am wrong. As another example, just include a zero in the array and see if your algorithm still works as written. Dave On Friday, July 13, 2012 9:59:31 AM UTC-5, jatin sethi wrote: as long as we are using goto with proper comments to ensure that it won't decrease the readability we can use them and ther's no harm in it! Secondly the worst case for my algo is o(n) .?..correct me if i am wrong On Friday, 13 July 2012 18:12:41 UTC+5:30, adarsh kumar wrote: Ya I didn't see that part, sorry. And in general, using goto is not advisable. Plus this will exceed O(n) in the worst case, as we may keep visiting the goto again and again. Not sure of its exact time complexity. -- From: vindhya chhabra Sent: 13-07-2012 17:46 To: algogeeks@googlegroups.com Subject: Re: [algogeeks] Re: Amazon Interview Question @adarsh But i think jatin has asked to check for the number( we achieved in step 1) occuring thrice or not..and in this check 27 will rule out.but i doubt the algo given by Jatin runs in O(n) time. please comment. On Fri, Jul 13, 2012 at 5:17 PM, adarsh kumar algog...@gmail.com wrote: @jatin: Your first method may be proved wrong. Here is a counter test case: Suppose the array is: 27 729 19683 2 3 3 27 3 81 729 Here, 81 occurs once, 19683 occurs once, 2 occurs once,729 occurs twice, 27 occurs twice, and 3 occurs thrice. You are supposed to return 3 But as per your method, the product will be computed as 729*19683*2*3*3*27*3*81*729=product(say) Upon traversing the second time, it will return 27, as product%(27*27*27) is equal to zero! regards. On Fri, Jul 13, 2012 at 1:29 PM, @jatin jatinseth...@gmail.com wrote: Or we can make a BST from array list in o(n) then traverse it inorder-o(logn) but this solution requires o(logn) space though. On Friday, 13 July 2012 13:16:50 UTC+5:30, jatin sethi wrote: 1)Find product of the array and store it in say prod o(n) and o(1) 2)now traverse the array and check if static int i; tag: while(in) if( prod %(ar[i]*arr[i]*arr[i] ) ==0) break; //this may be the required element //e-o-while //now check is this is the element that is occuring three times o(n) if(number is not the required one then) goto tag; On Thursday, 12 July 2012 10:55:02 UTC+5:30, algo bard wrote: 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 view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/lmzhJ-GSdigJ. 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. -- Vindhya Chhabra -- 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 view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/n6oN4OI__CsJ. 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] Re: Amazon Interview Question
No it's not O(n). Coz you're scanning the array and in case you do not find a solution, you're jumping back to the start of the loop. That's equivalent to a nested loop. And I think in the worst case...it'll turn out to be an O(n^2) solution. Please correct me if I'm wrong. On Fri, Jul 13, 2012 at 8:29 PM, jatin jatinseth...@gmail.com wrote: as long as we are using goto with proper comments to ensure that it won't decrease the readability we can use them and ther's no harm in it! Secondly the worst case for my algo is o(n) .?..correct me if i am wrong On Friday, 13 July 2012 18:12:41 UTC+5:30, adarsh kumar wrote: Ya I didn't see that part, sorry. And in general, using goto is not advisable. Plus this will exceed O(n) in the worst case, as we may keep visiting the goto again and again. Not sure of its exact time complexity. -- From: vindhya chhabra Sent: 13-07-2012 17:46 To: algogeeks@googlegroups.com Subject: Re: [algogeeks] Re: Amazon Interview Question @adarsh But i think jatin has asked to check for the number( we achieved in step 1) occuring thrice or not..and in this check 27 will rule out.but i doubt the algo given by Jatin runs in O(n) time. please comment. On Fri, Jul 13, 2012 at 5:17 PM, adarsh kumar algog...@gmail.com wrote: @jatin: Your first method may be proved wrong. Here is a counter test case: Suppose the array is: 27 729 19683 2 3 3 27 3 81 729 Here, 81 occurs once, 19683 occurs once, 2 occurs once,729 occurs twice, 27 occurs twice, and 3 occurs thrice. You are supposed to return 3 But as per your method, the product will be computed as 729*19683*2*3*3*27*3*81*729=**product(say) Upon traversing the second time, it will return 27, as product%(27*27*27) is equal to zero! regards. On Fri, Jul 13, 2012 at 1:29 PM, @jatin jatinseth...@gmail.com wrote: Or we can make a BST from array list in o(n) then traverse it inorder-o(logn) but this solution requires o(logn) space though. On Friday, 13 July 2012 13:16:50 UTC+5:30, jatin sethi wrote: 1)Find product of the array and store it in say prod o(n) and o(1) 2)now traverse the array and check if static int i; tag: while(in) if( prod %(ar[i]*arr[i]*arr[i] ) ==0) break; //this may be the required element //e-o-while //now check is this is the element that is occuring three times o(n) if(number is not the required one then) goto tag; On Thursday, 12 July 2012 10:55:02 UTC+5:30, algo bard wrote: 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 view this discussion on the web visit https://groups.google.com/d/** msg/algogeeks/-/lmzhJ-GSdigJhttps://groups.google.com/d/msg/algogeeks/-/lmzhJ-GSdigJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscribe@** googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=en 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+unsubscribe@** googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=en http://groups.google.com/group/algogeeks?hl=en. -- Vindhya Chhabra -- 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+unsubscribe@** googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=en 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/-/wYWXoPmf9_MJ. 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
Re: [algogeeks] Re: Amazon Interview Question
@jatin: even i think it will b more than O(n).. infact it will be O(n-square) in the worst case as if each hit is spurious(until the last element of course) we will have to traverse the array for each spurious hit.. thus giving the worst case time of O(n-square) On Fri, Jul 13, 2012 at 8:29 PM, jatin jatinseth...@gmail.com wrote: as long as we are using goto with proper comments to ensure that it won't decrease the readability we can use them and ther's no harm in it! Secondly the worst case for my algo is o(n) .?..correct me if i am wrong On Friday, 13 July 2012 18:12:41 UTC+5:30, adarsh kumar wrote: Ya I didn't see that part, sorry. And in general, using goto is not advisable. Plus this will exceed O(n) in the worst case, as we may keep visiting the goto again and again. Not sure of its exact time complexity. -- From: vindhya chhabra Sent: 13-07-2012 17:46 To: algogeeks@googlegroups.com Subject: Re: [algogeeks] Re: Amazon Interview Question @adarsh But i think jatin has asked to check for the number( we achieved in step 1) occuring thrice or not..and in this check 27 will rule out.but i doubt the algo given by Jatin runs in O(n) time. please comment. On Fri, Jul 13, 2012 at 5:17 PM, adarsh kumar algog...@gmail.com wrote: @jatin: Your first method may be proved wrong. Here is a counter test case: Suppose the array is: 27 729 19683 2 3 3 27 3 81 729 Here, 81 occurs once, 19683 occurs once, 2 occurs once,729 occurs twice, 27 occurs twice, and 3 occurs thrice. You are supposed to return 3 But as per your method, the product will be computed as 729*19683*2*3*3*27*3*81*729=**product(say) Upon traversing the second time, it will return 27, as product%(27*27*27) is equal to zero! regards. On Fri, Jul 13, 2012 at 1:29 PM, @jatin jatinseth...@gmail.com wrote: Or we can make a BST from array list in o(n) then traverse it inorder-o(logn) but this solution requires o(logn) space though. On Friday, 13 July 2012 13:16:50 UTC+5:30, jatin sethi wrote: 1)Find product of the array and store it in say prod o(n) and o(1) 2)now traverse the array and check if static int i; tag: while(in) if( prod %(ar[i]*arr[i]*arr[i] ) ==0) break; //this may be the required element //e-o-while //now check is this is the element that is occuring three times o(n) if(number is not the required one then) goto tag; On Thursday, 12 July 2012 10:55:02 UTC+5:30, algo bard wrote: 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 view this discussion on the web visit https://groups.google.com/d/** msg/algogeeks/-/lmzhJ-GSdigJhttps://groups.google.com/d/msg/algogeeks/-/lmzhJ-GSdigJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscribe@** googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=en 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+unsubscribe@** googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=en http://groups.google.com/group/algogeeks?hl=en. -- Vindhya Chhabra -- 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+unsubscribe@** googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=en 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/-/wYWXoPmf9_MJ. 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
RE: [algogeeks] Re: Amazon Interview Question
+1. -- From: Shruti Gupta Sent: 14-07-2012 08:08 To: algogeeks@googlegroups.com Subject: Re: [algogeeks] Re: Amazon Interview Question @jatin: even i think it will b more than O(n).. infact it will be O(n-square) in the worst case as if each hit is spurious(until the last element of course) we will have to traverse the array for each spurious hit.. thus giving the worst case time of O(n-square) On Fri, Jul 13, 2012 at 8:29 PM, jatin jatinseth...@gmail.com wrote: as long as we are using goto with proper comments to ensure that it won't decrease the readability we can use them and ther's no harm in it! Secondly the worst case for my algo is o(n) .?..correct me if i am wrong On Friday, 13 July 2012 18:12:41 UTC+5:30, adarsh kumar wrote: Ya I didn't see that part, sorry. And in general, using goto is not advisable. Plus this will exceed O(n) in the worst case, as we may keep visiting the goto again and again. Not sure of its exact time complexity. -- From: vindhya chhabra Sent: 13-07-2012 17:46 To: algogeeks@googlegroups.com Subject: Re: [algogeeks] Re: Amazon Interview Question @adarsh But i think jatin has asked to check for the number( we achieved in step 1) occuring thrice or not..and in this check 27 will rule out.but i doubt the algo given by Jatin runs in O(n) time. please comment. On Fri, Jul 13, 2012 at 5:17 PM, adarsh kumar algog...@gmail.com wrote: @jatin: Your first method may be proved wrong. Here is a counter test case: Suppose the array is: 27 729 19683 2 3 3 27 3 81 729 Here, 81 occurs once, 19683 occurs once, 2 occurs once,729 occurs twice, 27 occurs twice, and 3 occurs thrice. You are supposed to return 3 But as per your method, the product will be computed as 729*19683*2*3*3*27*3*81*729=**product(say) Upon traversing the second time, it will return 27, as product%(27*27*27) is equal to zero! regards. On Fri, Jul 13, 2012 at 1:29 PM, @jatin jatinseth...@gmail.com wrote: Or we can make a BST from array list in o(n) then traverse it inorder-o(logn) but this solution requires o(logn) space though. On Friday, 13 July 2012 13:16:50 UTC+5:30, jatin sethi wrote: 1)Find product of the array and store it in say prod o(n) and o(1) 2)now traverse the array and check if static int i; tag: while(in) if( prod %(ar[i]*arr[i]*arr[i] ) ==0) break; //this may be the required element //e-o-while //now check is this is the element that is occuring three times o(n) if(number is not the required one then) goto tag; On Thursday, 12 July 2012 10:55:02 UTC+5:30, algo bard wrote: 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 view this discussion on the web visit https://groups.google.com/d/** msg/algogeeks/-/lmzhJ-GSdigJhttps://groups.google.com/d/msg/algogeeks/-/lmzhJ-GSdigJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscribe@** googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=en 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+unsubscribe@** googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=en http://groups.google.com/group/algogeeks?hl=en. -- Vindhya Chhabra -- 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+unsubscribe@** googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=en 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/-/wYWXoPmf9_MJ. 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
Re: [algogeeks] Re: Amazon Interview Question
+1 for trie.. -- Amol Sharma Third Year Student Computer Science and Engineering MNNIT Allahabad http://gplus.to/amolsharma99 http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/ On Fri, Jun 15, 2012 at 5:21 PM, enchantress elaenjoy...@gmail.com wrote: se a trie with end of word marked by its corresponding entry in array. -- 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] Re: Amazon Interview Question
Hi Guys, The @pacific solution is the best? Wladimir Araujo Tavares *Federal University of Ceará * On Tue, Jun 28, 2011 at 7:26 AM, sunny agrawal sunny816.i...@gmail.comwrote: you can initialize it to (Max-Min+1) where Max = max of all elements Min = min of all elements Or simple initialise it to a large integer like 0x7fff for 32 bit numbers. On Tue, Jun 28, 2011 at 3:32 PM, vikas mehta...@gmail.com wrote: what will be the oldDiff initially. can u plz explain with a egsample -- 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/-/NXQqyUTbdlkJ. 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. -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- 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] Re: Amazon Interview Question
what will be the oldDiff initially. can u plz explain with a egsample -- 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/-/NXQqyUTbdlkJ. 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] Re: Amazon Interview Question
you can initialize it to (Max-Min+1) where Max = max of all elements Min = min of all elements Or simple initialise it to a large integer like 0x7fff for 32 bit numbers. On Tue, Jun 28, 2011 at 3:32 PM, vikas mehta...@gmail.com wrote: what will be the oldDiff initially. can u plz explain with a egsample -- 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/-/NXQqyUTbdlkJ. 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. -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- 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] Re: Amazon Interview Question
@pacific you are perfectly right but the order is not o(kn) its is O(k*n*log(n)) because to get the least number u have to use priority queue nd at every iteration (from 1 to k*n) u have to push and pop one single element. -- Anshuman Mishra IIIT Allahabad - anshumishra6...@gmail.com rit2007...@iiita.ac.in -- 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] Re: Amazon Interview Question
My approach : Have a pointer to the start (smallest of the array) of each of the N arrays. Until all pointers reach end of respective arrays : take the smallest value from all of the pointers and compute the difference between the smallest and the current pointers of each of the arrays let newdiff be the smallest among all the diffs if newdiff olddiff : olddiff = newdiff only advance the smallest number pointer Correctness : I believe that if the smallest difference occurs between a and b ,(a is smallest) you will come across that comparison and find the least. Complexity : 0(kn) , it should be the best because you atleast need to read all of the input. Please correct me if i'm wrong. On Mon, May 9, 2011 at 8:55 PM, bittu shashank7andr...@gmail.com wrote: see here let me know if anything wrong..?? http://shashank7s.blogspot.com/2011/05/wap-to-find-minimum-difference-between.html Thanks Regrads Shashank the Best Way to Escape From The problem is to Solve it Computer Science Engg. BIT Mesra -- 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, chinna. -- 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] Re: Amazon Interview question
I forgot to mention Time complexity: O(n), Space complexity: O(1) Assuming you accept my solution :-) On Mon, Feb 28, 2011 at 9:27 PM, Vinay Pandey babbupan...@gmail.com wrote: Hi, Here is my solution, let me know: /* a helper function */ void swap(int* arr, int index1, int index2) { /* this is only to swap to integers */ arr[index1] = arr[index1]^arr[index2]; arr[index2] = arr[index1]^arr[index2]; arr[index1] = arr[index1]^arr[index2]; } /* Actual switching */ void switch(int* arr, int length) { if(length%2!=0 length2) { coutCannot switch in this case; return; } int index = length-1, first=0, second=0; bool flag = 0; while(index=2) { if(flag == 0) { swap(arr, (index+1)/2, index); } if(flag == 1) { swap(arr, index/2 + 1, index); swap(arr, (index+1)/2, index); } index-=2; flag=(flag==0)?1:0; } } On Mon, Feb 28, 2011 at 4:32 PM, Dave dave_and_da...@juno.com wrote: @Arpit: The problem is that for certain values of n, you get more than one cycle, and the cycles are disjoint. You have to find all of the disjoint cycles and move the elements in each one. Dave On Feb 28, 12:25 pm, Arpit Sood soodfi...@gmail.com wrote: well space complexity should be mentioned in the question then, anyway, start with the second element put it at its correct location(say x), then take x put it at its correct location, this was when you do this n-1 time, you will get the correct answer because it forms a cycle. On Mon, Feb 28, 2011 at 11:33 PM, bittu shashank7andr...@gmail.com wrote: @arpit otherwise it wont b amzon quest.. space dude..space is constants Thanks Shashank -- 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.- Hide quoted text - - Show quoted text - -- 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] Re: Amazon Interview question
Here is one recursive solution I propose : consider example a1,a2,a3,a4,b1,b2,b3,b4 1. if n is even swap second Half of first array with first half of second array so it would be a1,a2,b1,b2,a3,a4,b3,b4 and it can be solved recursively so rearrange({a1,a2,a3,a4,b1,b2,b3,b4}) = rearrange({a1,a2,b1,b2}), rearrange({a3,a4,b3,b4}); 2. if n is odd (a1,a2,a3,a4,a5,b1,b2,b3,b4,b5) swap second Half+1 of first array with first half+1 of second array so it would be a1,a2,b1,b2,*b3,a3*,a4,a5,b4,b5 swap bolded elements( nth and n+1 th) a1,a2,b1,b2,a3,b3,a4,a5,b4,b5 and it can be solved recursively by dividing in two sub parts rearrange({a1,a2,a3,a4,a5,b1,b2,b3,b4,b5}) = swap(b3,a3), rearrange({a1,a2,b1,b2}), rearrange({a4,a5,b4,b5}); limiting case would be if n==2 //since the pair is in required order return; Time complexity analysis ( n is size of total array a+b): T(n) = 2*T(n/2) + n/4 ( n/4 is swapping time of second Half of first array with first half of second array) T(n) = 2^k T(1) + n/4( 1+1/2+1/4+...+1/(2^k)) = 2^k+n/4( 1-1/(2^k))*2k = log(n) =n+ (n-1)/2 =O(n) What say? On Mon, Feb 28, 2011 at 11:55 PM, Arpit Sood soodfi...@gmail.com wrote: well space complexity should be mentioned in the question then, anyway, start with the second element put it at its correct location(say x), then take x put it at its correct location, this was when you do this n-1 time, you will get the correct answer because it forms a cycle. On Mon, Feb 28, 2011 at 11:33 PM, bittu shashank7andr...@gmail.comwrote: @arpit otherwise it wont b amzon quest.. space dude..space is constants Thanks Shashank -- 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, Gaurav Gupta 7676-999-350 Quality is never an accident. It is always result of intelligent effort - John Ruskin -- 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] Re: Amazon Interview question
Hi, Here is my solution, let me know: /* a helper function */ void swap(int* arr, int index1, int index2) { /* this is only to swap to integers */ arr[index1] = arr[index1]^arr[index2]; arr[index2] = arr[index1]^arr[index2]; arr[index1] = arr[index1]^arr[index2]; } /* Actual switching */ void switch(int* arr, int length) { if(length%2!=0 length2) { coutCannot switch in this case; return; } int index = length-1, first=0, second=0; bool flag = 0; while(index=2) { if(flag == 0) { swap(arr, (index+1)/2, index); } if(flag == 1) { swap(arr, index/2 + 1, index); swap(arr, (index+1)/2, index); } index-=2; flag=(flag==0)?1:0; } } On Mon, Feb 28, 2011 at 4:32 PM, Dave dave_and_da...@juno.com wrote: @Arpit: The problem is that for certain values of n, you get more than one cycle, and the cycles are disjoint. You have to find all of the disjoint cycles and move the elements in each one. Dave On Feb 28, 12:25 pm, Arpit Sood soodfi...@gmail.com wrote: well space complexity should be mentioned in the question then, anyway, start with the second element put it at its correct location(say x), then take x put it at its correct location, this was when you do this n-1 time, you will get the correct answer because it forms a cycle. On Mon, Feb 28, 2011 at 11:33 PM, bittu shashank7andr...@gmail.com wrote: @arpit otherwise it wont b amzon quest.. space dude..space is constants Thanks Shashank -- 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.- Hide quoted text - - Show quoted text - -- 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] Re: Amazon Interview question
Are there any constraints in the problem, because it seems straight forward. if number of elements are 2n indexed from 0 to 2n-1 for i=0 to n-1: new_array[i*2]=old_array[i]; new_array[i*2+1]=old_array[i+n]; On Mon, Feb 28, 2011 at 7:41 PM, bittu shashank7andr...@gmail.com wrote: @jalaj U needs to clarify becoz what i can say that dat is overwritten in ur explanation so we loosing the original data where we are saving when we swapping the elements ur explanation seems to be right but little confusing @ujjwal i haven't tested ur code but i think its O(n^2) then why not try for this 20 Line Simple code of O(n^2) Finally we wants O(n) better solution fro this which exist for this ??? #includestring.h void swap(char *c,char *p) { char tmp; tmp=*c; *c=*p; *p=tmp; } int main (int argc, char const* argv[]) { char str[] = 1234abcd; int i,j; int len = strlen(str)/2; //swap str[len-1] and str[len] and so on for ( i = 0; i len-1; i += 1) { for ( j = len-1-i; j = len+i; j += 2) { printf(i=%d j=%d c1=%c \t c2=%c \n,i,j,str[j],str[j+1]); swap(str[j],str[j+1]); } } printf(%s \n, str); return 0; } Time Complexcity O(n^2) O(n) Needed.. Thanks Regards Shashank The Best Way to escape From The Problem is Solve It -- 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] Re: Amazon Interview question
how abt dis guys ?? #include stdio.h #include string.h #define MAX 100 int main() { int n; int i; int j; int it; char input[MAX]; char tmp; scanf(%s,input); n = strlen(input); i = j = n/2; for(it=1; itn-2; it++) { if(it%2 == 1) { tmp = input[j]; input[j] = input[it]; input[it] = tmp; j++; } else if( it i ) { tmp = input[i]; input[i] = input[it]; input[it] = tmp; } else { tmp = input[it]; input[it] = input[it+1]; input[it+1] = tmp; } } printf(\n%s\n,input); return 0; } On Mon, Feb 28, 2011 at 8:29 PM, Arpit Sood soodfi...@gmail.com wrote: Are there any constraints in the problem, because it seems straight forward. if number of elements are 2n indexed from 0 to 2n-1 for i=0 to n-1: new_array[i*2]=old_array[i]; new_array[i*2+1]=old_array[i+n]; On Mon, Feb 28, 2011 at 7:41 PM, bittu shashank7andr...@gmail.com wrote: @jalaj U needs to clarify becoz what i can say that dat is overwritten in ur explanation so we loosing the original data where we are saving when we swapping the elements ur explanation seems to be right but little confusing @ujjwal i haven't tested ur code but i think its O(n^2) then why not try for this 20 Line Simple code of O(n^2) Finally we wants O(n) better solution fro this which exist for this ??? #includestring.h void swap(char *c,char *p) { char tmp; tmp=*c; *c=*p; *p=tmp; } int main (int argc, char const* argv[]) { char str[] = 1234abcd; int i,j; int len = strlen(str)/2; //swap str[len-1] and str[len] and so on for ( i = 0; i len-1; i += 1) { for ( j = len-1-i; j = len+i; j += 2) { printf(i=%d j=%d c1=%c \t c2=%c \n,i,j,str[j],str[j+1]); swap(str[j],str[j+1]); } } printf(%s \n, str); return 0; } Time Complexcity O(n^2) O(n) Needed.. Thanks Regards Shashank The Best Way to escape From The Problem is Solve It -- 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] Re: Amazon Interview question
well space complexity should be mentioned in the question then, anyway, start with the second element put it at its correct location(say x), then take x put it at its correct location, this was when you do this n-1 time, you will get the correct answer because it forms a cycle. On Mon, Feb 28, 2011 at 11:33 PM, bittu shashank7andr...@gmail.com wrote: @arpit otherwise it wont b amzon quest.. space dude..space is constants Thanks Shashank -- 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] Re: amazon interview question
O(m+n). Search from rightmost top corner. Count the no of zero from right and go to left, i.e. traverse through columns from right of the first row. When you find a column having 0, go down to lower row. Check the correspondent column is 1 or not. If it is, follow the above step or else go down to next lower row. On 24 December 2010 16:02, MAC macatad...@gmail.com wrote: updated :) Given a boolean matrix with all the true elements on left side in the row so that each row can be broken into two parts left part containing only true elements and right part containing only false elements. Find the row with max number of true elements in it. 00011 0 1 true is 0 false is 1 .. so we will say 2nd row has maximum 1 and 3rd row has mximum 0 -- thanks --mac -- thanks --mac -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards, soumya prasad ukil -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] Re: amazon interview question
@SoumyaNice Solution. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] Re: Amazon Interview Question
It can be done easily by counting sort On Wed, Dec 15, 2010 at 5:36 AM, Soumya Prasad Ukil ukil.sou...@gmail.comwrote: Have a look : http://geeksforgeeks.org/?p=1488 On 15 December 2010 05:19, Saurabh Koar saurabhkoar...@gmail.com wrote: @ Bittu: Lets analyze your code with iterations: the array contains 1 3 3 1 2 3 5 2 3 count contains 0 2 2 4 0 1 0 0 0 now 1st iteration: i=8,7,6 the inner loop will nt be executed; i=5; so j=0 only; as count[5]=1; Now arr[pos](i.e array[0])=5 i=4; the inner loop fails i=3; so j=0 to 3 as count[3]=4 Now array[1]=array[2]=array[3]=array[4]=3 i=2; so j=0 to 1 as count[2]=2 so array[5]=array[6]=2 and likewise array[7]=array[8]=1 so the final array 5 3 3 3 3 2 2 1 1 It doesnt match with the desired output. Correct me if I m missing something. On 12/15/10, bittu shashank7andr...@gmail.com wrote: @ankur,saurabh,soumya.. ya ankur i forget to remove range from dare also no need to find range for this..\ put size-1 intead of range so that malloc will alocate the memory to all elements in array ..no hope its fine... what i did is that i took counter array thta cvontains the no of times particular elements comes then i have sort d array in reverse order... prints accoding to count array..thats it... and the last line of actual question says.. ..in case of a tie print the number which occurred first ..i don't think d way i hav solved dis.. still please let me no..if m wrong.. Regards Shashank Mani Narayan Don't b evil U can earn while u Learn Computer Science enginerring BIrla Institute of Technology,Mesra Cell 9166674831 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards, soumya prasad ukil -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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] Re: Amazon Interview Question
Have a look : http://geeksforgeeks.org/?p=1488 On 15 December 2010 05:19, Saurabh Koar saurabhkoar...@gmail.com wrote: @ Bittu: Lets analyze your code with iterations: the array contains 1 3 3 1 2 3 5 2 3 count contains 0 2 2 4 0 1 0 0 0 now 1st iteration: i=8,7,6 the inner loop will nt be executed; i=5; so j=0 only; as count[5]=1; Now arr[pos](i.e array[0])=5 i=4; the inner loop fails i=3; so j=0 to 3 as count[3]=4 Now array[1]=array[2]=array[3]=array[4]=3 i=2; so j=0 to 1 as count[2]=2 so array[5]=array[6]=2 and likewise array[7]=array[8]=1 so the final array 5 3 3 3 3 2 2 1 1 It doesnt match with the desired output. Correct me if I m missing something. On 12/15/10, bittu shashank7andr...@gmail.com wrote: @ankur,saurabh,soumya.. ya ankur i forget to remove range from dare also no need to find range for this..\ put size-1 intead of range so that malloc will alocate the memory to all elements in array ..no hope its fine... what i did is that i took counter array thta cvontains the no of times particular elements comes then i have sort d array in reverse order... prints accoding to count array..thats it... and the last line of actual question says.. ..in case of a tie print the number which occurred first ..i don't think d way i hav solved dis.. still please let me no..if m wrong.. Regards Shashank Mani Narayan Don't b evil U can earn while u Learn Computer Science enginerring BIrla Institute of Technology,Mesra Cell 9166674831 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards, soumya prasad ukil -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] Re: Amazon Interview Question
@sajj: if the range of number is not given then ? On Tue, Dec 14, 2010 at 11:41 PM, sajj sajjv...@gmail.com wrote: you can use hash table for this dude. On Dec 14, 8:22 pm, Prims topcode...@gmail.com wrote: given some positive numbers output the numbers in decreasing order of frequency..in case of a tie print the number which occurred first for eg: 1,3,3,1,2,3,5,2,3 the output should be 11225 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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 algoge...@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] Re: Amazon Interview Question
what you can do is create a vector pairint,int and sort it on the baisis of secondary key where it will be it's frequency. if tha range is not given. If the range is in permissible limits, then hash table is the answer. I suppose. On Tue, Dec 14, 2010 at 11:45 PM, Ankur Khurana ankur.kkhur...@gmail.com wrote: @sajj: if the range of number is not given then ? On Tue, Dec 14, 2010 at 11:41 PM, sajj sajjv...@gmail.com wrote: you can use hash table for this dude. On Dec 14, 8:22 pm, Prims topcode...@gmail.com wrote: given some positive numbers output the numbers in decreasing order of frequency..in case of a tie print the number which occurred first for eg: 1,3,3,1,2,3,5,2,3 the output should be 11225 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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 algoge...@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] Re: Amazon Interview Question
bittu, in stead of writing your code, put your logic here. It is not the place to show how capable one is to write a program. On 14 December 2010 11:00, bittu shashank7andr...@gmail.com wrote: #include stdlib.h #includestdio.h #includeconio.h int main() { int array[]={1,3,3,1,2,3,5,2,3}; int size=sizeof(array)/sizeof(int); int min,max; max=min=array[0]; int i=0; for(i = 1; i size; i++) { if (array[i] min) min = array[i]; else if (array[i] max) max = array[i]; } int range = max - min + 1; int *count =(int *) malloc(range * sizeof(int)); for(i = 0; i size; i++) count[i] = 0; for(i = 0; i size; i++) count[array[i]]++; int pos=0; for(i=size-1;i=0;i--) { for(int j=0;jcount[i];j++) { array[pos]=i; pos++; } } //free(count); for(int i=0;isize;i++) printf(%d \n ,array[i]); getch(); } in case of a tie print the number which occurred first ...i think dis situation never occurs...as ..array is sorted.. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards, soumya prasad ukil -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] Re: Amazon Interview Question
I think ankur khanna's solution is appropriate. couldn't get what bittu was trying to do completely.. could you just explain it once please! On Wed, Dec 15, 2010 at 10:35 AM, Soumya Prasad Ukil ukil.sou...@gmail.comwrote: bittu, in stead of writing your code, put your logic here. It is not the place to show how capable one is to write a program. On 14 December 2010 11:00, bittu shashank7andr...@gmail.com wrote: #include stdlib.h #includestdio.h #includeconio.h int main() { int array[]={1,3,3,1,2,3,5,2,3}; int size=sizeof(array)/sizeof(int); int min,max; max=min=array[0]; int i=0; for(i = 1; i size; i++) { if (array[i] min) min = array[i]; else if (array[i] max) max = array[i]; } int range = max - min + 1; int *count =(int *) malloc(range * sizeof(int)); for(i = 0; i size; i++) count[i] = 0; for(i = 0; i size; i++) count[array[i]]++; int pos=0; for(i=size-1;i=0;i--) { for(int j=0;jcount[i];j++) { array[pos]=i; pos++; } } //free(count); for(int i=0;isize;i++) printf(%d \n ,array[i]); getch(); } in case of a tie print the number which occurred first ...i think dis situation never occurs...as ..array is sorted.. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards, soumya prasad ukil -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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] Re: Amazon Interview Question
@gene: can you do dry run a test case: a[0]-a[n-1] 0 1 2 31 34 135 and if u c On Tue, Dec 7, 2010 at 8:55 AM, Gene gene.ress...@gmail.com wrote: I should have mentioned that this problem only makes sense if the array values must be unique. On Dec 6, 8:20 pm, Gene gene.ress...@gmail.com wrote: You guys are working too hard. Think about the sequence of numbers [ A[i] - i | i = 0,1,2,...n-1 ]. You are trying to probe this sequence to find the number of zeros. If you think about it for a while, you will see that this sequence is non-decreasing. It must be a segment of zero or more negative numbers followed by a segment of zero or more zeros followed by a segment of zero or more positive numbers. Therefore you can easily use two binary searches to find the index of the leftmost and rightmost zeros. This identifies all the elements where A[i]=i in O(2 log n) = O(log n) time. Of course if the searches fail, you have no elements at all where A[i]=i. On Dec 5, 9:46 am, Nikhil Agarwal nikhil.bhoja...@gmail.com wrote: @Divesh I have updated my algo and Array A[1,2,3.n] is sorted with unique elements.CALL FIND_EQUAL(A,1,n) int FIND_EQUAL(A,start,end) 1.Go to the middle element 2. If A[mid]mid) 3. if(start==mid) 4 return mid-1; 5return FIND_EQUAL(A,1,mid-1); 6 if(A[mid]=mid) 7if(mid==end) 8 return mid; 9return FIND_EQUAL(A,mid+1,end); On Sun, Dec 5, 2010 at 7:36 PM, coolfrog$ dixit.coolfrog.div...@gmail.comwrote: @Nikhil run you algo .. on test case index - 1 2 3 4 5 value - 1 2 3 4 5 ouput is mid+1= 3+1=4 but it should be 5... correct me if i am wrong... and u have assumed all are positive, hence base index should be 1 On Sun, Dec 5, 2010 at 4:41 PM, Nikhil Agarwal nikhil.bhoja...@gmail.comwrote: If All the elements are unique and sorted in ascending order then we can design an algorithm for O(lgn) and all nos are positive. Run FIND_EQUAL(A,0,N-1) [A0,A1 and A2 are the array elements] FIND_EQUAL(A,start,end) 1.Go to the middle element 2.If A[mid]==mid) return mid+1; if(A[mid]mid) then FIND_EQUAL(A,start,mid-1) else FIND_EQUAL(A,mid+1,end) Runs in O(lgn) On Sun, Dec 5, 2010 at 12:20 PM, jai gupta sayhelloto...@gmail.com wrote: Any algorithm must in worst case lead to O(n) if the elements are not unique. Take the case: 1 2 3 4 5 6 as all the elements satisfy the condition of of key==index . we must go someway to each element. Hence O(n). This may be somehow made less if the element are given to be unique by using heap. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups .com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups .com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Divesh* (¨`·.·´¨) Always `·.¸(¨`·.·´¨ ) Keep (¨`·.·´¨)¸.·´Smiling! `·.¸.·´ Life can give u 100's of reason 2cry,but u can give life 1000's of reasons 2Smile -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups .com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,Indiahttp://tech-nikk.blogspot.comhttp:// beta.freshersworld.com/communitie... -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com.
Re: [algogeeks] Re: Amazon Interview Question
@Divesh I have updated my algo and Array A[1,2,3.n] is sorted with unique elements.CALL FIND_EQUAL(A,1,n) int FIND_EQUAL(A,start,end) 1.Go to the middle element 2. If A[mid]mid) 3. if(start==mid) 4 return mid-1; 5return FIND_EQUAL(A,1,mid-1); 6 if(A[mid]=mid) 7if(mid==end) 8 return mid; 9return FIND_EQUAL(A,mid+1,end); On Sun, Dec 5, 2010 at 7:36 PM, coolfrog$ dixit.coolfrog.div...@gmail.comwrote: @Nikhil run you algo .. on test case index - 1 2 3 4 5 value - 1 2 3 4 5 ouput is mid+1= 3+1=4 but it should be 5... correct me if i am wrong... and u have assumed all are positive, hence base index should be 1 On Sun, Dec 5, 2010 at 4:41 PM, Nikhil Agarwal nikhil.bhoja...@gmail.comwrote: If All the elements are unique and sorted in ascending order then we can design an algorithm for O(lgn) and all nos are positive. Run FIND_EQUAL(A,0,N-1) [A0,A1 and A2 are the array elements] FIND_EQUAL(A,start,end) 1.Go to the middle element 2.If A[mid]==mid) return mid+1; if(A[mid]mid) then FIND_EQUAL(A,start,mid-1) else FIND_EQUAL(A,mid+1,end) Runs in O(lgn) On Sun, Dec 5, 2010 at 12:20 PM, jai gupta sayhelloto...@gmail.comwrote: Any algorithm must in worst case lead to O(n) if the elements are not unique. Take the case: 1 2 3 4 5 6 as all the elements satisfy the condition of of key==index . we must go someway to each element. Hence O(n). This may be somehow made less if the element are given to be unique by using heap. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Divesh* (¨`·.·´¨) Always `·.¸(¨`·.·´¨ ) Keep (¨`·.·´¨)¸.·´Smiling! `·.¸.·´ Life can give u 100's of reason 2cry,but u can give life 1000's of reasons 2Smile -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] Re: Amazon Interview Question
If All the elements are unique and sorted in ascending order then we can design an algorithm for O(lgn) and all nos are positive. Run FIND_EQUAL(A,0,N-1) [A0,A1 and A2 are the array elements] FIND_EQUAL(A,start,end) 1.Go to the middle element 2.If A[mid]==mid) return mid+1; if(A[mid]mid) then FIND_EQUAL(A,start,mid-1) else FIND_EQUAL(A,mid+1,end) Runs in O(lgn) On Sun, Dec 5, 2010 at 12:20 PM, jai gupta sayhelloto...@gmail.com wrote: Any algorithm must in worst case lead to O(n) if the elements are not unique. Take the case: 1 2 3 4 5 6 as all the elements satisfy the condition of of key==index . we must go someway to each element. Hence O(n). This may be somehow made less if the element are given to be unique by using heap. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] Re: Amazon Interview Question
yaar I can use simple O(n) sweep to find out who all are equal, I think it can't be less than this On Sat, Dec 4, 2010 at 8:05 PM, Abioy Sun abioy@gmail.com wrote: 2010/12/4 ankit sablok ankit4...@gmail.com: as all the elements are sorted in the array make a min heap of the array elements and as min heap is a tree of keys querying a min heap or a binary search tree requires operations with time equal to the height of the tree which is log(n) hence time for querying a min heap I think you might be use a log(n) time to find out a element whose value is equal to some certain index, so the complexity could be n*log(n)? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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] Re: Amazon Interview Question
@Nikhil run you algo .. on test case index - 1 2 3 4 5 value - 1 2 3 4 5 ouput is mid+1= 3+1=4 but it should be 5... correct me if i am wrong... and u have assumed all are positive, hence base index should be 1 On Sun, Dec 5, 2010 at 4:41 PM, Nikhil Agarwal nikhil.bhoja...@gmail.comwrote: If All the elements are unique and sorted in ascending order then we can design an algorithm for O(lgn) and all nos are positive. Run FIND_EQUAL(A,0,N-1) [A0,A1 and A2 are the array elements] FIND_EQUAL(A,start,end) 1.Go to the middle element 2.If A[mid]==mid) return mid+1; if(A[mid]mid) then FIND_EQUAL(A,start,mid-1) else FIND_EQUAL(A,mid+1,end) Runs in O(lgn) On Sun, Dec 5, 2010 at 12:20 PM, jai gupta sayhelloto...@gmail.comwrote: Any algorithm must in worst case lead to O(n) if the elements are not unique. Take the case: 1 2 3 4 5 6 as all the elements satisfy the condition of of key==index . we must go someway to each element. Hence O(n). This may be somehow made less if the element are given to be unique by using heap. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Divesh* (¨`·.·´¨) Always `·.¸(¨`·.·´¨ ) Keep (¨`·.·´¨)¸.·´Smiling! `·.¸.·´ Life can give u 100's of reason 2cry,but u can give life 1000's of reasons 2Smile -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] Re: Amazon Interview Question
@ashim please refer my post.I posted an o(lgn) algo.i.e. I am copying again below with an update If All the elements are unique and sorted in ascending order then we can design an algorithm for O(lgn) and all nos are positive. Run FIND_EQUAL(A,0,N-1) [A0,A1 and A2 are the array elements] FIND_EQUAL(A,start,end) 1.Go to the middle element 2.If A[mid]==mid||mid==0) { if(mid==0A[0]!=0) return 0; return mid+1; } if(A[mid]mid) then FIND_EQUAL(A,start,mid-1) else FIND_EQUAL(A,mid+1,end) Runs in O(lgn) On Sat, Dec 4, 2010 at 8:08 PM, Ashim Kapoor ashimkap...@gmail.com wrote: yaar I can use simple O(n) sweep to find out who all are equal, I think it can't be less than this On Sat, Dec 4, 2010 at 8:05 PM, Abioy Sun abioy@gmail.com wrote: 2010/12/4 ankit sablok ankit4...@gmail.com: as all the elements are sorted in the array make a min heap of the array elements and as min heap is a tree of keys querying a min heap or a binary search tree requires operations with time equal to the height of the tree which is log(n) hence time for querying a min heap I think you might be use a log(n) time to find out a element whose value is equal to some certain index, so the complexity could be n*log(n)? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] Re: Amazon Interview Question
2010/12/5 juver++ avpostni...@gmail.com: Wrong. Counterexample: 1 2 2 2 2 6 suppose you mean 1 3 3 3 3 6? 1) divide-conquer 2) search binary, in each sub array [s, t], mid = (s+t)/2 if t array[mid]: // no need to check the part after mid, all will fail else if s array[mid]: // no need to check the part before mid, all will fail // if we have the elements unique if mid array[mid]: // no need to check the part after mid, all will fail else if mid array[mid]: // no need to check the part before mid, all will fail 3) when the elements are unique, in [s, t], if (array[s] = s array[t] = t) // all in [s, t] is ok but I think its complexity will be O(n) in the worse case if elements could be equal. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] Re: Amazon interview Question (Array yet again!)
i think this prob cannot be solved by DP then... Because anytime a new value coming into the non decreasing sub-array obtained by the DP equation can be disrupted(like in the above example). I think a backtracking approach cud prove useful. (Recursion) anytime we get a new element we can do two things : Either delete it or decrement the previous values equal to it. We do both by calling the same function twice for each element. Plz comment on this... -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] Re: Amazon interview Question (Array yet again!)
@gene ..if u just give an example herethat will make things more clear... -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] Re: Amazon interview Question (Array yet again!)
@ Gene: Sorry I misunderstood the problem. I thought the other operation is of increment rather than decrement... My bad -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] Re: Amazon interview Question (Array yet again!)
Just read the comments. You will get logic. 1 read global variables 2 start with main 3 read rec (a recursive fn) The main logic is that whether to keep the no in the final no (by decrementing it) or to completely remove it. #include stdio.h #define SIZE 4 int result[SIZE];/*Array for storing current state of solution*/ int final_cost = 10; /*set minimum cost to some large value*/ int curr_ans[SIZE]; /*sorted array with the minimum cost*/ /*copies result into curr_ans*/ void save_arr(int *result) { int i; for (i=0 ;iSIZE ;i++) { curr_ans[i] = result[i]; } } /*print the final solution*/ void print_ans() { int i; for (i=0 ;iSIZE ;i++) { printf ( %d,curr_ans[i]); } } void rec (int *arr,int index,int min,int cost) { if (index = 0) { /* * keep the arr[index] in the solution * i.e copy arr[index] in curr_ans[index] * will increase cost by * 1 arr[index] - min if arr[index] min * (where min is the min no among arr[index] to arr[SIZE-1]) * 2 0 if arr[index] min and will set min = arr[index] * (where min is the min no among arr[index] to arr[SIZE-1]) * * After this call a fn rec (recursively) with index-1 * new cost calculated and new min */ if (arr[index] = min) { result[index] = arr[index]; rec (arr,index-1,arr[index],cost); } else { result[index] = min; cost += (arr[index] - min); rec (arr,index-1,min,cost); cost -= (arr[index] - min); } /* * remove the arr[index] from the solution * copy 0 in curr_ans[index] increases the * cost by arr[index] as we are removig it */ result[index] = 0; cost += arr[index]; rec (arr,index-1,min,cost); } else if (index == -1) { if (cost final_cost) { final_cost = cost; save_arr(result); } return; } } int main(int argc,char *argv[]) { int i; int arr[SIZE] = {10,3,11,12}; rec(arr,SIZE-1,arr[SIZE]+1,0); /* * start with the last index i.e traverse array from end to start * as we call rec with index-1 each time */ printf (\n minimum cost = %d \n sorted array =,final_cost); print_ans(); return 0; } On Sun, Aug 29, 2010 at 2:18 PM, jagadish jagadish1...@gmail.com wrote: @Rahul Patil: I ran your code on some basic test cases and i found it to be correct! Can you please explain the logic you used to arrive at the solution? Thanks :-) On Aug 29, 12:25 pm, rahul patil rahul.deshmukhpa...@gmail.com wrote: check out this solution.I think this works correct will explain logic if u find it correct. #include stdio.h #define SIZE 4 int result[SIZE]; int final_cost = 10; int curr_ans[SIZE]; void save_arr(int *result) { int i; for (i=0 ;iSIZE ;i++) { curr_ans[i] = result[i]; } } void print_ans() { int i; for (i=0 ;iSIZE ;i++) { printf ( %d,curr_ans[i]); }} void rec (int *arr,int index,int min,int cost) { if (index = 0) { // keep the arr[index] if (arr[index] = min) { result[index] = arr[index]; rec (arr,index-1,arr[index],cost); } else { result[index] = min; cost += (arr[index] - min); rec (arr,index-1,min,cost); cost -= (arr[index] - min); } // remove the arr[index] result[index] = 0; cost += arr[index]; rec (arr,index-1,min,cost); } else if (index == -1) { if (cost final_cost) { final_cost = cost; save_arr(result); } return; } } int main(int argc,char *argv[]) { int i; int arr[SIZE] = {10,3,11,12}; rec(arr,SIZE-1,arr[SIZE]+1,0); printf (\n minimum cost = %d \n sorted array =,final_cost); print_ans(); return 0; } On Aug 29, 1:17 am, Neeraj Gupta neeraj.gu...@nsitonline.in wrote: On Sun, Aug 29, 2010 at 1:35 AM, Gene gene.ress...@gmail.com wrote: My algorithm proposal wasn't correct, but I can't see how to get 8. You need to decrement 14, 15, 16, 13 to 11. This costs 14. So do I. May be he has not noticed that incrementing a number is not an option. ;) On Aug 28, 5:41 am, gaurav singhal singhal08gau...@gmail.com wrote: @ Gene : Output for int a[] = { 14, 15, 16, 13, 11, 18 }; is coming out to be 14 whereas minimum cost will be : 8 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to
Re: [algogeeks] Re: Amazon interview Question (Array yet again!)
@ Gene : Output for int a[] = { 14, 15, 16, 13, 11, 18 }; is coming out to be 14 whereas minimum cost will be : 8 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] Re: Amazon interview Question (Array yet again!)
On Sun, Aug 29, 2010 at 1:35 AM, Gene gene.ress...@gmail.com wrote: My algorithm proposal wasn't correct, but I can't see how to get 8. You need to decrement 14, 15, 16, 13 to 11. This costs 14. So do I. May be he has not noticed that incrementing a number is not an option. ;) On Aug 28, 5:41 am, gaurav singhal singhal08gau...@gmail.com wrote: @ Gene : Output for int a[] = { 14, 15, 16, 13, 11, 18 }; is coming out to be 14 whereas minimum cost will be : 8 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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] Re: Amazon interview Question (Array yet again!)
This code is giving incorrect answer in some inputs.If possible someone correct it. #includestdio.h #includeconio.h static int SIZE=5; void print(int *array); int del(int *array,int i); int decrement(int *array,int i); void print(int *array) { printf(\n); int i=0; for(;iSIZE;i++) printf(%d\t,array[i]);printf(\n); } int del(int *array,int i) { int x=array[i]; for(;i=SIZE-2;i++) array[i-1]=array[i+1]; SIZE-=1; return x; printf(\nSize,SIZE); } int decrement(int *array,int i) {int c=0; while(array[i]array[i+1]){ c++; array[i]=array[i]-1; return c; } } int main() { int i,j,array[SIZE],count=0,flag=0; for(i=0;iSIZE;i++) scanf(%d,array[i]); while(!flag){ flag=1; j=1; i=0; do{ if(array[i]array[j]){ if((array[i]-array[j])array[j]) count=del(array,j); else count=decrement(array,i);flag=0; } j++;i++; }while(j=SIZE); } print(array); printf(\nTotal cost=%d,count); getch(); return 0; } -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] Re: Amazon interview Question (Array yet again!)
greedy won't work on 8,2,2,2,2,2,2... On Sat, Aug 28, 2010 at 7:39 AM, Gene gene.ress...@gmail.com wrote: This is a nice problem. It looks like a trivial matroid, so a greedy algorithm will work fine. The obvious greedy algorithm is to work left-to-right and incorporate elements into the sorted order one-by- one. In each case, you have 2 choices. The first is to decrement elements to the left by the amount needed to restore non-decreasing order. The second is to delete the new element. The cost of each is easy to calculate. Pick the choice with least cost and continue. This algorithm is O(n^2). There may be a faster way to do it, but I can't see one. #include stdio.h int make_nondecreasing(int *a, int n) { int i, j, dec, dec_cost, total_cost; total_cost = 0; for (i = 0; i n - 1; i++) { // If we find a decrease... if (a[i] a[i + 1]) { // Find cost of decrementing all to the left. dec_cost = dec = a[i] - a[i + 1]; for (j = i - 1; j = 0; j--) { // Find decrement that would be needed. dec += a[j] - a[j + 1]; // If no decement, we're done. if (dec = 0) break; // Count cost of decrement. dec_cost += dec; } // Compare decrement cost with deletion cost. if (dec_cost a[i + 1]) { // Decrement is cheaper. Do it. for (j = i; j = 0; j--) { if (a[j] a[i + 1]) a[j] = a[i + 1]; } total_cost += dec_cost; } else { // Deletion is cheaper. Do it. total_cost += a[i + 1]; for (j = i + 1; j n - 1; j++) a[j] = a[j + 1]; --n; } } } return total_cost; } int main(void) { int a[] = { 14, 15, 16, 13, 11, 18 }; //int a[] = { 4, 3, 5, 6}; //int a[] = { 10, 3, 11, 12 }; int cost = make_nondecreasing(a, sizeof a / sizeof a[0]); printf(cost=%d\n, cost); return 0; } On Aug 27, 12:15 pm, jagadish jagadish1...@gmail.com wrote: You are given an array of positive integers. Convert it to a sorted array with minimum cost. Only valid operation are 1) Decrement - cost = 1 2) Delete an element completely from the array - cost = value of element For example: 4,3,5,6, - cost 1 10,3,11,12 - cost 3 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- The Power to Believe in yourself, will become the power to change Fate. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] Re: AMAZON Interview Question
@harit.. logic plz.. not the code.. On Wed, Jul 14, 2010 at 9:50 PM, harit agarwal agarwalha...@gmail.comwrote: this is O(n) solution and using O(n) space... #includeiostream #includevector #includestack using namespace std; void leader_count(vectorint v,int *ar) { stackint s; int n=v.size(); int i=n-1; while(i=0) { if(s.empty()) { ar[--n]=0; s.push(i); i--; } else { if(v[i] = v[s.top()]) { ar[--n]=s.top(); s.push(i); i--; } else { s.pop(); } } } for(int i=v.size()-1;i=0;i--) if(ar[i]!=0) ar[i]=ar[ar[i]]+1; } main() { int i; vectorint v; while(cini) v.push_back(i); int *ar=new int[v.size()]; leader_count(v,ar); for(int i=0;iv.size();i++) coutar[i] ; } -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- With Regards Ankur Aggarwal -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] Re: AMAZON Interview Question
One approach will be while creating a BST and also store position of the element in the original array. While constructing ar_low check for two condition 1. element should be less than the given element and also position of element should greater than the given element. On Tue, Jul 13, 2010 at 4:01 AM, Vipul Agrawal vipul.itbh...@gmail.comwrote: // sort ar[] and store in temp[] -- o(nlogn) for(i=0 to n-1) { //search position of ar[i] in temp[] binary search --o(logn) ar_low[i] = pos-1; delete temp[pos]; } in binary search increase pos until next element is same . On Tue, Jul 13, 2010 at 4:09 PM, Amir hossein Shahriari amir.hossein.shahri...@gmail.com wrote: make a balanced bst which also has the size of subtree at each node start from ar[n-1] and insert each element and see what is it's rank in BST for finding the rank when inserting each time you pick the right subtree add size of left subtree to rank O(nlogn) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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] Re: AMAZON Interview Question
I guess it is a dynamic programming problem. On Wed, Jul 14, 2010 at 11:34 AM, Anand anandut2...@gmail.com wrote: One approach will be while creating a BST and also store position of the element in the original array. While constructing ar_low check for two condition 1. element should be less than the given element and also position of element should greater than the given element. On Tue, Jul 13, 2010 at 4:01 AM, Vipul Agrawal vipul.itbh...@gmail.comwrote: // sort ar[] and store in temp[] -- o(nlogn) for(i=0 to n-1) { //search position of ar[i] in temp[] binary search --o(logn) ar_low[i] = pos-1; delete temp[pos]; } in binary search increase pos until next element is same . On Tue, Jul 13, 2010 at 4:09 PM, Amir hossein Shahriari amir.hossein.shahri...@gmail.com wrote: make a balanced bst which also has the size of subtree at each node start from ar[n-1] and insert each element and see what is it's rank in BST for finding the rank when inserting each time you pick the right subtree add size of left subtree to rank O(nlogn) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks, Chakravarthi. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] Re: AMAZON Interview Question
this is O(n) solution and using O(n) space... #includeiostream #includevector #includestack using namespace std; void leader_count(vectorint v,int *ar) { stackint s; int n=v.size(); int i=n-1; while(i=0) { if(s.empty()) { ar[--n]=0; s.push(i); i--; } else { if(v[i] = v[s.top()]) { ar[--n]=s.top(); s.push(i); i--; } else { s.pop(); } } } for(int i=v.size()-1;i=0;i--) if(ar[i]!=0) ar[i]=ar[ar[i]]+1; } main() { int i; vectorint v; while(cini) v.push_back(i); int *ar=new int[v.size()]; leader_count(v,ar); for(int i=0;iv.size();i++) coutar[i] ; } -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] Re: AMAZON Interview Question
actually the problem is to make BST construction in O(nlogn)... we need rotations which changes the structure so you wont be able to distinguish between elements right to a particular elements, elements left to it . ( in original array ).. On Tue, Jul 13, 2010 at 12:52 AM, Tech Id tech.login@gmail.com wrote: Initialise all elements of ar_low with 0 for (int i=0; in-1; i++) { for (int j=i+1; jn-1; j++) { if (ar[j] = ar[i]) ar_low[i]++ ; } } O(n^2) For O(nlogn), create a BST - O(nlogn) Traverse the tree, counting children on the left side of each node and putting it ar_low - O(n) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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] Re: AMAZON Interview Question
make a balanced bst which also has the size of subtree at each node start from ar[n-1] and insert each element and see what is it's rank in BST for finding the rank when inserting each time you pick the right subtree add size of left subtree to rank O(nlogn) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] Re: AMAZON Interview Question
// sort ar[] and store in temp[] -- o(nlogn) for(i=0 to n-1) { //search position of ar[i] in temp[] binary search --o(logn) ar_low[i] = pos-1; delete temp[pos]; } in binary search increase pos until next element is same . On Tue, Jul 13, 2010 at 4:09 PM, Amir hossein Shahriari amir.hossein.shahri...@gmail.com wrote: make a balanced bst which also has the size of subtree at each node start from ar[n-1] and insert each element and see what is it's rank in BST for finding the rank when inserting each time you pick the right subtree add size of left subtree to rank O(nlogn) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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.