Interview Question

Associate Software Engineer Interview

-Hyderābād

Amazon

In Array find largest second number ?

AnswerAdd Tags

Interview Answers

5 Answers

2

Can,t we do sorting from largest to smallest give arr[1] which is of course second largest

Dheeraj on

1

It Took Time but Simple logic is needed.

Anonymous on

0

Would be impressive to solve the general case... find the kth large number: create a minheap of size k, and for each element in the array, if that number is bigger than the top of the minheap, replace the top of the minheap with that number and recreate the minheap. Running time is O(nlgn). If you can have negative numbers, then you can easily modify this code. int findKthLargestNumber(int[] A, int k) { if (k minHeap[2*i+1]) { int temp = minHeap[i]; minHeap[i] = minHeap[2*i+1]; minHeap[ 2*i+1] = temp; i = 2*i+1; } else if (minHeap.length minHeap[2*i+2)]) { int temp = minHeap[i]; minHeap[i] = minHeap[2*i+2]; minHeap[ 2*i+2] = temp; i = 2*i+2; } else { done = true; } }

Zach on

0

Since it asks for the second largest number, you can define two variables: theLargest theSecondLargest And scan the array and update these two variables accordingly. If it extends to find the Kth number and K is not very large (e.g. 1000), you can use a minHeap with size K. If the value of K can be very large, you can talk with the interviewer the pros and cons of these two methods: 1) MInHeap 2) QuickSelect

Yan on

0

Yes we can do sorting. But it's unnecessary. We can do it in O(n). I.e one traversal by maintaining two variables. Max and second max

Anonymous on

Add Answers or Comments

To comment on this, Sign In or Sign Up.