Re: [algogeeks] Amazon: sort array
Something like merge sort should do. On Sat, Jul 3, 2010 at 12:00 AM, ANKUR BHARDWAJ ankibha...@gmail.com wrote: Given an array of n elements and an integer k where kn. Elemnts {a[0].a[k] and a[k+1].a[n] are already sorted. Give an algorithm to sort in O(n) time and O(1) space. -- 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. -- Siddharth Prakash Singh http://www.spsneo.com -- 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.
[algogeeks] Monte Carlo Algorithm to find a repeated element
An array arr has n/4 copies of a particular unknown element x. Every other element in arr has at most n/8 copies. Give an O(logn) time Monte Carlo alorithm to identify x. The answer should be correct with high probability. -- 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] Sort the data from a big file.
This wikipedia article on external sorting may help : http://en.wikipedia.org/wiki/External_sorting On Mon, Dec 21, 2009 at 8:18 PM, Abhilash L L llabhil...@gmail.com wrote: A merge sort would be helpful i guess... it can also happen in parallel and IIRC databases use them internally. Please correct me if im wrong. Regards, Abhilash On Mon, Dec 21, 2009 at 7:06 PM, dinesh bansal bansal...@gmail.comwrote: On Mon, Dec 21, 2009 at 6:47 PM, Linus Probert linus.prob...@gmail.comwrote: If the numbers are unique you could use a bitmap-sort this way you could easily read just parts of the file at a time. If they aren't unique it gets a bit trickier. /L dinesh bansal wrote: Hi All, Suppose I have a big file (~100M) containing integer data. I want to sort this file. The problem is I don't want to load the complete file data into main memory in one shot. I mean I can read the file in batches and sort the batch and save it in another file but cannot store the entire file contents in main memory. Can somebody help me with algorithm or pseudo code? Thanks in advance. -- 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. Hi Linus, Thanks for the reply. But yes we cannot guarantee that data value are unique. -- Dinesh Bansal The Law of Win says, Let's not do it your way or my way; let's do it the best way. -- 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. -- Siddharth Prakash Singh http://www.spsneo.com -- 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.
[algogeeks] Finding first and last k digits of n^n
Can anybody suggest an algorithm to find first and last k digits of n^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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=.
Re: [algogeeks] Finding first and last k digits of n^n
On Mon, Nov 23, 2009 at 3:57 PM, Saurabh Aggarwal saurabh...@gmail.comwrote: Could you explain it with an example ? I hope you are considering that n^n may be well beyond any datatype range. Yes I am considering n to be well beyond any datatype range. On Mon, Nov 23, 2009 at 3:24 PM, Bharath bharath1...@gmail.com wrote: For first k digits: (unsigned long)floor(pow(10.0, modf(n*log10((double)n), dummy) + k - 1)) On Mon, Nov 23, 2009 at 3:24 PM, Bharath bharath1...@gmail.com wrote: For last k digits int foo(int n, int k) { int m=1; for(; k 0; k--) m*=10; int r=1, t=n % m; while(n) { if (n % 2) r = r * t % m; t = t * t % m; n = 1; } return r; } On Sat, Nov 21, 2009 at 9:44 AM, Siddharth Prakash Singh sps...@gmail.com wrote: Can anybody suggest an algorithm to find first and last k digits of n^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=. -- Bharath -- Bharath -- 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=. -- Regards, Saurabh 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=. -- Siddharth Prakash Singh http://www.spsneo.com -- 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=.