Hudson River Trading Software Engineer Phone Screen Questions

I recently had an interview for a C++ new grad position at HRT. The interview lasted 30 minutes; we introduced ourselves and then it quickly began. The question was: Design a game. The board has 9x9 d

## Problem Simulate an auction or order book exchange: match buy/sell orders by price-time priority. Likely involves heaps or sorted structures for order matching. ## Likely LeetCode equivalent No direct match. ## Tags coding, heap, simulation, trading

## Problem Given an integer `n` and a list of integers `factors`, find the smallest integer strictly greater than `n` that is divisible by every element in `factors`. ```python def smallest_divisible(n: int, factors: list[int]) -> int: ... ``` ``` Input: n=10, factors=[3, 4] LCM(3,4) = 12 Smallest multiple of 12 > 10 -> 12 Output: 12 Input: n=12, factors=[3, 4] Must be STRICTLY greater than 12 -> 24 Output: 24 Input: n=0, factors=[5, 7] LCM=35, first multiple > 0 -> 35 Output: 35 ``` ## Follow-ups 1. How do you compute the LCM of a list of numbers? Walk through the GCD-based approach. 2. What is the time complexity of your solution and what are the edge cases (e.g., factors contains 1, or factors contains duplicates)? 3. What if `n` can be up to 10^18? Does your integer arithmetic still work in Python? In Java/C++? 4. Generalize: find the K-th integer greater than N divisible by all factors. How does the formula change?

## Problem Two players alternate turns. There is a token on integer position `pos` on a number line. Each turn the current player moves the token left or right by any value in a given set `moves` (e.g., `{1, 3}`). A player who moves the token to position 0 wins. A player who cannot move (or is forced to move off the line) loses. Given `pos` and `moves`, determine if the first player wins with optimal play. ```python def first_player_wins(pos: int, moves: set[int]) -> bool: ... ``` ``` moves = {1, 3}, pos = 4 Winning positions (W) vs losing positions (L): pos=0: W (you just won) pos=1: W (move 1 -> 0) pos=2: L (can go to 1 or ... 1 is W for opponent; -1 invalid) pos=3: W (move 3 -> 0) pos=4: L (move 1->3 W for opp, move 3->1 W for opp) Output: False (first player loses) ``` ## Follow-ups 1. This is a combinatorial game theory problem. Describe the DP recurrence for `is_winning(pos)`. 2. What is the time complexity of your DP solution, and what is the memoization base case? 3. How does the problem change if moves can also increase `pos` (bidirectional movement)? 4. Extend to a 2D grid: the token is at `(r,c)`, allowed moves are `{up, down, left, right}`. The player who reaches `(0,0)` wins. How do you adapt your solution?