Decagon Software Engineer Interview Questions

## Problem You have a single-threaded CPU running `n` functions (0-indexed). You are given a log of start and end events. Compute the exclusive execution time of each function (time spent in that function, not counting nested calls). Log format: `"function_id:start|end:timestamp"` ```python def exclusive_time(n: int, logs: list[str]) -> list[int]: """Return list of length n with exclusive time for each function.""" pass ``` ``` Input: n = 2 logs = ["0:start:0","1:start:2","1:end:5","0:end:6"] Output: [3, 4] # Function 0: runs [0,1] and [6,6] -> 2+1=3 # Function 1: runs [2,5] -> 4 Input: n = 1 logs = ["0:start:0","0:start:2","0:end:5","0:end:6"] Output: [7] ``` ## Follow-ups 1. How does a stack naturally model the nesting of function calls here? 2. What edge cases arise with recursive functions (same function ID appears on the stack multiple times)? 3. If timestamps were floating-point, how would you adjust the interval arithmetic? 4. Extend to multi-threaded execution: each function has a thread ID — what changes?

## Problem Two players alternate taking tokens from a pile. On each turn a player may take between 1 and `k` tokens (inclusive). The player who takes the last token wins. Given the initial pile size `n` and `k`, determine who wins assuming both play optimally — return `"Player 1"` or `"Player 2"`. ```python def game_winner(n: int, k: int) -> str: pass ``` ``` Input: n = 4, k = 3 Output: "Player 2" # Whatever P1 takes (1,2,3), P2 can take (3,2,1) to finish. # If P1 takes 1 -> 3 left, P2 takes 3 -> wins. Input: n = 5, k = 3 Output: "Player 1" # P1 takes 1 -> 4 left -> P2 is now in losing position. Input: n = 7, k = 2 Output: "Player 1" ``` ## Follow-ups 1. What is the closed-form condition for Player 2 winning in terms of `n` and `k`? 2. How does Sprague-Grundy theory generalize this to sums of such games? 3. Modify the rules so the player who takes the LAST token LOSES (misere game) — how does the winner change? 4. If each player may also choose to skip their turn once, how does that affect the analysis?

## Problem A hidden cell is placed uniformly at random in an N x M grid. You can query a row or a column; the oracle tells you whether the cell is in that row/column. Devise a strategy to locate the cell using the minimum worst-case number of queries, then implement it. ```python def locate_cell( n: int, m: int, oracle # callable: oracle('row', i) -> bool, oracle('col', j) -> bool ) -> tuple[int, int]: pass ``` ``` Example (n=4, m=4): Binary search on rows: ceil(log2(4))=2 queries -> narrow to 1 row Binary search on cols: 2 queries -> narrow to 1 col Total: 4 queries worst case Naive: query each row then each col -> up to n+m-1 queries = 7 ``` ## Follow-ups 1. Prove that binary search on rows then columns is optimal in terms of worst-case query count. 2. If the oracle is noisy (lies with probability p), how would you adapt the strategy? 3. How many expected queries does random probing require before finding the cell? 4. Extend to a 3D grid (N x M x D cube) — what is the optimal worst-case query count?

## Problem "Mado" (window in Japanese) average: given an integer array and an integer `k`, compute the moving average using a window of size `k`. Also implement a streaming version that processes one element at a time. ```python def mado_average(nums: list[float], k: int) -> list[float]: """Return list of averages. First k-1 entries use all available elements.""" pass class StreamingMadoAverage: def __init__(self, k: int): ... def next(self, val: float) -> float: """Return current window average after adding val.""" ... ``` ``` Input: nums = [1, 3, 5, 7, 9], k = 3 Output: [1.0, 2.0, 3.0, 5.0, 7.0] # Window [1]->1, [1,3]->2, [1,3,5]->3, [3,5,7]->5, [5,7,9]->7 Streaming: k=3, next(1)->1.0, next(3)->2.0, next(5)->3.0, next(7)->5.0 ``` ## Follow-ups 1. How do you maintain O(1) per element in the streaming version using a deque and running sum? 2. What happens to floating-point precision after many additions? How would you mitigate drift? 3. Extend to a weighted moving average where recent elements have higher weight. 4. How would you compute the moving median instead of the moving mean efficiently?

## Problem Compute or process the skyline silhouette given a set of building rectangles. ## Likely LeetCode equivalent LeetCode 218 - The Skyline Problem ## Tags coding, stack, heap, geometry, phone