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, 15:18
