Network Packet Stream Reassembly

What's being tested

This concept tests whether you can design a reliable stream reassembler from unordered, duplicated, delayed, overlapping, and fragmented packets. The interviewer is probing data-structure choice, sequence-number arithmetic, gap detection, memory bounds, and clear handling of malformed or adversarial input. At OpenAI, this matters because production services depend on robust protocol implementations, bounded resource usage, and debugging discipline under partial failure—not merely the happy path of receiving packets in order.

Core knowledge

A packet reassembler converts records (stream_id, sequence_number, payload, flags) into an ordered byte stream. Clarify whether sequence numbers identify bytes or fragments, whether packets may be duplicated, and whether multiple streams must be isolated.
The standard design keeps a contiguous frontier next_expected, plus a sorted interval map of buffered out-of-order data. When a packet begins at next_expected, emit it and repeatedly consume adjacent buffered intervals.
For arbitrary sequence numbers, use an ordered map such as std::map, a balanced tree, or a heap plus hash index. Insertion and merging cost O(log k) for k buffered intervals; emitting a run costs O(number of merged intervals + bytes emitted).
A hash map keyed by exact sequence number is simpler but performs poorly when packets overlap or start at different offsets. An interval tree or ordered disjoint interval map is preferable when fragmentation and overlap are common.
Normalize every packet into an interval [start, end) with payload length end - start. Half-open intervals make adjacency precise: [0, 100) and [100, 150) can merge without ambiguity, while [0, 100) and [101, 150) contain a one-byte gap.
Handle overlap using an explicit policy. For trusted transport, “first byte received wins” or “latest byte wins” may be acceptable; for security-sensitive reassembly, inconsistent overlapping payloads should be rejected or surfaced because different endpoints may interpret them differently.
Bound memory with a receive window, maximum buffered bytes, maximum interval count, and packet-size limits. Without these controls, an attacker can send far-future sequence numbers and force unbounded storage; reject or evict data outside the configured window.
Sequence-number wraparound requires modular comparison rather than ordinary integer comparison. For a sequence space of size $2^n$ , compare differences only when the valid receive window is less than $2^{n-1}$ ; otherwise “before” and “after” become ambiguous.
Duplicate suppression should occur after clipping against already delivered and buffered ranges. A packet fully below next_expected contributes nothing; a partially overlapping packet should retain only its unseen suffix or disjoint portions.
Packet arrival does not imply stream progress. A reassembler should distinguish received bytes, delivered bytes, highest observed sequence, and end-of-stream; a FIN/end marker may arrive before the final missing bytes.
Correctness invariants are more valuable than ad hoc tests: emitted bytes are strictly ordered, each byte is emitted at most once, next_expected advances only through contiguous data, and buffered intervals never overlap after normalization.
Concurrency requires a clear ownership model. A per-stream mutex is straightforward; sharding streams across workers improves throughput. Never let callbacks execute while holding the reassembly lock, or a slow consumer can block packet ingestion and create avoidable deadlocks.
Recovery policy depends on protocol semantics. For a reliable transport, retain gaps and wait for retransmission; for a bounded-latency telemetry stream, expose a timeout or gap marker. The choice is a correctness-versus-latency tradeoff, not an implementation detail.

Worked example: Network Packet Stream Reassembly

For “Network Packet Stream Reassembly,” a strong candidate first clarifies whether packets can arrive out of order, whether sequence numbers wrap, whether overlapping payloads are legal, and whether the API must block, timeout, or report gaps. They would declare a byte-oriented model, half-open intervals, one logical stream per reassembler, and a finite receive window. The answer can be organized around four pillars: normalize and validate packets, merge them into an ordered interval structure, advance the contiguous frontier, and enforce resource and concurrency limits. The key state is next_expected, an ordered set of non-overlapping buffered intervals, buffered-byte count, and optional end-of-stream metadata. A concrete decision to flag is “first-wins versus latest-wins” overlap handling, since inconsistent policies can create endpoint desynchronization and security bugs. They should explain that a duplicate packet is harmless after clipping, while a packet containing a gap is buffered rather than emitted. They would close by saying that, with more time, they would add property-based tests, wraparound tests, fuzzing for malformed intervals, and metrics for gap age, buffer pressure, and rejected bytes.

A second angle

A different framing is a live log or media stream where waiting forever for a missing packet is unacceptable. The same interval machinery applies, but the API now needs gap timers, maximum reassembly latency, and an explicit policy such as skip, zero-fill, or terminate the stream. The candidate should separate transport correctness from application policy: the core can report “bytes available through offset X, gap begins at X,” while the caller decides whether latency or completeness matters more. This version also makes backpressure and cancellation central, because a slow consumer must not allow buffered data to grow without bound.

Common pitfalls

Pitfall: Treating packets as indivisible chunks and appending them whenever they arrive fails on out-of-order delivery and overlapping ranges. Store byte intervals and advance output only from the contiguous frontier.

Pitfall: Saying “use a hash map” without discussing overlap, ordering, or complexity sounds incomplete. Name the invariant, explain how intervals merge, and state why an ordered structure is appropriate.

Pitfall: Ignoring sequence wraparound, malicious far-future packets, or memory limits is a depth mistake. A production answer should specify modular comparison, receive-window validation, and measurable resource caps.

Connections

The interviewer may pivot to TCP receive windows, sliding-window protocols, backpressure, and flow control. Other natural extensions include checksum validation, retransmission timers, event-loop concurrency, and property-based testing of stream invariants.

Visa Tools

Visa Sponsors

H-1B Odds Calculator

Visa Bulletin