Sean.B.Wan
BAN USERagree. Median of Medians algorithm is what interviewer want. But my question is how many people can implement Median of Medians algorithm in half an hour?
This question is ridicule.
I guess this is assignment not interview question
- Sean.B.Wan March 26, 2012Master mothed.
T(n) = a *T(n/b) + f(n)
here a = 3, b = 3
a *T(n/b) contributes the same as f(n) dose.
Therefore nlog(n)
Since it is a big big book, internal sorting or internal data structure may not work.
My solution is split the whole book into K buckets.
handle bucket one by one.
For firest bucket, take 20% of top frequency words to build a maxheap.
When next bucket comes in, maintain the maxheap.
After read all bucket, the words on the top of the maxheap is most frequent words.
Do not know if it works. I will be very happy if it is corrected.
can we use heapsort? Since we just need k-th. readjustment will cost log(n). But we just need readjust k times. So the total cost is klog(n) for sorting part.
- Sean.B.Wan March 03, 2012
put two pointers pointing to head. first pointer move 2 each time, the second pointer just 1. if they meet. then there is a loop.
- Sean.B.Wan May 22, 2013pointer1 = head.next.next.
pointer2 = head.next.
while(pointer1 != null){
pointer1 = pointer1.next
pointer2 = pointer2.next
if pointer1 == pointer2 return has loop
pointer1 = pointer1.next
if pointer1 == pointer2 return has loop
}