Release the Buffered Packets
Easy About 15 min Free, no account needed
Report how far an ordered stream can advance as packets arrive late, out of order, or more than once.
The brief
A receiver must deliver packets in order, starting with packet 1. It can hold packets that arrive early, and the sender may retry a packet that has already arrived.
Given the arrival order packets, return an array of the same length. After each arrival, report the largest packet number r for which every packet from 1 through r has arrived at least once. Report 0 while packet 1 is missing. The answer is the cumulative delivery frontier, not the number of packets released by that arrival.
For packets = [3, 1, 2, 2, 5, 4], return [0, 1, 3, 3, 3, 5]:
| Arrival | Delivery frontier | Reason |
|---|---|---|
3 |
0 |
Packet 1 is still missing. |
1 |
1 |
Packet 2 is still missing. |
2 |
3 |
Packets 1, 2, and 3 have all arrived. |
2 |
3 |
Receiving a duplicate changes nothing. |
5 |
3 |
Packet 4 is still missing. |
4 |
5 |
The gap before packet 5 has closed. |
Implement int[] Solve(int[] packets).
0 <= packets.Length <= 300_000.- Each packet number is between
1and2_147_483_647. Numbers need not fit inside an array indexed by the number of arrivals. - Packet numbers may repeat. The stream may end with gaps still open.
- An empty input returns an empty array. Do not change
packets.
The hidden tests include long streams that advance after every arrival. Checking the entire delivered prefix again each time takes too long. Aim for expected O(n) total time and O(n) space, where n is the number of arrivals.
Starter code
using System;
public class Solution
{
public int[] Solve(int[] packets)
{
throw new NotImplementedException();
}
}How it is graded
Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.
What it practices
- Hash maps and sets
- Trade memory for constant-time lookups, membership tests and frequency counts.
Related katas
- Contains Duplicate Easy Free Decide whether an array contains any repeated value.
- Count Distinct Letters Easy Free How many different letters appear? A 26-slot array already knows.
- Count Pairs With Difference K Easy Free Count the pairs of indices whose values differ by exactly k.
- Isomorphic Strings Easy Free Can one string be turned into the other by a consistent character substitution?