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]].
leftandrightare lists of rows(time, key, value). Each list is sorted bytimein non-decreasing order, so several rows may share a time.- For every left row
(t, key, value), in the order ofleft, output one row(t, key, value, match). matchis thevalueof the latest right row with the samekeyand a time<= t. Latest means the largest time. If several right rows with that key share that time, take the one that comes last inright.- If no right row qualifies,
matchisNone. tolerance, when it is set, is an integer>= 0that limits how stale a match may be. The latest right row (as above) only counts ift - its time <= tolerance. If it is older than that,matchisNone. 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.