Two Sigma Software Engineer Phone Screen Questions

## Problem Model code compilation dependencies, likely determining valid compilation order or detecting cyclic dependencies using topological sort. ## Likely LeetCode equivalent No direct unambiguous LC equivalent. ## Tags graph, topological_sort, recursion

## Problem Determine if a string of brackets is correctly matched and properly nested using a stack. ## Likely LeetCode equivalent LC 20 - Valid Parentheses (>80% confident) ## Tags stack, strings

## Problem Implement a data compression or run-length encoding scheme on strings or byte sequences. ## Likely LeetCode equivalent No single unambiguous LC equivalent. ## Tags strings, design, coding_other

## Problem Find the exchange rate between currency pairs using graph traversal, similar to evaluating chained division equations. ## Likely LeetCode equivalent LC 399 - Evaluate Division (>80% confident, same structure) ## Tags graph, bfs, hash_table

## Problem Given a social network represented as an adjacency list `{user_id: [friend_ids]}`, find the shortest chain of connections between two users `start` and `end`. Return the path as a list of user IDs, or an empty list if no path exists. ```python def friend_chain( network: dict, # {user_id: List[user_id]} start: str, end: str ) -> List[str]: ... ``` **Example:** ``` network = { "Alice": ["Bob", "Carol"], "Bob": ["Alice", "Dave"], "Carol": ["Alice", "Eve"], "Dave": ["Bob"], "Eve": ["Carol", "Frank"], "Frank": ["Eve"] } friend_chain(network, "Alice", "Frank") -> ["Alice", "Carol", "Eve", "Frank"] ``` ## Follow-ups 1. What is the time and space complexity of BFS on a graph with V users and E friendships? 2. How would you find the shortest path between all pairs of users efficiently? 3. If the graph has 500M users (like a real social network), how do you scale this? 4. How would you compute the "degrees of separation" distribution across the whole network?

## Problem Design a friends invitation and reward tracking system. When user A invites user B who signs up, A earns a reward. If B then invites C who signs up, A also earns an indirect reward (one level deep only). Implement: - `invite(inviter_id, invitee_email)` - record invitation. - `signup(email, user_id)` - register the user and trigger rewards. - `get_rewards(user_id) -> int` - total reward credits earned. - `get_invitees(user_id) -> List[str]` - list of successfully signed-up direct invitees. ```python class InvitationSystem: def invite(self, inviter_id: str, invitee_email: str): ... def signup(self, email: str, user_id: str): ... def get_rewards(self, user_id: str) -> int: ... def get_invitees(self, user_id: str) -> List[str]: ... ``` **Example:** ``` sys.invite("u1", "[email protected]") sys.signup("[email protected]", "u2") # u1 earns 10 credits (direct) sys.invite("u2", "[email protected]") sys.signup("[email protected]", "u3") # u2 earns 10, u1 earns 5 (indirect) sys.get_rewards("u1") -> 15 ``` ## Follow-ups 1. How do you prevent reward farming (user inviting themselves with fake emails)? 2. Extend the reward chain to arbitrary depth with diminishing returns. 3. How would you idempotently handle duplicate `signup` calls for the same email? 4. How do you generate an invitation leaderboard (top inviters) efficiently?

## Problem Group or aggregate financial transactions by some key (user, category, date), likely returning totals per group. ## Likely LeetCode equivalent No direct unambiguous LC equivalent. ## Tags hash_table, arrays, design

## Problem Design an in-memory key-value database supporting set, get, delete, and possibly transaction rollback operations. ## Likely LeetCode equivalent No direct unambiguous LC equivalent (common Two Sigma OA problem). ## Tags hash_table, design, stack

## Problem Implement a memory allocator (malloc/free) managing a fixed-size memory block with first-fit or best-fit allocation strategy. ## Likely LeetCode equivalent No direct LC equivalent. ## Tags design, coding_other, systems

## Problem Merge multiple sorted data streams into one sorted output, using a min-heap for efficient multi-way merge. ## Likely LeetCode equivalent LC 23 - Merge k Sorted Lists (>80% confident, same pattern) ## Tags heap, linked_list, sorting

