Brave Heart
BAN USEROh, I saw the fact that extra memory shouldn't be used. That's kind of weird they would tell you such a thing. I am open to seeing other solutions.
The other way to do it would be to use segment trees to find the minimum in O(1). Updates to the tree will take O(logN). Then again seg trees take O(N) space.
We have N Lists. Maintain a min heap of size N. The heap will store the top value of all the lists initially and will help in getting the min at any point of time in O(1). Each node in the heap will also store a reference to the list it belongs to, inorder to handle duplicates. Have N pointers pointing to the top of the N lists. Do the same thing merge sort does, but get the min in O(logN) time instead of doing O(N) comparisons.
- Brave Heart April 06, 2014You are supposed to not just find the maximum number, but find the overlapping intervals that result in the particular max. How does your algorithm do that?
- Brave Heart February 28, 2014This is not fully true incase of micro-kernels and also the Linux kernel which has "worker threads" and "workqueues".
- Brave Heart March 12, 2013That is not a correct answer. Read up on concepts of kernel threads and micro kernels. Further a good portion of the kernel executes on behalf of a process during system calls and is not even a "thread".
- Brave Heart March 12, 2013copy_from_user does not page fault unlike other kernel or user code sections when an attempt happens to access memory addresses passed by userspace. This allows it to gracefully handle exception instead of kernel panic.
- Brave Heart March 12, 2013Hi!
Each x and y are grouped together as a single point. There are n such points. Hence O(n)
Yes, thanks :)
- Brave Heart November 25, 2010Hi, I don't think there is a linear algorithm to search for k min/max elements in an array that is not sorted.
It will be > O(n) no matter which algorithm you use.
Above solutions are too trivial, a better solution would be
compute x^2 + y^2 (no need sqrt!) and transform into another array. O(n)
Next,
build a Max Heap (Q) out of the first k elements in the array. ---> O(k)
For all elements from k+1..n , if a[i] < Q.min() ,
then Q.replace(Q.min() , a[i])
Q.downheap()
The above loop will take a total time of O(nlogk) in the worst case.
After the loop terminates, the contents of the heap is the k closest elements to the origin.
The total running time of this algorithm = O(n + nlogk)
If you use the trivial sorting method, it will take O(nlogn) . If n is very large, and if k is small, then you can see how inefficient sorting is.
The solution to the problem is the same as the unbounded knapsack problem and can be solved in pseudo polynomial time.
- Brave Heart April 06, 2014