Streaming Equivalence of Two Trade Feeds with Per-Company Ordering
Company: Jane Street
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
A market-data system receives trade events from two independent feeds. Each event is a pair `(company, trade_id)` identifying one trade for one company.
Two feeds are **equivalent** when, for every company, the ordered sequence of that company's trade ids is identical in both feeds. The relative interleaving of *different* companies is allowed to differ.
For example, these two feeds are equivalent:
```
Feed 1: ("A",1) ("A",2) ("B",1) ("B",2)
Feed 2: ("A",1) ("B",1) ("A",2) ("B",2)
```
Company `A`'s trade ids appear in the order `[1, 2]` in both feeds, and company `B`'s in the order `[1, 2]` in both — only the interleaving differs. In contrast, `("A",1) ("A",2)` and `("A",2) ("A",1)` are **not** equivalent, because company `A`'s order differs.
Write a function
```
are_equivalent(feed1, feed2) -> bool
```
where `feed1` and `feed2` are lists of `[company, trade_id]` pairs in arrival order. Return `true` if the two feeds are equivalent and `false` otherwise.
Your solution must treat the inputs as **streams** and satisfy both of the following:
1. **Single pass with early termination.** Consume events from the two feeds incrementally (for example, alternating one event from each feed per step, then draining whichever feed is longer). The moment the events seen so far *prove* the feeds cannot be equivalent — e.g., a company's next trade id in one feed contradicts the pending, unmatched trade ids already seen for that company in the other feed — return `false` immediately without reading any further events. You may not pre-scan, sort, or fully materialize per-company sequences up front.
2. **Space proportional to the lag, not the feed.** Auxiliary memory must be bounded by the number of events read from one feed whose matching event has not yet arrived in the other feed (plus per-company bookkeeping), not by the total feed length. Storing complete copies of both feeds and comparing at the end is not acceptable.
If both feeds are exhausted and every event has been matched, return `true`. If one feed ends while the other still has unmatched events — or the feeds have different lengths — they are not equivalent.
### Examples
| feed1 | feed2 | result |
|-------|-------|--------|
| `[["A",1],["A",2],["B",1],["B",2]]` | `[["A",1],["B",1],["A",2],["B",2]]` | `true` |
| `[["A",1],["A",2]]` | `[["A",2],["A",1]]` | `false` |
| `[["A",1],["B",7]]` | `[["B",7],["A",1]]` | `true` |
| `[["A",1]]` | `[["A",1],["A",2]]` | `false` |
| `[["A",1],["B",2]]` | `[["A",1],["C",2]]` | `false` |
| `[]` | `[]` | `true` |
### Constraints
- `0 <= len(feed1), len(feed2) <= 2 * 10^5`
- `company` is a non-empty string of at most 10 uppercase letters
- `trade_id` is an integer in `[1, 10^9]`
- Trade ids are **not** guaranteed to be unique, even within a single company — the per-company sequences must match exactly as ordered lists, duplicates included
- Target complexity: `O(n)` time overall and `O(d)` auxiliary space, where `d` is the maximum number of in-flight (not-yet-matched) events at any point during processing
Quick Answer: This question evaluates understanding of streaming algorithms, per-key sequence matching, and bounded-memory online processing within the Coding & Algorithms domain, focusing on maintaining per-entity ordering, matching sequences with possible duplicates, and handling asynchronous interleaving.
A market-data system receives trade events from two independent feeds. Each event is a pair `[company, trade_id]` identifying one trade for one company.
Two feeds are **equivalent** when, for every company, the ordered sequence of that company's trade ids is identical in both feeds. The relative interleaving of *different* companies is allowed to differ. For example, `[["A",1],["A",2],["B",1],["B",2]]` and `[["A",1],["B",1],["A",2],["B",2]]` are equivalent (A's ids are `[1,2]` and B's are `[1,2]` in both), but `[["A",1],["A",2]]` and `[["A",2],["A",1]]` are not (A's order differs).
Implement `solution(feed1, feed2)` returning `True` if the two feeds are equivalent and `False` otherwise, where `feed1` and `feed2` are lists of `[company, trade_id]` pairs in arrival order.
Treat the inputs as **streams**: make a single pass, consuming events incrementally (e.g. one from each feed per step, then draining the longer feed), and return `False` the moment the events seen so far prove the feeds cannot be equivalent — do not pre-scan, sort, or fully materialize per-company sequences up front. Auxiliary memory must be bounded by the number of read-but-not-yet-matched events (the lag), not by total feed length.
If both feeds are exhausted with every event matched, return `True`. If one feed ends while the other still has unmatched events — or the feeds have different lengths — they are not equivalent. Trade ids are **not** guaranteed unique even within a company, so the per-company sequences must match exactly as ordered lists, duplicates included.
**Approach.** Keep a per-company FIFO queue of pending (unmatched) trade ids that all belong to whichever feed is currently ahead for that company. For each incoming `[company, trade_id]`: if that company has no pending events, enqueue the id and record the owning feed; if the event comes from the same feed that is already ahead, just enqueue it; otherwise (it comes from the trailing feed catching up) it must equal the oldest pending id — pop and compare, returning `False` on mismatch. After both feeds are drained, the feeds are equivalent iff no company has any pending id left. This runs in O(n) time and O(d) auxiliary space, where d is the peak number of in-flight unmatched events.
Constraints
- 0 <= len(feed1), len(feed2) <= 2 * 10^5
- company is a non-empty string of at most 10 uppercase letters
- trade_id is an integer in [1, 10^9]
- Trade ids are not guaranteed unique, even within a single company; per-company sequences must match exactly as ordered lists, duplicates included
- Target: O(n) time overall and O(d) auxiliary space, where d is the max in-flight unmatched events at any point
Examples
Input: ([['A',1],['A',2],['B',1],['B',2]], [['A',1],['B',1],['A',2],['B',2]])
Expected Output: True
Explanation: A's ids are [1,2] in both feeds and B's are [1,2] in both; only the cross-company interleaving differs, so the feeds are equivalent.
Input: ([['A',1],['A',2]], [['A',2],['A',1]])
Expected Output: False
Explanation: Company A appears as [1,2] in feed1 but [2,1] in feed2 — its per-company order differs, so not equivalent.
Hints
- Interleaving of different companies doesn't matter — only each company's own trade-id order does. So the problem reduces to: for every company, does feed1 emit the same ordered id sequence as feed2?
- Compare each company's two sequences with a single FIFO queue instead of storing both fully: whichever feed is ahead buffers its ids; when the trailing feed emits an id for that company it must equal the oldest buffered one, or the feeds differ.
- Track which feed currently owns the pending queue for each company. Same-feed events just extend the buffer; an event from the other feed consumes the front. This bounds memory by the lag, not the feed length.
- After draining both feeds, the answer is True only if no company has any leftover pending ids — that also correctly rejects unequal-length feeds and one-feed-ends-early cases.