## Problem Multiply two non-negative integers represented as strings without using built-in big integer libraries. ## Likely LeetCode equivalent LC 43 - Multiply Strings (>80% confident) ## Tags strings, math, simulation

## Problem You have an `n x n` chessboard with rooks placed at given positions. For each rook, find the nearest other rook by Manhattan distance. If multiple rooks are equidistant, return the one with the smallest row index, then smallest column index. ```python def nearest_rook( n: int, rooks: List[Tuple[int,int]] ) -> List[Tuple[int,int]]: # Returns list where result[i] = position of nearest rook to rooks[i] ... ``` **Example:** ``` n = 8 rooks = [(0,0), (0,3), (5,0)] nearest_rook(8, rooks) -> [(0,3), # nearest to (0,0) is (0,3), dist=3 (0,0), # nearest to (0,3) is (0,0), dist=3 (0,0)] # nearest to (5,0) is (0,0), dist=5 ``` ## Follow-ups 1. Your brute-force is O(k^2) for k rooks. How do you use a spatial index (k-d tree) to improve this? 2. How does the answer change if distance is Euclidean instead of Manhattan? 3. For a rook that can attack along rows and columns, find the nearest rook it can attack in one move. 4. If rooks are added and removed dynamically, what data structure supports O(log k) nearest-neighbor queries?

## Problem Implement a limit order book for a single trading pair. Support: - `place_order(order_id, side, price, quantity)` - add a limit order (`"buy"` or `"sell"`). - `cancel_order(order_id)` - remove the order. - `get_best_bid() -> float` - highest buy price with resting quantity. - `get_best_ask() -> float` - lowest sell price with resting quantity. - Automatically match orders when best bid >= best ask. ```python class OrderBook: def place_order(self, order_id: str, side: str, price: float, qty: int): ... def cancel_order(self, order_id: str): ... def get_best_bid(self) -> float: ... def get_best_ask(self) -> float: ... def get_trades(self) -> List[dict]: ... ``` **Example:** ``` ob = OrderBook() ob.place_order("o1", "buy", 100.0, 10) ob.place_order("o2", "sell", 99.0, 5) # crosses -> trade 5 @ 100.0 ob.get_best_bid() -> 100.0 # 5 remaining on o1 ob.get_trades() -> [{"buy": "o1", "sell": "o2", "price": 100.0, "qty": 5}] ``` ## Follow-ups 1. What data structures give O(log n) insert/delete and O(1) best-bid/ask lookup? 2. How do you handle price-time priority (FIFO within same price level)? 3. How would you extend to market orders and stop orders? 4. What guarantees do you need to make the matching engine thread-safe?

## Problem You know in advance the stock prices for the next `n` days. You may hold at most one share at a time. Each buy or sell incurs a fixed transaction cost `c`. Find the maximum profit. ```python def max_profit(prices: List[int], c: int) -> int: ... ``` **Example:** ``` Input: prices=[1, 3, 2, 8, 4, 9], c=2 Output: 8 # Buy at 1, sell at 8 -> profit 7 - cost 2*2 = 3 # Actually: Buy@1, sell@8 (profit 7, cost 4) -> net 3 # Or: Buy@1 sell@3 (-2 fees) profit 0, Buy@2 sell@9 -> profit 7-4=3 -> total 3 # Optimal: Buy@1, sell@8, buy@4, sell@9 -> (8-1-2) + (9-4-2) = 5+3 = 8 Output: 8 ``` ## Approach DP: `hold[i]` = max profit ending day `i` holding a share. `cash[i]` = max profit ending day `i` holding no share. - `hold[i] = max(hold[i-1], cash[i-1] - prices[i])` - `cash[i] = max(cash[i-1], hold[i-1] + prices[i] - c)` ## Follow-ups 1. How does removing the transaction cost change the solution? 2. Extend to allow holding at most `k` shares simultaneously. 3. Add a cooldown period: after selling you must wait 1 day before buying again. 4. How do you reconstruct the actual buy/sell days from the DP table?

