FastPrep
Problem · Heap

Running Delivery Time Medians

Learn this problem
● MediumAmazonFULLTIMEONSITE INTERVIEW
See Amazon hiring insights

Problem statement

Given an array deliveryTimes, process the values from left to right. After each new delivery time arrives, output the median of all delivery times seen so far.

When the number of seen values is even, use the lower median, meaning the larger value in the lower half after sorting.

Return an array containing the median after each insertion.

Source note: The source only shared a short prompt and one example. FastPrep filled in the explanation and clarified the constraints from that example, especially the lower-median behavior, so the problem is easier to practice. If you find a fuller source, feel free to let us know and we will update it. Thank you! 🦩

Function

runningDeliveryMedians(deliveryTimes: int[]) → int[]

Examples

Example 1

deliveryTimes = [5,17,100,11]return = [5,5,17,11]

The sorted prefixes are [5], [5,17], [5,17,100], and [5,11,17,100]. Their lower medians are 5, 5, 17, and 11.

Constraints

  • deliveryTimes are processed from left to right.
  • After each new value is inserted, record the median of all values seen so far.
  • When the number of seen values is even, use the lower median: the larger value in the lower half after sorting.
  • Return one median for each insertion.

More Amazon problems

drafts saved locally
public int[] runningDeliveryMedians(int[] deliveryTimes) {
  // write your code here
}
deliveryTimes[5,17,100,11]
expected[5,5,17,11]
checking account