Two Sigma Software Engineer Interview Questions

I applied for a QSE position through a referral (the kind where you interview tech first, then get a team match). I just passed the online assessment (OA) and am about to schedule the next interview.

https://leetcode.com/problems/course-schedule/ (inputs modified but similar to this one) problem similar to KNN algorithm implementation (knowing how to implement it would help). Design a text editor . I implemented it in python using...

LeetCode #43: Multiply Strings. Difficulty: Medium. Topics: Math, String, Simulation. Asked at Two Sigma in the last 6 months.

LeetCode #2050: Parallel Courses III. Difficulty: Hard. Topics: Array, Dynamic Programming, Graph Theory, Topological Sort. Asked at Two Sigma in the last 6 months.

LeetCode #20: Valid Parentheses. Difficulty: Easy. Topics: String, Stack. Asked at Two Sigma in the last 6 months.

LeetCode #528: Random Pick with Weight. Difficulty: Medium. Topics: Array, Math, Binary Search, Prefix Sum, Randomized. Asked at Two Sigma in the last 6 months.

LeetCode #337: House Robber III. Difficulty: Medium. Topics: Dynamic Programming, Tree, Depth-First Search, Binary Tree. Asked at Two Sigma in the last 6 months.

## 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?