FastPrep
Problem

Dynamic Kth Largest Queries

Learn this problem
Amazon logoAmazonFULLTIMEONSITE INTERVIEW
See Amazon hiring insights

Problem statement

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.

Function

dynamicKthLargestQueries(initialValues: int[], operations: String[], values: int[]) → int[]

Examples

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.

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]
checking account