Two Sigma software engineer interviews cover algorithms, data structures, system design, and coding problems drawn from real interview rounds.
Question A venue is holding an auction to allocate a limited number of concert tickets to fans. Before the sale closes, fans can submit bids. Each...
Input: ListQuestion A message-processing pipeline consists of n services that must all be traversed in sequence. The pipeline's effective throughput is...
Question You are given n people labeled from 0 to n - 1. Some pairs of people know each other directly. These relationships are given as a...
UPSERT records contain op, id, symbol, desk, time, and amount; DELETE records contain only op and id.amount is a positive USD notional with exactly two decimal places. Use exact integer cents internally. time is a nonnegative integer event timestamp in seconds, represented as a string.UPSERT inserts a new ID or replaces every field of an existing ID. Evaluate rules against the tentative state after removing the old version and adding the new version. If any rule fails, reject the entire update and preserve the previous state.TRADE_CAP: the proposed trade's amount must be at most 100.00.SYMBOL_CAP: the total amount of all active trades with the proposed trade's symbol, across all desks and timestamps, must be at most 250.00.TRADE_CAP, then SYMBOL_CAP. Equality with a cap is allowed.DELETE removes an active ID and returns ACCEPTED; deleting an absent ID returns NOOP. Neither case has violations.process_trades(records: list[dict[str, str]], enable_desk_windows: bool = False) — return type chosen by the candidate.Example 1:{
"enable_desk_windows": false,
"records": [
{"op":"UPSERT","id":"a","symbol":"X","desk":"alpha","time":"0","amount":"80.00"},
{"op":"UPSERT","id":"b","symbol":"X","desk":"alpha","time":"10","amount":"90.00"},
{"op":"UPSERT","id":"c","symbol":"Y","desk":"beta","time":"20","amount":"120.00"},
{"op":"UPSERT","id":"d","symbol":"X","desk":"alpha","time":"30","amount":"90.00"},
{"op":"DELETE","id":"a"}
]
}[
{"id":"a","status":"ACCEPTED","violations":[]},
{"id":"b","status":"ACCEPTED","violations":[]},
{"id":"c","status":"REJECTED","violations":["TRADE_CAP"]},
{"id":"d","status":"REJECTED","violations":["SYMBOL_CAP"]},
{"id":"a","status":"ACCEPTED","violations":[]}
]80.00 + 90.00 = 170.00. Trade c exceeds the individual cap. Trade d would create 260.00 of symbol-X exposure and is rejected. Deleting a leaves only b active.Part 2 — Out-of-order event-time exposure rulesenable_desk_windows is true, without replacing Part 1:DESK_WINDOW_CAP: for each desk and every integer endpoint r, the total amount of active trades whose timestamps satisfy r - 59 <= time <= r must be at most 180.00. Thus timestamps 0 and 59 can share a window, but timestamps 0 and 60 cannot.TRADE_CAP, SYMBOL_CAP, DESK_WINDOW_CAP. Each failure now includes rule, scope, observed, and limit. Scope is the proposed trade ID, symbol, or desk, respectively. For the desk rule, observed is that desk's maximum window total in the tentative state. Format monetary diagnostics with exactly two decimal places.op, sorted lexicographically by ID. The canonical representation is an object containing results and active_records.{
"enable_desk_windows": true,
"records": [
{"op":"UPSERT","id":"a","symbol":"X","desk":"alpha","time":"0","amount":"90.00"},
{"op":"UPSERT","id":"b","symbol":"Y","desk":"alpha","time":"30","amount":"80.00"},
{"op":"UPSERT","id":"c","symbol":"Z","desk":"alpha","time":"59","amount":"20.00"},
{"op":"UPSERT","id":"d","symbol":"Z","desk":"alpha","time":"60","amount":"20.00"},
{"op":"UPSERT","id":"b","symbol":"Y","desk":"alpha","time":"30","amount":"60.00"}
]
}{
"results": [
{"id":"a","status":"ACCEPTED","violations":[]},
{"id":"b","status":"ACCEPTED","violations":[]},
{"id":"c","status":"REJECTED","violations":[{"rule":"DESK_WINDOW_CAP","scope":"alpha","observed":"190.00","limit":"180.00"}]},
{"id":"d","status":"ACCEPTED","violations":[]},
{"id":"b","status":"ACCEPTED","violations":[]}
],
"active_records": [
{"id":"a","symbol":"X","desk":"alpha","time":"0","amount":"90.00"},
{"id":"b","symbol":"Y","desk":"alpha","time":"30","amount":"60.00"},
{"id":"d","symbol":"Z","desk":"alpha","time":"60","amount":"20.00"}
]
}90.00 + 80.00 = 170.00. At endpoint 59, c would raise it to 190.00, so c is rejected. Trade d is accepted: at endpoint 60, the window excludes a and contains 80.00 + 20.00 = 100.00; the earlier peak remains 170.00. Replacing b with 60.00 reduces the peak to 90.00 + 60.00 = 150.00. No individual or symbol cap fails.Example 3:{
"enable_desk_windows": true,
"records": [
{"op":"UPSERT","id":"a","symbol":"X","desk":"alpha","time":"0","amount":"100.00"},
{"op":"UPSERT","id":"b","symbol":"X","desk":"beta","time":"0","amount":"100.00"},
{"op":"UPSERT","id":"c","symbol":"Y","desk":"alpha","time":"10","amount":"80.00"},
{"op":"UPSERT","id":"b","symbol":"X","desk":"alpha","time":"20","amount":"160.00"},
{"op":"DELETE","id":"c"}
]
}{
"results": [
{"id":"a","status":"ACCEPTED","violations":[]},
{"id":"b","status":"ACCEPTED","violations":[]},
{"id":"c","status":"ACCEPTED","violations":[]},
{"id":"b","status":"REJECTED","violations":[
{"rule":"TRADE_CAP","scope":"b","observed":"160.00","limit":"100.00"},
{"rule":"SYMBOL_CAP","scope":"X","observed":"260.00","limit":"250.00"},
{"rule":"DESK_WINDOW_CAP","scope":"alpha","observed":"340.00","limit":"180.00"}
]},
{"id":"c","status":"ACCEPTED","violations":[]}
],
"active_records": [
{"id":"a","symbol":"X","desk":"alpha","time":"0","amount":"100.00"},
{"id":"b","symbol":"X","desk":"beta","time":"0","amount":"100.00"}
]
}200.00, and alpha reaches exactly 100.00 + 80.00 = 180.00, which is allowed. The proposed replacement of b has amount 160.00, makes X total 100.00 + 160.00 = 260.00, and makes alpha's window total 100.00 + 80.00 + 160.00 = 340.00. All three rules fail. The old b remains on beta with amount 100.00; deleting c then leaves two unchanged trades.Notes:[0, 10^9], and amounts are between 0.01 and 1000000.00. IDs, symbols, and desks are nonempty, case-sensitive strings of at most 40 characters.shortest_path that finds the shortest path from a starting node to a destination node using Dijkstra's algorithm. You should return the path as a list of node identifiers and the total weight of that path.Function/class signature: def shortest_path(graph: Dict[int, List[Tuple[int, int]]], start: int, end: int) -> Tuple[List[int], int]:graph = {0: [(1, 4), (2, 1)], 1: [(3, 1)], 2: [(1, 2), (3, 5)], 3: []}, start = 0, end = 3([0, 2, 1, 3], 5) graph = {0: [(1, 10), (2, 5)], 1: [(3, 2)], 2: [(1, 3), (3, 1)], 3: []}, start = 0, end = 3([0, 2, 3], 6)Sign up for free to access walkthroughs, AI-generated questions, and more.
Get Started Free