Re: [algogeeks] Re: another google telephone interview question
I think one way to solve is to build a max heap of the array(in place). Now remove the max element and keep it at the end and reheapify. This algorithm takes O(nlogn). I am not able to think how to make O(nlogk). -- 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: another google telephone interview question
I think you don't need to use the median number as pivot. As long as you use different number to do partition, after log(k) times recursive, the N element will be sorted. On Sun, May 23, 2010 at 3:17 PM, Jagadish M jagadis...@gmail.com wrote: Further to my previous post, one question. Can the median be found in O(n) time without using extra memory? I am not familiar with the algorithms that find the median though I know the median can be found in O(n) time. This is important! I don't see how the standard algorithm for median finding can be tweaked to use only constant extra space. @Bharath: It's a nice algorithm, nevertheless :) -Jagadish http://www.cse.iitb.ac.in/~jagadishhttp://www.cse.iitb.ac.in/%7Ejagadish -- 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. -- Liu Yan -- 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: another google telephone interview question
how about using binary index tree?? On Tue, May 25, 2010 at 5:41 PM, liu yan ryu...@gmail.com wrote: I think you don't need to use the median number as pivot. As long as you use different number to do partition, after log(k) times recursive, the N element will be sorted. On Sun, May 23, 2010 at 3:17 PM, Jagadish M jagadis...@gmail.com wrote: Further to my previous post, one question. Can the median be found in O(n) time without using extra memory? I am not familiar with the algorithms that find the median though I know the median can be found in O(n) time. This is important! I don't see how the standard algorithm for median finding can be tweaked to use only constant extra space. @Bharath: It's a nice algorithm, nevertheless :) -Jagadish http://www.cse.iitb.ac.in/~jagadishhttp://www.cse.iitb.ac.in/%7Ejagadish -- 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. -- Liu Yan -- 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. -- yezhu malai vaasa venkataramana Govinda Govinda -- 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: another google telephone interview question
Find the median of the values and move the lower values to left and higher
values to the right. This can be done in o(n). now do the same on both the
parts recursively. And the total complexity will be o(nlogk).
On Fri, May 21, 2010 at 1:12 PM, Shachin Sharma shac...@gmail.com wrote:
No heapify will not barf. Here is how it goes:
Whenever you get a node value root value (you have already determined the
root value in first scan) you are sure that this isnt the actual value can't
be in a heap. So determine actual value.
if (pres_node_value root_value say R) //Value keeps frequency and isnt
actual
Call get_actual_value (pres_node_value)
get_actual_value (pres_node_value)
{
frequency_of_occurence = pres_node_value /R = Quotient
actual_value = pres_node_value % R = remainder
So e.g. when 2 is repeated twice and root value is 3 you will store (2
+ 3 +3 = 8). When you see 8 you know it is ROOT = 3 so get_actual_value
(8) will give 8/3 = 2 = frequency and 8% 3 = 2 = actual value.
}
Rest of heapify insertion works as usual. This way nothing in heap changes,
no property. And by the way how can you save bits in an integer ?? It is
always 4 bytes (on most of platforms) whether its = 1 or 1 + 1000 ? If you
said that there could be overflow I would still have agreed but I dont think
you are saving bits. In fact in your solution a whole new 4 byte chunk is
used when you keep something like 2:1 which is O(K) space and violates the
in-place property which says that extra space should have upper bound logn.
Thanks,
Sachin
On Thu, May 20, 2010 at 7:59 PM, Piyush Verma 114piy...@gmail.com wrote:
@shachin,when u add value of root in the child of root then for insertion
of new element when heap is called(so heapify is called) so now this child
becomes root which is not desired..
plzz correct me if i m wrong
--
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.
--
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.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: another google telephone interview question
Hi Jagdish, I think your solution looks good. The only thing about extra space to store count can be dealt with like this in my view: 1) Do a scan of numbers and determine the max number. 2) Create a max heap (Root is the largest number so by step 1 we have determined the Root for the heap). 3) Whenever a number repeats instead of storing the count store modify the number to (number + ROOT Value) ie for 2 which is repeated twice 2 + 3 +3 = 8 instead of 2:3 as you give in your example. 4) Since in a heap no number can be greater than root value whenever a number greater than ROOT (here 3) is accessed/encountered we know the frequency by subtracting till the number is root value. For example when you see 8 subtract value 3 till number is less than 3. Which means 8-3-3 or frequency =2 for the number. Number of subtractions is the frequency of occurrence. So we don't need extra space to determine frequency but with some extra computation can determine the count at runtime. There can be better ways than addition but you get the basic idea of not using any extra space O(k). What do you think? Personally I feel space isn't that big a issue specially if its linear but interviewer is the boss ;-) Regards, Sachin On Tue, May 18, 2010 at 7:01 PM, Jagadish M jagadis...@gmail.com wrote: On May 18, 8:29 am, Terence technic@gmail.com wrote: How do you maintain the heap? Could you explain in detail for the following example: 1 2 3 3 2 1 1 1 2 3 (n=10, k=3) Basically, in each node we maintain the key and its count. Initially, heap has the first element. 1:1 Search for 2 and insert( since its not found) 1:1 / 2:1 Search for 3 and insert ( since its not found). 1:1 / \ 2:13:1 Search for 3; since 3 is already there increment its count by 1. 1:1 / \ 2:13:2 Search for 2; since 2 is already there increment its count by 1. 1:1 / \ 2:23:2 and so on... Since, there are only k distinct keys the heap size will at most be k; so each search/insert/increment operation takes O(log k) time. Jagadish http://www.cse.iitb.ac.in/~jagadish On 2010-5-17 22:38, Jagadish M wrote: The best algorithm I can think of is to maintain a heap of k elements. Takes O(n log k) time. Is anything told about the values of the keys? If the keys have values less than N, then it is possible to do what you say, i.e sort them in place. -Jagadish http://www.cse.iitb.ac.in/~jagadish On May 13, 7:06 pm, divyasweetdivya@gmail.com wrote: This problem was asked in google phone interview. We have N element array with k distinct keys(No relation between k N given so assume kN) What is the best method to sort this array without using any extra memory? Please elaborate. -- 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 athttp:// 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 athttp:// 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: another google telephone interview question
@shachin,when u add value of root in the child of root then for insertion of new element when heap is called(so heapify is called) so now this child becomes root which is not desired.. plzz correct me if i m wrong -- 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: another google telephone interview question
i think we can use sorting algorithm like insertion sort, in insertion sort whenever we are putting the element into it's proper position we can check whether this elements already exists don't put otherwise insert into into it's proper position (element) -- Prashant Kulkarni || Lokaha Samastaha Sukhino Bhavanthu || || Sarve Jana Sukhino Bhavanthu || On Wed, May 19, 2010 at 4:09 AM, Aarthi Thangamani aarthi.thangam...@gmail.com wrote: If you are using an extra space to count, why need a heap? An array of size k can be used to first count the occurances. Then run through the original array of size N and fill it according to the count our occirances using the constant k size array. Space O(k) and time O(N) is the best thing I think of. :( On Tue, May 18, 2010 at 7:11 PM, CHERUVU JAANU REDDY jaanu.cher...@gmail.com wrote: Here u r using extra space to store count values.. CHERUVU JAANU REDDY M.Tech in CSIS On Tue, May 18, 2010 at 7:01 PM, Jagadish M jagadis...@gmail.com wrote: On May 18, 8:29 am, Terence technic@gmail.com wrote: How do you maintain the heap? Could you explain in detail for the following example: 1 2 3 3 2 1 1 1 2 3 (n=10, k=3) Basically, in each node we maintain the key and its count. Initially, heap has the first element. 1:1 Search for 2 and insert( since its not found) 1:1 / 2:1 Search for 3 and insert ( since its not found). 1:1 / \ 2:13:1 Search for 3; since 3 is already there increment its count by 1. 1:1 / \ 2:13:2 Search for 2; since 2 is already there increment its count by 1. 1:1 / \ 2:23:2 and so on... Since, there are only k distinct keys the heap size will at most be k; so each search/insert/increment operation takes O(log k) time. Jagadish http://www.cse.iitb.ac.in/~jagadishhttp://www.cse.iitb.ac.in/%7Ejagadish On 2010-5-17 22:38, Jagadish M wrote: The best algorithm I can think of is to maintain a heap of k elements. Takes O(n log k) time. Is anything told about the values of the keys? If the keys have values less than N, then it is possible to do what you say, i.e sort them in place. -Jagadish http://www.cse.iitb.ac.in/~jagadishhttp://www.cse.iitb.ac.in/%7Ejagadish On May 13, 7:06 pm, divyasweetdivya@gmail.com wrote: This problem was asked in google phone interview. We have N element array with k distinct keys(No relation between k N given so assume kN) What is the best method to sort this array without using any extra memory? Please elaborate. -- 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 athttp:// 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 athttp:// 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. -- 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: another google telephone interview question
Heap maintains the word and frequency count On 5/18/10, Terence technic@gmail.com wrote: How do you maintain the heap? Could you explain in detail for the following example: 1 2 3 3 2 1 1 1 2 3 (n=10, k=3) On 2010-5-17 22:38, Jagadish M wrote: The best algorithm I can think of is to maintain a heap of k elements. Takes O(n log k) time. Is anything told about the values of the keys? If the keys have values less than N, then it is possible to do what you say, i.e sort them in place. -Jagadish http://www.cse.iitb.ac.in/~jagadish On May 13, 7:06 pm, divyasweetdivya@gmail.com wrote: This problem was asked in google phone interview. We have N element array with k distinct keys(No relation between k N given so assume kN) What is the best method to sort this array without using any extra memory? Please elaborate. -- 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 athttp://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. -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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.
