Detect Recent Duplicate Records with Bounded Memory
Company: Bloomberg
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
# Detect Recent Duplicate Records with Bounded Memory
A time-ordered stream contains records [id, text, title, timestamp]. Detect records whose exact (text, title) pair appeared recently while discarding state that can no longer affect future answers.
~~~python
def recent_duplicate_pairs(
records: list[list[object]],
window_seconds: int = 60
) -> list[list[str]]:
...
~~~
For each record in input order, look at the most recent earlier record with the same text and title. If current_timestamp - earlier_timestamp is between 0 and window_seconds inclusive, append [earlier_id, current_id] to the output. Whether or not a pair is emitted, the current record becomes the most recent record for that content key.
This exact contract resolves ambiguity in the abbreviated source example and makes the output deterministic.
## Constraints and Boundary Rules
- 0 <= len(records) <= 300000
- Every record contains exactly [string_id, string_text, string_title, integer_timestamp].
- Timestamps are nonnegative and nondecreasing. Input order breaks ties.
- IDs are nonempty strings and are guaranteed unique by an upstream validator. Duplicate IDs are outside this function's input domain and are not included in tests, so the implementation does not need a global seen-ID set.
- window_seconds is a nonnegative integer.
- For window_seconds == 0, only equal-timestamp duplicates match.
- Malformed records, empty IDs, Boolean timestamps, or decreasing time must raise `ValueError`.
- Inputs and outputs are JSON-marshalable and outputs are compared exactly.
- Target `O(n)` expected time and memory proportional to distinct content keys whose latest record is still inside the active window, not all historical IDs or keys.
## Example
~~~text
Input:
records = [
["id1", "alpha", "title", 2],
["id2", "other", "title", 4],
["id3", "alpha", "title", 50],
["id4", "alpha", "title", 80]
]
window_seconds = 60
Output:
[["id1", "id3"], ["id3", "id4"]]
~~~
## Hints
- An insertion-ordered mapping can store only the latest record for each content key; move a key to the newest position whenever it appears.
- Because timestamps are nondecreasing, evicting expired keys from the oldest end keeps one live state record per active content key.
- Eviction must use the same inclusive boundary as matching.
Quick Answer: Detect repeated text-title pairs in a time-ordered record stream within an inclusive recent window. Emit pairs against the most recent matching record while evicting expired content keys so memory depends on active history rather than the full stream.
For each time-ordered record, emit a pair with the most recent equal text-and-title record inside an inclusive time window while evicting obsolete state.
Constraints
- Timestamps are nonnegative and nondecreasing
- IDs are unique nonempty strings
- Memory should track only content keys active in the window
Examples
Input: {'records': [], 'window_seconds': 60}
Expected Output: []
Explanation: An empty stream has no duplicates.
Input: {'records': [['id1', 'alpha', 'title', 2], ['id2', 'other', 'title', 4], ['id3', 'alpha', 'title', 50], ['id4', 'alpha', 'title', 80]], 'window_seconds': 60}
Expected Output: [['id1', 'id3'], ['id3', 'id4']]
Explanation: The prompt example pairs each record with the latest matching predecessor.
Hints
- Store only the latest record for each content key.
- Maintain keys in latest-timestamp order so the oldest expired state can be removed first.