progress

~/problems / Two pointers

As-of join of two time series

On a phone? Coding is easier on a laptop: email this problem to yourself . Meanwhile: quiz this topic or fight a boss.

medium ~25 min Headlands

A trading desk keeps two tables that tick at different moments: trades on the left and quotes on the right. To see what the market looked like when each trade happened, you attach to every trade the most recent quote for the same symbol. This is called an as-of join: each left row is joined with the right row that was current as of its time.

Write asof_join(left, right, tolerance=None) -> list[tuple[int, str, int, int | None]].

  • left and right are lists of rows (time, key, value). Each list is sorted by time in non-decreasing order, so several rows may share a time.
  • For every left row (t, key, value), in the order of left, output one row (t, key, value, match).
  • match is the value of the latest right row with the same key and a time <= t. Latest means the largest time. If several right rows with that key share that time, take the one that comes last in right.
  • If no right row qualifies, match is None.
  • tolerance, when it is set, is an integer >= 0 that limits how stale a match may be. The latest right row (as above) only counts if t - its time <= tolerance. If it is older than that, match is None. An older row never replaces it, because it would be even staler.

Don't change left or right.

left = [(1, "AAPL", 100), (3, "MSFT", 50), (5, "AAPL", 101), (9, "AAPL", 102), (9, "TSLA", 7)]
right = [(0, "AAPL", 10), (2, "MSFT", 20), (4, "AAPL", 11), (5, "AAPL", 12), (6, "MSFT", 21)]

asof_join(left, right)
# [(1, "AAPL", 100, 10), (3, "MSFT", 50, 20), (5, "AAPL", 101, 12), (9, "AAPL", 102, 12), (9, "TSLA", 7, None)]

asof_join(left, right, tolerance=2)
# [(1, "AAPL", 100, 10), (3, "MSFT", 50, 20), (5, "AAPL", 101, 12), (9, "AAPL", 102, None), (9, "TSLA", 7, None)]

In the first call, the trade at time 5 sees the quote at time 5 (a quote at the same moment counts). The trade at time 9 still sees it, because nothing newer for AAPL arrived. With tolerance=2, that quote is 4 ticks old at time 9, so it is too stale.

Constraints: each table has at most 2 * 10^5 rows. Times are integers in 0..10^15, values are integers in -10^9..10^9, and keys are non-empty strings of at most 8 characters. In C++ and Java, times, values and tolerance are 64-bit integers.

⭐ Bonus: searching right again for every left row passes the correctness tests. A speed test with 2 * 10^5 rows on each side earns a star in O(len(left) + len(right)) time.

Show hint

both tables are sorted by time. Walk through them together, and remember what you have already seen of right.

Topic: Two pointers. Sorted input + moving ends inward; skip duplicates; pairs and triples.

Read the visual guide
0:00
Ctrl ' run · Ctrl ↵ submit
esc