PROBLEM LINK:Author: Yogesh Malpani DIFFICULTY:MEDIUM. PREREQUISITES:ArrayList, Binary Search, Heap PROBLEM:Given the values of N transactions, the task is to insert these to records and print the value of Kth highest transaction in the records at each insertion. QUICK EXPLANATION:Find the index for the each new transaction using efficient Sorting algorithms which work well on an almost sorted list. Next find the Kth highest transaction and print it. EXPLANATION:How to process a new transaction of record, Ni? ALTERNATIVE SOLUTION:Another Solution is to use Min Heap of size N to store N largest transactions of records. The Kth highest transaction is always at root and can be found in O(1) time. AUTHOR'S SOLUTION:Solution can be found here.
This question is marked "community wiki".
asked 02 Jul '17, 15:18

Java users kindly use "Fast I/O" else get ready to experience "NZEC". answered 23 Nov '17, 14:21

I used Two heaps. One min heap and one max heap. https://ideone.com/ATY9yH answered 09 Dec '17, 17:42
