hcmurthy
BAN USER
Comments (6)
Reputation 0
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
I think we need to use a min heap to get the two of the smallest numbers (in general n-element min heap to find the first n smallest numbers).
- hcmurthy February 14, 20111. Create a min heap using A[0] and A[1];
2. Now for each element from 2 to n-1; for(i = 2; i < n; ++i)
3. If A[i] > heap[0], then exchange A[i] and heap[0. Heapify to restore the min heap property. Since this is a 2-element min heap, time taken for heapify is constant (usually it is O(log n)). Hence, the complexity would be O(n).
4. Finally, the two numbers in the heap are the smallest two numbers.