Spot a repeated order id within a recent window

Question

A feed streams order ids. A duplicate id is only a problem if it recurs soon, within k messages of its earlier appearance (later repeats are legitimate reuse). You want to flag whether any such near-duplicate exists.

ids = [1, 2, 3, 1], k = 3
-> True           # the two 1s are 3 positions apart, and 3 <= k

ids = [1, 2, 3, 1], k = 2
-> False          # the two 1s are 3 apart, but 3 > k

Return True if some value repeats within k positions, else False. Aim for $O(n)$ .

Accepted Answer

Keep a map from value to the index where you last saw it. For each element, if it appeared before and the gap to that last sighting is at most k, you have a near-duplicate. Either way, overwrite the stored index so it always holds the most recent position, the only one that can be within k of a future occurrence. Tracing [1, 2, 3, 1], k = 3: after 1, 2, 3 the map is {1:0, 2:1, 3:2}. At i = 3, x = 1 was last at index 0, gap 3 - 0 = 3 \le 3, return True. With k = 2 the gap 3 2, so it updates last[1] = 3 and finishes False. Time O(n), space O(\min(n, 	ext{distinct ids})). Storing only the lates…

Spot a repeated order id within a recent window

Your answer

More Coding questions