How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Jane Street.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Jane Street during technical interviews.

Optimize trade PnL table updates | Jane Street Coding Question

Optimize trade PnL table updates

Company: Jane Street

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Onsite

You are asked to modify an existing class **without changing its public API**: ```python class Table: def __init__(self, filters, times): pass def add_trade(self, trade): pass def view_result(self) -> list[list[int]]: pass def set_global_filter(self, global_filter): pass ``` Assume the following: - `filters` is a list of predicates, where each predicate takes a `trade` and returns `True` or `False`. - A trade may match multiple filters; the filters are **not** mutually exclusive. - `times` is an ordered list of time points such as `t0, t1, t2, ...`. - `get_pnl(trade, time)` returns the PnL of a trade at a given time. - `global_filter` is an extra predicate applied in addition to the row filter. It is initially `None`. `view_result()` should return a 2D list where: - row `i` corresponds to `filters[i]` - column `j` corresponds to `times[j]` - `result[i][j]` is the sum of `get_pnl(trade, times[j])` over all trades that satisfy `filters[i]` and also satisfy `global_filter` if it is set The starter implementation makes `add_trade()` simple and computes `view_result()` using nested loops over all trades, filters, and times. Redesign the internals so that: 1. `view_result()` runs in **O(1)** time. 2. `add_trade(trade)` incrementally updates any internal state needed for fast queries. 3. `set_global_filter(global_filter)` correctly changes the active filter and keeps subsequent results accurate. 4. In a follow-up, `get_pnl(trade, time)` becomes **asynchronous / callback-based** and expensive, so repeated calls should be avoided by caching results inside the class. Describe or implement a clean state management strategy, including how to handle overlapping filters and changes to the global filter without returning stale results.

Quick Answer: This question evaluates understanding of incremental aggregation and state management, including handling overlapping predicates, caching expensive or asynchronous computations, and algorithmic complexity considerations in time-series PnL updates.

Part 1: Maintain a Filtered PnL Table Under Trade Updates

You are given a fixed list of row filters and a stream of operations on trades. To make the problem concrete, each row filter is a tag value. A trade matches row i if row_filters[i] appears in that trade's tag list. Trades may contain multiple tags, so one trade can contribute to multiple rows. Process these operations: - ("ADD", tags, pnl): add one trade. tags is a list of distinct integers. pnl is a list of length times_count, where pnl[j] is this trade's PnL at time j. - ("SET_GLOBAL", g): activate an extra global tag filter g, or None to clear it. - ("VIEW",): snapshot the current result matrix. For every VIEW, return an F x T matrix where F = len(row_filters) and T = times_count. Cell [i][j] must equal the sum of pnl[j] over all previously added trades that: 1. contain row_filters[i], and 2. also contain the current global tag if it is not None. Your implementation should incrementally maintain internal state so that changing the global filter does not require rescanning all past trades.

Constraints

0 <= len(row_filters) <= 50
1 <= times_count <= 30
0 <= len(operations) <= 20000
row_filters contains distinct integers
For every ADD, tags contains distinct integers
For every ADD, len(pnl) == times_count
PnL values may be negative

Examples

Input: ([1, 2, 3], 2, [('ADD', [1, 2], [10, 20]), ('ADD', [3], [5, 7]), ('VIEW',), ('SET_GLOBAL', 2), ('VIEW',), ('ADD', [1, 2, 3], [1, 1]), ('VIEW',), ('SET_GLOBAL', None), ('VIEW',)])

Expected Output: [[[10, 20], [10, 20], [5, 7]], [[10, 20], [10, 20], [0, 0]], [[11, 21], [11, 21], [1, 1]], [[11, 21], [11, 21], [6, 8]]]

Explanation: The third trade overlaps all three rows. When the global filter is 2, only trades containing tag 2 contribute.

Input: ([1, 2], 3, [('VIEW',), ('SET_GLOBAL', 9), ('VIEW',), ('ADD', [9], [4, 4, 4]), ('VIEW',)])

Expected Output: [[[0, 0, 0], [0, 0, 0]], [[0, 0, 0], [0, 0, 0]], [[0, 0, 0], [0, 0, 0]]]

Explanation: Edge case: no trade ever matches row filter 1 or 2, so every view is all zeros.

Input: ([1, 2], 1, [('ADD', [1, 2], [5]), ('ADD', [2], [-3]), ('SET_GLOBAL', 1), ('VIEW',), ('SET_GLOBAL', None), ('VIEW',)])

Expected Output: [[[5], [5]], [[5], [2]]]

Explanation: With global filter 1, the second trade is excluded because it lacks tag 1.

