Re: [algogeeks] Amazon interview Question
@Rashmi: I did not get your approach. I do not get emails from the group just in case you have posted a solution :( What do you mean by keeping a count? Also, are you using a hashmap? If yes, whats ur K,V? #Pralay On Tue, Feb 12, 2013 at 10:00 AM, rashmi i rash...@gmail.com wrote: Hey Pralay, Sorry, if I have missed any point.Why would we need to map the frequencies when the second problem can be solved by simply keeping a count and comparing the index values that have been already mapped. On Fri, Feb 8, 2013 at 11:19 AM, sourabh jain wsour...@gmail.com wrote: One solution for the 2nd question can be LinkedHashMap (linked list + hashmap) . Store the integer in linked list in the order of occurrence in stream and make an entry in hashmap on first occurence. Delete the integer entry from linked list on 2nd occurence and replace the reference with some special value so for 3rd time no need to touch the linked list. while printing the result print first k integers from linked list. On Fri, Feb 8, 2013 at 9:46 AM, bharat b bagana.bharatku...@gmail.comwrote: @sourabh : how do u find whether the element in stream gets repeated in heap.-- O(n) time...totally its O(nk) algo .. If we maintain max-heap with BST property on index, then it would be O(nlogk). On Wed, Feb 6, 2013 at 12:25 PM, sourabh jain wsour...@gmail.comwrote: for 2nd question you can make a heap with their index as a factor to heapify them. whenever a integer in stream gets repeated you just nead to remove it from heap and heapify it. On Wed, Feb 6, 2013 at 10:00 AM, navneet singh gaur navneet.singhg...@gmail.com wrote: nice algo ankit, so it will be nlogn using O (n) space only. What abt 2nd Q., which have a big online stream. On Mon, Feb 4, 2013 at 9:30 PM, kumar ankit k.anki...@gmail.com wrote: For 1: i think you can use sorting, sort the array and keep the indices of the numbers in the sorted list. Now traverse the sorted list and in the sorted list you need to find the unique number with the minimum index which is easy to find. Eg: Array:5 3 1 2 4 1 4 Indices: 0 1 2 3 4 5 6 After sorting : Array:1 1 2 3 4 4 5 Indices: 2 5 3 1 4 6 1 Now you can see the unique number with lowest index is 3(index=1). So , you have your answer. On Mon, Feb 4, 2013 at 3:45 PM, navneet singh gaur navneet.singhg...@gmail.com wrote: 1. Given a array,find a first unique integer. 2. Integers are coming as online stream,have to find a kth unique integer till now. For 1. Even we cannot use sorting for solving this as if we sort it than our first number which is non-repetitive changes. The best I am able to do is nlogn using a space of O( n ). For 2. No idea -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- Kumar Ankit Senior Undergraduate Department of Computer Engineering Institute of Technology Banaras Hindu University Varanasi Ph: +91 9473629892 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- navneet singh gaur -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- Regards, Sourabh Kumar Jain +91-8971547841 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- Regards, Sourabh Kumar Jain +91-8971547841 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- R@$!-! DoN'T LimIt Ur cHaLlEngeS, ChAlLenGe uR LImItS. -- You received this
Re: [algogeeks] Amazon interview Question
Guys, Why can't we simply use a hashset for both the questions. hash the arr[i] and the frequencies in the hash map in the first pass. Then iterate over the array to find the first arr[i] whose freq is 1 in the hash map. For second part, keep a count and find the kth element in the array whose freq in the hashmap is 1. *Pralay MS-Comp Sci* *Univ of California* On Thu, Feb 7, 2013 at 8:16 PM, bharat b bagana.bharatku...@gmail.comwrote: @sourabh : how do u find whether the element in stream gets repeated in heap.-- O(n) time...totally its O(nk) algo .. If we maintain max-heap with BST property on index, then it would be O(nlogk). On Wed, Feb 6, 2013 at 12:25 PM, sourabh jain wsour...@gmail.com wrote: for 2nd question you can make a heap with their index as a factor to heapify them. whenever a integer in stream gets repeated you just nead to remove it from heap and heapify it. On Wed, Feb 6, 2013 at 10:00 AM, navneet singh gaur navneet.singhg...@gmail.com wrote: nice algo ankit, so it will be nlogn using O (n) space only. What abt 2nd Q., which have a big online stream. On Mon, Feb 4, 2013 at 9:30 PM, kumar ankit k.anki...@gmail.com wrote: For 1: i think you can use sorting, sort the array and keep the indices of the numbers in the sorted list. Now traverse the sorted list and in the sorted list you need to find the unique number with the minimum index which is easy to find. Eg: Array:5 3 1 2 4 1 4 Indices: 0 1 2 3 4 5 6 After sorting : Array:1 1 2 3 4 4 5 Indices: 2 5 3 1 4 6 1 Now you can see the unique number with lowest index is 3(index=1). So , you have your answer. On Mon, Feb 4, 2013 at 3:45 PM, navneet singh gaur navneet.singhg...@gmail.com wrote: 1. Given a array,find a first unique integer. 2. Integers are coming as online stream,have to find a kth unique integer till now. For 1. Even we cannot use sorting for solving this as if we sort it than our first number which is non-repetitive changes. The best I am able to do is nlogn using a space of O( n ). For 2. No idea -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- Kumar Ankit Senior Undergraduate Department of Computer Engineering Institute of Technology Banaras Hindu University Varanasi Ph: +91 9473629892 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- navneet singh gaur -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- Regards, Sourabh Kumar Jain +91-8971547841 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Amazon interview Question
I guess the part 1 can be solved in O(n) time and space both. Here is my approach. Assume: Array given is arr[] = {2,3,1,2,3,2,4,1,5,6} 1. Given an array, scan thru it, element by element and hash it on a hashmap with key as the arr[i] as the key and i+1 as the index. 2. There would be two cases a) arr[i] is already there in the hash map, if so, check if the hashmap.get(arr[i]) is a negative or not. If it is negative , do nothing. If its is not negative, negate it. b) arr[i] is a new element, in such a case, hash key as arr[i] and i+1 as the value. 3. Scan thru the value set, the key corresponding to minimum of positive values is the answer. Example. For {2,3,1,2,3,2,4,1, 5,6} 2 = not seen, hash 2,1 (arr[i], i+1) 3 = not seen, hash 3, 2 1 = not seen, hash 1,3 2 = seen - is the value corresponding to key 2 negative = No. So negate it- hash entry now becomes 2,-1 3 = similar to above - Hash entry is 3,-2 2 = seen, is the value negative = yes, do nothing 4 = not seen, hash 4,8 1 = seen, is the value corresponding to key 1 -ve? No, negate it, hashentry = 1,-3 5 = not seen, hash 5,10 6= not seen, hash 6,11 Hasmap ready. Whats the value set (the values only) ? -1,-2,-3,8,10,11 Whats the *least minimum of positive values*? 8 Whats the key corresponding to value 8? Its 4. *4 is the first unique number!* Please let me know if you need the code, shall send you ova :) Cheers, *Pralay* *MS,Comp Sci, * *University of California, Irvine* On Tue, Feb 5, 2013 at 8:30 PM, navneet singh gaur navneet.singhg...@gmail.com wrote: nice algo ankit, so it will be nlogn using O (n) space only. What abt 2nd Q., which have a big online stream. On Mon, Feb 4, 2013 at 9:30 PM, kumar ankit k.anki...@gmail.com wrote: For 1: i think you can use sorting, sort the array and keep the indices of the numbers in the sorted list. Now traverse the sorted list and in the sorted list you need to find the unique number with the minimum index which is easy to find. Eg: Array:5 3 1 2 4 1 4 Indices: 0 1 2 3 4 5 6 After sorting : Array:1 1 2 3 4 4 5 Indices: 2 5 3 1 4 6 1 Now you can see the unique number with lowest index is 3(index=1). So , you have your answer. On Mon, Feb 4, 2013 at 3:45 PM, navneet singh gaur navneet.singhg...@gmail.com wrote: 1. Given a array,find a first unique integer. 2. Integers are coming as online stream,have to find a kth unique integer till now. For 1. Even we cannot use sorting for solving this as if we sort it than our first number which is non-repetitive changes. The best I am able to do is nlogn using a space of O( n ). For 2. No idea -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- Kumar Ankit Senior Undergraduate Department of Computer Engineering Institute of Technology Banaras Hindu University Varanasi Ph: +91 9473629892 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- navneet singh gaur -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Amazon interview Question
Also, for the part two of the question, you can simply go in for the *kth largest positive index *in the same hashmap (described earlier for part 1). That solves the part two of the problem :) Hth, *Pralay Biswas* *MS,Comp Sci, * *University of California, Irvine* On Tue, Feb 5, 2013 at 8:46 PM, Pralay Biswas pralaybiswas2...@gmail.comwrote: I guess the part 1 can be solved in O(n) time and space both. Here is my approach. Assume: Array given is arr[] = {2,3,1,2,3,2,4,1,5,6} 1. Given an array, scan thru it, element by element and hash it on a hashmap with key as the arr[i] as the key and i+1 as the index. 2. There would be two cases a) arr[i] is already there in the hash map, if so, check if the hashmap.get(arr[i]) is a negative or not. If it is negative , do nothing. If its is not negative, negate it. b) arr[i] is a new element, in such a case, hash key as arr[i] and i+1 as the value. 3. Scan thru the value set, the key corresponding to minimum of positive values is the answer. Example. For {2,3,1,2,3,2,4,1, 5,6} 2 = not seen, hash 2,1 (arr[i], i+1) 3 = not seen, hash 3, 2 1 = not seen, hash 1,3 2 = seen - is the value corresponding to key 2 negative = No. So negate it- hash entry now becomes 2,-1 3 = similar to above - Hash entry is 3,-2 2 = seen, is the value negative = yes, do nothing 4 = not seen, hash 4,8 1 = seen, is the value corresponding to key 1 -ve? No, negate it, hashentry = 1,-3 5 = not seen, hash 5,10 6= not seen, hash 6,11 Hasmap ready. Whats the value set (the values only) ? -1,-2,-3,8,10,11 Whats the *least minimum of positive values*? 8 Whats the key corresponding to value 8? Its 4. *4 is the first unique number!* Please let me know if you need the code, shall send you ova :) Cheers, *Pralay* *MS,Comp Sci, * *University of California, Irvine* On Tue, Feb 5, 2013 at 8:30 PM, navneet singh gaur navneet.singhg...@gmail.com wrote: nice algo ankit, so it will be nlogn using O (n) space only. What abt 2nd Q., which have a big online stream. On Mon, Feb 4, 2013 at 9:30 PM, kumar ankit k.anki...@gmail.com wrote: For 1: i think you can use sorting, sort the array and keep the indices of the numbers in the sorted list. Now traverse the sorted list and in the sorted list you need to find the unique number with the minimum index which is easy to find. Eg: Array:5 3 1 2 4 1 4 Indices: 0 1 2 3 4 5 6 After sorting : Array:1 1 2 3 4 4 5 Indices: 2 5 3 1 4 6 1 Now you can see the unique number with lowest index is 3(index=1). So , you have your answer. On Mon, Feb 4, 2013 at 3:45 PM, navneet singh gaur navneet.singhg...@gmail.com wrote: 1. Given a array,find a first unique integer. 2. Integers are coming as online stream,have to find a kth unique integer till now. For 1. Even we cannot use sorting for solving this as if we sort it than our first number which is non-repetitive changes. The best I am able to do is nlogn using a space of O( n ). For 2. No idea -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- Kumar Ankit Senior Undergraduate Department of Computer Engineering Institute of Technology Banaras Hindu University Varanasi Ph: +91 9473629892 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- navneet singh gaur -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] reverse a string efficiently
Technically linear! On Mon, Nov 26, 2012 at 9:47 PM, shady sinv...@gmail.com wrote: what is the time complexity of this? str_reverse(str){ if(isempty(str)) return str; else if(length(str) = even) then split str into str_1 and str_2; (of equal length) (Calculate mid =O(1), then extract(0,mid) , extract(mid+1,end) return str_reverse(str_2)+str_reverse(str_1); Reversals again have linear dependence on length. else split str into str_1, str_2, str_3; //if str is odd length, e.g. len = 7, split by 1-3 | 4 | 5-7 return str_reverse(str_3)+str_2+str_reverse(str_1); } Similar argument for the odd length stuff. So the net complexity is in fact linear. --
Re: [algogeeks] reverse a string efficiently
Yes, my bad. I din notice the recursion at all! Thot it to be a flat mid-split followed by a reverse followed by a concat. Thanks. On Mon, Nov 26, 2012 at 11:18 PM, atul anand atul.87fri...@gmail.comwrote: considering '+' , here will take Cn time . Here '+' is for concatenate , now this concatenation taking place in constant time?? , i dont think so..internally it will be adding elements to new m/m space and for that it need to traverse each character...so it will take cn time. so T(n) =T(n/2) + cn = nlogn On Tue, Nov 27, 2012 at 11:17 AM, shady sinv...@gmail.com wrote: what is the time complexity of this? str_reverse(str){ if(isempty(str)) return str; else if(length(str) = even) then split str into str_1 and str_2; (of equal length) return str_reverse(str_2)+str_reverse(str_1); else split str into str_1, str_2, str_3; //if str is odd length, e.g. len = 7, split by 1-3 | 4 | 5-7 return str_reverse(str_3)+str_2+str_reverse(str_1); } -- -- --
Re: [algogeeks] fastest sequential access
i) vector = A non synced data structure good for random access and bad for insertions,deletions and sequential scans. ii) Singly linked list = Bad for random access, good for one way sequential access, good for insertions in the middle. iii) Doubly linked list = Bad for random access, best for two way sequential access, good for insertions in the middle. Pralay Biswas MS-CS, University of California Irvine On Wed, Nov 21, 2012 at 6:51 AM, shady sinv...@gmail.com wrote: which data structure among the follow has fastest sequential access ? i) vector ii) Singly linked list iii) Doubly linked list it won't be doubly linked list as it involves more pointer manipulations than singly linked list... -- --
Re: [algogeeks] fastest sequential access
I am sorry, vectors are synced and hence slow (concurrency overhead, arraylists are non synced). Rest remain the same, if your application demands frequent two way sequential scans, go for DLL. Pralay Biswas MS-CS, University of California Irvine On Wed, Nov 21, 2012 at 6:57 AM, Pralay Biswas pralaybiswas2...@gmail.comwrote: i) vector = A non synced data structure good for random access and bad for insertions,deletions and sequential scans. ii) Singly linked list = Bad for random access, good for one way sequential access, good for insertions in the middle. iii) Doubly linked list = Bad for random access, best for two way sequential access, good for insertions in the middle. Pralay Biswas MS-CS, University of California Irvine On Wed, Nov 21, 2012 at 6:51 AM, shady sinv...@gmail.com wrote: which data structure among the follow has fastest sequential access ? i) vector ii) Singly linked list iii) Doubly linked list it won't be doubly linked list as it involves more pointer manipulations than singly linked list... -- --
Re: [algogeeks] fastest sequential access
Also, vectors are not contiguously memory slotted always. Its a expanding array where the resizing takes place on demand. There are times when the array backing the vector is resized and re-allocated, but even then the amortized cost of insertion stays linear (O(n)). Although it makes sense to think that since all the microprocessor requires to do is an index*datasize calculation in case of an array or a vector, it would be interesting to note what happens to the execution runtime of two-way sequential access when there are frequent insertion-deletion-sequential-access cycles. My guess is that since there would be frequent insertions, that would trigger a vector doubling frequently (which translates to resizing and reallocation, an expensive operation). I guess if the application does frequent random insertions and random deletions and then looks for sequential accesses, DLL can beat vector. On Fri, Nov 23, 2012 at 9:00 AM, Atul Singh atulsingh7...@gmail.com wrote: @Pralay.. can u give a more detail about non synced data structure -- --
Re: [algogeeks] Re: time complexity of gcd euclid algo(recursive)
@Dave: Could you please correct me if am wrong here. 1) So we are looking out for the worst case, and that happens when m and n are consecutive Fibo numbers, being mutually prime to reach other. 2) Its taking 5 iterations to reduce the number of digits in the smaller of m and n, by one. Assuming there are h digits in the smaller number from now on. 3) Also, the computation cost is proportional to the number of digits, hence cost is proportional to h. (Could you please elaborate a lil more on this) 4) So net complexity is h*h = O(quadratic) On Fri, Nov 16, 2012 at 8:50 PM, Dave dave_and_da...@juno.com wrote: @Sonesh: Not so. The worst case for Euclid's algorithm is when the numbers are consecutive Fibonacci numbers. So (89,55) -- (55,34) -- (34,21) -- (21,13) -- (13,8) -- (8,5), so it took 5 steps to reduce the number of digits of the first number from 2 to 1. Asymptotically, the number of digits reduces by log_10(phi) = log_10((1+sqrt(5))/2) ~= 0.209, where phi is the Golden Ratio, so it takes, on average, ~4.78 iterations to reduce the numbers by 1 digit, in the worst case. But still, we can say that Euclid's algorithm is O(log n). Dave On Friday, November 16, 2012 6:40:58 PM UTC-6, sonesh wrote: you see, in each step of recursion, the number of digits in *n* is decrease by one(at least in worst case), so the complexity you can decide. On Tuesday, November 13, 2012 3:34:06 PM UTC+5:30, Shruti wrote: hi Can anyone help me find out the time complexity of recursive gcd algorithm (using euclid's algo) i.e. for the following program : int gcd(int n,int m) //given nm { if(n%m==0) return m; else return gcd(m,n%m); } i think the soln is lg(a*b) but have no idea how.. -- 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/-/bCB-L41X6ukJ. 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] BIG O
@ Siddharth : Well, here is how you may understand it: 1) There is an outer loop that runs n times. (k) 2) Then there is an inner loop where j is initially set to current k, but it halves itself in every iteration -- So for example, if k is 32, and j halves every time, then the inner loop runs for 5 times (32-16-8-4-2 etc) -- This is a log base 2 order depreciation in for all k 3) So for every k, the inner loop runs for log k times. k itself varies from 1 to n, hence O(nlogn) Hope this helps. #Pralay MS-CS, UC Irvine On Sun, Oct 28, 2012 at 10:38 AM, bharat b bagana.bharatku...@gmail.comwrote: while loop : logj base 2 .. == log1 + log2 + ... logn = log(n!) [since logab = loga + logb] == O(log(n^n)) = O(nlogn) On Sun, Oct 28, 2012 at 3:56 AM, Siddharth Malhotra codemalho...@gmail.com wrote: Can somebody explain how it is O(n log n). What is the significance of while loop in the above code? I understand that the for loop implies O(n),does the log n in the O(n log n) comes from the while loop? What if there where two while loops in the for loop separately? On Sat, Oct 27, 2012 at 3:26 AM, Pralay Biswas pralaybiswas2...@gmail.com wrote: Yes! On Fri, Oct 26, 2012 at 2:55 PM, rahul sharma rahul23111...@gmail.comwrote: for k=1 to n { j=k; while(j0) j=j/2; } the complexity is big o is o(nlogn) am i ryt -- 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. -- 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] BIG O
Yes! On Fri, Oct 26, 2012 at 2:55 PM, rahul sharma rahul23111...@gmail.comwrote: for k=1 to n { j=k; while(j0) j=j/2; } the complexity is big o is o(nlogn) am i ryt -- 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: Microsoft interview question
@Piyush: Try this i/p 8,0,0 ; 2,6,0-- Ur algo aint adequate.. On Sat, May 19, 2012 at 11:24 PM, Piyush Khandelwal piyushkhandelwal...@gmail.com wrote: Hiii!! I have some idea about the solution. Please notify me if i am wrong a= [ 4,3,5 ] and b= [ 3,5,4 ] diff=0; for (i=0; in;i++) { diff= diff+a[i]-b[i]; } if diff == 0 print: permutation else print: not permutation On 20 May 2012 07:2 0, Dave dave_and_da...@juno.com wrote: @Harshit: These are a few unanswered questions that came to mind when I read your solution attempt: What do you do with negative elements? What is the -12th prime number? How do you deal with overflow in the cases where you have a lot of large prime numbers and the product exceeds your native data types? Dave On Saturday, May 19, 2012 2:29:52 PM UTC-5, harshit pahuja wrote: given 2 unsorted integer arrays a and b of equal size. Determine if b is a permutation of a. Can this be done in O(n) time and O(1) space ? please help me with my solution suppose a -- 3 5 4 b -- 4 3 5 now we replace a[i] with a[i]..th prime number and b with b[i] .. th prime number now array a becomes 5 11 7 array b becomes 7 5 11 now we take product of elements of array a and do the same with array b elements if product is equal then b is a permutation of a -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/WEW0M5VUUVEJ. 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. -- *Piyush Khandelwal*** Mobile No: 91-8447229204 91-9808479765 -- 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] Permutations of a string
Nice solution Akshay. Here is my small attempt! [image: Inline image 1] #Pralay On Mon, May 7, 2012 at 1:03 AM, Akshay Rastogi akr...@gmail.com wrote: private static void swap(char[] str, int i,int j) { char temp = str[i]; str[i] = str[j]; str[j] = temp; } private static void permute (char[] str, int strCurrIndex) { if (strCurrIndex == (str.length-1)) { System.out.println(str); return; } for (int i = strCurrIndex; i str.length; i++) { swap(str, i, strCurrIndex); permute(str, (strCurrIndex+1)); swap(str, i, strCurrIndex); } return; } public static void main (String[] args) { char[] str = {'a','b','c'}; permute(str, 0); } On Mon, May 7, 2012 at 12:59 PM, Sairam Ravu ravu...@gmail.com wrote: Somebody please help me!! -- With love and regards, Sairam Ravu I M.Tech(CS) Sri Sathya Sai Institute of Higher Learning To live life, you must think it, measure it, experiment with it, dance it, paint it, draw it, and calculate 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. -- AKSHAY RASTOGI BE(Hons) CS BITS PILANI , Pilani -- 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. image.png