## Problem Two players take turns on a 1D board. There is a pile of `n` stones. On each turn the current player removes 1, 2, or 3 stones. The player who takes the last stone wins. Given `n`, determine if the first player can guarantee a win with optimal play. ```python def can_first_player_win(n: int) -> bool: ... ``` **Example:** ``` can_first_player_win(1) -> True # take 1, win can_first_player_win(4) -> False # any move leaves opponent in winning position can_first_player_win(5) -> True # take 1, leave 4 for opponent can_first_player_win(8) -> False ``` ## Approach Base cases: n=0 -> False (no stones to take = loss). n in {1,2,3} -> True. Pattern: first player loses iff `n % 4 == 0`. Solve in O(1). For the general version with arbitrary move set, use DP: `dp[i] = any(not dp[i-m] for m in moves if i >= m)`. ## Follow-ups 1. Prove why the `n % 4 == 0` pattern holds. 2. Generalize: players can remove any number in set `S`. Derive the losing positions. 3. Extend to a 2D grid game where players take stones from rows or columns. 4. How do you handle games with cycles using memoization vs. iterative DP?

## Problem A subarray-related problem; likely finding a subarray with some constraint such as a target sum, max sum, or specific property. ## Likely LeetCode equivalent No single unambiguous LC equivalent (title too generic). ## Tags arrays, sliding_window, hash_table

## Problem Design a text editor supporting insert, delete, and cursor movement operations efficiently. ## Likely LeetCode equivalent LC 2296 - Design a Text Editor (>80% confident) ## Tags design, stack, strings

## Problem You have a stream of event attendance records `{event_id, user_id, timestamp}`. Implement a class that supports: - `record(event_id, user_id, timestamp)` - log an attendance entry. - `top_k(k, start_ts, end_ts) -> List[str]` - return the top `k` event IDs by unique attendee count within the time range, sorted by count descending; break ties by event_id ascending. ```python class EventTracker: def record(self, event_id: str, user_id: str, timestamp: int): ... def top_k(self, k: int, start_ts: int, end_ts: int) -> List[str]: ... ``` **Example:** ``` tracker = EventTracker() tracker.record("e1", "u1", 100) tracker.record("e1", "u2", 150) tracker.record("e2", "u1", 120) tracker.record("e2", "u3", 200) tracker.top_k(2, 100, 200) -> ["e1", "e2"] # e1=2, e2=2 -> tie, alphabetical tracker.top_k(1, 100, 150) -> ["e1"] # e1=2 unique in range ``` ## Follow-ups 1. How do you count unique attendees per event efficiently without a full scan? 2. If records can be ingested out of order, how do you handle late arrivals? 3. How would you shard this across multiple nodes for a high-throughput event platform? 4. Extend to return results for a specific category filter on top of the time range.

## Problem Implement a turn-based game engine for a simplified strategy game on an `n x n` grid. Two players alternate turns. Each turn, a player moves one of their pieces to an adjacent cell (up/down/left/right). A piece captures an opponent piece by moving onto its cell. The game ends when one player has no pieces left. Implement: - `move(player, from_pos, to_pos)` - execute a move or raise if invalid. - `valid_moves(player) -> List[Tuple]` - all legal moves for the player. - `is_game_over() -> bool` - `winner() -> Optional[str]` ```python class GameEngine: def __init__(self, n: int, pieces: dict): ... # pieces: {player: [positions]} def move(self, player: str, frm: tuple, to: tuple): ... def valid_moves(self, player: str) -> List[tuple]: ... def is_game_over(self) -> bool: ... def winner(self) -> Optional[str]: ... ``` ## Follow-ups 1. How do you enforce turn order and reject out-of-turn moves? 2. What data structure lets you efficiently look up all pieces on the board? 3. How would you add a move history for undo functionality? 4. Extend to support a simple AI: minimax with alpha-beta pruning for move selection.

## Problem Simulate a vacuum cleaner traversing a grid or graph, covering all reachable cells with minimum moves or steps. ## Likely LeetCode equivalent No direct unambiguous LC equivalent. ## Tags graph, bfs, matrix