FastPrep
Problem

Dynamic Kth Largest Queries

AmazonFULLTIMEONSITE INTERVIEW
See Amazon hiring insights

You are given an initial list of integer values and a stream of operations. The list changes over time as values are inserted.

Each operation is one of the following:

  • "insert": insert the accompanying value into the list.
  • "find": treat the accompanying value as k and return the current k-th largest value in the list.

Return the answers to all "find" operations in order.

Examples
01 · Example 1
initialValues = [3, 7, 1]
operations = ["find", "insert", "insert", "find", "find"]
values = [3, 4, 9, 2, 4]
return = [1, 7, 3]

Initially the sorted values are [1,3,7], so the 3rd largest is 1. After inserting 4 and 9, the values are [1,3,4,7,9]; the 2nd largest is 7 and the 4th largest is 3.

02 · Example 2
initialValues = [5]
operations = ["insert", "find", "insert", "find"]
values = [2, 1, 10, 2]
return = [5, 5]

After inserting 2, the largest value is 5. After inserting 10, the 2nd largest value is still 5.

Constraints
  • operations.length == values.length
  • Each operation is either "insert" or "find".
  • For each "find" operation, 1 <= k <= the current list size.
More Amazon problems
drafts saved locally
public int[] dynamicKthLargestQueries(int[] initialValues, String[] operations, int[] values) {
  // write your code here
}
initialValues[3, 7, 1]
operations["find", "insert", "insert", "find", "find"]
values[3, 4, 9, 2, 4]
expected[1, 7, 3]
sign in to submit