You are not logged in. Please login at to post your questions!


Chef and his software - TSECJ05 - Editorial


Chef and his software

Author: Yogesh Malpani
Editorialist: Yogesh Malpani




ArrayList, Binary Search, Heap


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.


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.


How to process a new transaction of record, Ni?
For every Ni, check if it is smaller than current Kth largest element.
If yes, then ignore it. If no, then a modification of Binary Search can be used to find the index for the Ni. This can be done in O(LogN) time.
The transaction value is added at an index in the ArrayList which runs in amortized constant time, O(N) time.
So the Time complexity of processing a new transaction is O(N + LogN).
The Kth highest transaction is found in the ArrayList in constant time, O(1).


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.
How to process a new transaction of record?
Compare the new transaction value, Ni, with root of heap. If Ni is smaller, then ignore it. Otherwise replace root with Ni and call heapify for the root of modified heap. Time complexity of finding the Kth highest transaction is O(LogN).


Solution can be found here.

This question is marked "community wiki".

asked 02 Jul, 15:18

crazdhacker101's gravatar image

accept rate: 0%

edited 02 Jul, 17:11

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 02 Jul, 15:18

question was seen: 193 times

last updated: 02 Jul, 17:11