Input: ([], 2, [('VIEW',), ('ADD', [1], [3, 4]), ('VIEW',)])

Expected Output: [[], []]

Explanation: Edge case: there are no row filters, so each snapshot is an empty matrix.

Hints

A trade with tags S contributes to every row whose tag is in S, not just one row.
Maintain one aggregate matrix for no global filter and additional aggregate matrices keyed by global tag. Then SET_GLOBAL only needs to switch which matrix is active.

Part 2: Process Asynchronous PnL Callbacks with Caching

This version models expensive asynchronous get_pnl(trade, time) calls. Trades are added before their PnL values are known. Later, callback results arrive one time point at a time. Each row filter is still a tag value. A trade matches row i if row_filters[i] is in that trade's tag list. Process these operations: - ("ADD", trade_id, tags): register a trade with a unique ID and a list of distinct tags. - ("RESOLVE", trade_id, time_idx, value): an asynchronous callback delivers the PnL value for that trade at one time index. - ("SET_GLOBAL", g): activate an extra global tag filter g, or None to clear it. - ("VIEW",): snapshot the current table. Only resolved values count. If a trade's PnL for a time index has not been resolved yet, it contributes 0 to that column. If the same (trade_id, time_idx) is resolved more than once, only the first value should be used; later duplicates must be ignored because the result is already cached. For every VIEW, return an F x T matrix where cell [i][j] is the sum of all resolved PnL values for time j from trades that match row_filters[i] and also match the active global filter if it is not None. A strong solution updates all affected aggregates as soon as a callback arrives, so later VIEW operations do not need to rescan trades or reprocess old callbacks.

Constraints

0 <= len(row_filters) <= 50
1 <= times_count <= 30
0 <= len(operations) <= 30000
row_filters contains distinct integers
Each ADD uses a unique trade_id; if duplicates appear, only the first ADD matters
For every ADD, tags contains distinct integers
For every RESOLVE, 0 <= time_idx < times_count
If the same (trade_id, time_idx) appears multiple times in RESOLVE operations, only the first one should affect the answer

Examples

Input: ([1, 2], 3, [('ADD', 'A', [1, 2]), ('VIEW',), ('RESOLVE', 'A', 0, 5), ('RESOLVE', 'A', 2, 9), ('VIEW',), ('SET_GLOBAL', 2), ('VIEW',), ('ADD', 'B', [2]), ('RESOLVE', 'B', 1, 4), ('VIEW',)])

Expected Output: [[[0, 0, 0], [0, 0, 0]], [[5, 0, 9], [5, 0, 9]], [[5, 0, 9], [5, 0, 9]], [[5, 0, 9], [5, 4, 9]]]

Explanation: Before any RESOLVE calls, the table is all zeros. Later callbacks update the exact cells they affect.

Input: ([1], 2, [('ADD', 'X', [9]), ('RESOLVE', 'X', 0, 7), ('VIEW',), ('SET_GLOBAL', 9), ('VIEW',)])

Expected Output: [[[0, 0]], [[0, 0]]]

Explanation: Edge case: the trade never matches row filter 1, so even resolved values do not appear in the table.

Input: ([1, 2, 3], 2, [('ADD', 'A', [1, 3]), ('ADD', 'B', [2]), ('RESOLVE', 'A', 1, 4), ('SET_GLOBAL', 3), ('VIEW',), ('RESOLVE', 'B', 0, 5), ('VIEW',), ('SET_GLOBAL', None), ('VIEW',)])

Expected Output: [[[0, 4], [0, 0], [0, 4]], [[0, 4], [0, 0], [0, 4]], [[0, 4], [5, 0], [0, 4]]]

Explanation: Trade B does not have tag 3, so its resolved value is invisible while the global filter is 3.

Input: ([1, 2], 1, [('ADD', 'A', [1, 2]), ('RESOLVE', 'A', 0, 3), ('RESOLVE', 'A', 0, 99), ('VIEW',), ('SET_GLOBAL', 2), ('VIEW',)])

Expected Output: [[[3], [3]], [[3], [3]]]

Explanation: Edge case: the second RESOLVE for the same (trade_id, time_idx) is ignored because the value is already cached.

Hints

Store each trade's tag set when the trade is added. Then when one callback arrives, you can immediately update every row/global aggregate that this single value affects.
Use a seen set for (trade_id, time_idx) so duplicate callbacks do not corrupt the totals.

Quick Overview

This question evaluates understanding of incremental aggregation and state management, including handling overlapping predicates, caching expensive or asynchronous computations, and algorithmic complexity considerations in time-series PnL updates.