Two Sigma software engineer interviews cover algorithms, data structures, system design, and coding problems drawn from real interview rounds.
n. Your goal is to reduce it to zero using the fewest operations possible. In a single operation, you may add or...Input: Integer(s)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...
Question You are given an undirected tree with n nodes labeled from 0 to n - 1. The tree is described by two integer arrays treeFrom and...
Question You are given a water drainage network shaped as a rooted tree with n nodes labeled from 0 to n - 1. Water flows from each node...
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)KeyValueStore that allows for storing, retrieving, and deleting key-value pairs. The operations should have O(1) time complexity. The class should also provide a method to check if a key exists in the store.def set_key(key: str, value: Any) -> None: # Adds or updates a key-value pairdef get_value(key: str) -> Optional[Any]: # Returns the value associated with the key, or None if it doesn't existdef delete_key(key: str) -> None: # Removes the key from the storedef key_exists(key: str) -> bool: # Returns True if the key exists, else Falseset_key('alpha', 100), get_value('alpha') → Output: 100. Explanation: 'alpha' is set to 100, therefore retrieving it returns 100.set_key('beta', 200), delete_key('beta'), get_value('beta') → Output: None. Explanation: 'beta' is deleted, so retrieving it returns None.LRUCache class that supports the following operations: get(key) and put(key, value). The get method should return the value of the key if it exists in the cache, otherwise return -1. The put method should insert or update the value of the key. If the number of keys exceeds the capacity, the least recently used key should be removed.class LRUCache:def __init__(self, capacity: int): # initializes the LRU cache with a positive capacity.def get(self, key: int) -> int: # returns the value of the key if it exists.def put(self, key: int, value: int) -> None: # updates or adds the key-value pair.put(1, 1); put(2, 2); get(1) → Output: 1 Explanation: Key 1 is found, returning 1.put(3, 3); get(2) → Output: -1 Explanation: Key 2 was evicted when putting key 3 since the capacity is 2.0 represents an open cell and 1 represents an obstacle, write a function that returns the length of the shortest path from the top-left corner (0,0) to the bottom-right corner (n-1,m-1). You can only move right, left, up, or down. If there is no such path, return -1.def shortest_path(grid: List[List[int]]) -> int:[[0,0,0],[0,1,0],[0,0,0]] 4 down -> down -> right -> right.[[0,1],[0,0]] 3 down -> right -> right.1 <= n, m <= 100 0s and 1s.0.m x n grid represented by a 2D array, where each cell is either 0 (open space) or # (obstacle), determine the shortest path from the starting point (0, 0) to a destination point (x, y). You may move up, down, left, or right but may not traverse the cells containing obstacles (#). Return the length of the shortest path if it exists, otherwise return -1.def shortest_path(grid: List[List[str]], destination: Tuple[int, int]) -> int:grid = [['0', '0', '#'], ['0', '0', '0'], ['#', '0', '0']], destination = (2, 2) 4 [(0,0), (0,1), (1,1), (2,1), (2,2)], which has 4 steps.grid = [['0', '#', '0'], ['0', '0', '0'], ['#', '#', '0']], destination = (2, 2) 5 [(0,0), (1,0), (1,1), (1,2), (2,2)], which has 5 steps.LRUCache class that supports the following operations: get and put. The get(key) method retrieves the value if the key exists, otherwise returns -1. The put(key, value) method updates the value if the key is present, or inserts a new key-value pair. If the cache reaches its limit, it should remove the least recently used item before inserting a new item.Function/class signature: def __init__(self, capacity: int): def get(self, key: int) -> int: def put(self, key: int, value: int) -> None: cache = LRUCache(2); cache.put(1, 1); cache.put(2, 2); cache.get(1) 1 cache.put(3, 3); cache.get(2) -1 1 <= capacity <= 3000 0 <= key, value <= 100000 get and put operations are called at most 10^4 times.Sign up for free to access walkthroughs, AI-generated questions, and more.
Get Started Free