FastPrepAuction Sniping Window Minimum

Auction Sniping Window Minimum

Cisco logoCisco● MediumFULLTIMEOA

Problem statement

You are given n pairs (times[i], values[i]), listed in order of non-decreasing time, and two integers windowLength and k.

For each index i, look at the window of pair i: every pair j with j <= i and times[i] - windowLength <= times[j] <= times[i]. Pair i itself is in its window, and pairs that come later in the list are never in it, even when they have the same time.

The answer for index i is the smallest value that appears at least k times among the values in its window. If no value appears k times, the answer is -1.

Return an array answer of length n, where answer[i] is the answer for index i.

Function

smallestFrequentValues(times: int[], values: int[], windowLength: int, k: int) → int[]

Examples

Example 1

times = [1,2,3,5,6]values = [4,2,4,2,2]windowLength = 3k = 2return = [-1,-1,4,2,2]

Each window covers times from times[i] - 3 to times[i].

  • Index 0 (time 1): the window holds only value 4, once. No value appears twice, so the answer is -1.
  • Index 1 (time 2): values 4 and 2, once each, so -1.
  • Index 2 (time 3): values 4, 2, 4. Value 4 appears twice, so the answer is 4.
  • Index 3 (time 5): the window starts at time 2, so it holds values 2, 4, 2. The answer is 2.
  • Index 4 (time 6): the window starts at time 3, so it holds values 4, 2, 2. The answer is 2.

Example 2

times = [5,5,5]values = [7,7,3]windowLength = 0k = 2return = [-1,7,7]

All three pairs have time 5, but a window only holds pairs up to its own index.

The window of index 0 holds one 7, so its answer is -1. The window of index 1 holds two 7s, so its answer is 7. The window of index 2 holds 7, 7, 3. Only 7 appears twice, so its answer is 7.

Example 3

times = [0,10,20,30]values = [9,5,8,1]windowLength = 10k = 1return = [9,5,5,1]

With k = 1, the answer is the smallest value in each window. Both ends of a window are included.

The windows hold [9], [9, 5], [5, 8], and [8, 1]. For index 2, time 10 is exactly 20 - 10, so the pair with value 5 is still inside. The answers are 9, 5, 5, and 1.

Constraints

  • 1 <= times.length <= 10^4
  • values.length == times.length
  • 0 <= times[i] <= 10^9
  • times[i] <= times[i + 1] for every valid i.
  • 1 <= values[i] <= 10^9
  • 0 <= windowLength <= 10^9
  • 1 <= k <= times.length

More Cisco problems

See Cisco hiring insights
Saved
public int[] smallestFrequentValues(int[] times, int[] values, int windowLength, int k) {
    // Write your solution here.
}
Checking account…