Uber·Backend Engineer·Technical Phone Screen·Senior

Senior

Jul 2026

Summary

Uber backend interview with a combinatorics problem that looks deceptively simple but has some real math hiding underneath. The kind of question where you either see the pattern or you're just staring at examples hoping something clicks.

Questions Asked (1)

You have a 1D array of houses where some are initially infected. Each day, an infected house can spread to one neighbor. How many distinct orderings exist in which all houses eventually become infected?

Algorithms & Data Structures

Author's notes

The setup sounds like BFS/simulation at first and I think most people go down that path before realizing it's a counting problem.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the infection process as a combinatorial problem where each day's spread corresponds to choosing a direction for each infected segment. Use dynamic programming or combinatorial counting to compute the number of distinct orderings, considering the initial infected positions and the constraints of 1D spread.

Pro tip: Clarify that 'distinct orderings' refers to the sequence of infection events (which house gets infected when), not the final configuration. This shows attention to detail and avoids misinterpretation.

1. Clarify the problem

Confirm that we are counting the number of possible sequences of infection events (orderings) that lead to all houses infected, given the initial infected set. Ensure understanding of 'distinct orderings' and constraints.

2. Identify independent segments

Split the array into independent segments separated by initially infected houses. Each segment is a contiguous block of uninfected houses bounded by infected houses or array ends.

3. Count orderings per segment

For each segment, the infection spreads from the boundaries inward. The number of orderings is the number of ways to interleave the infections from the left and right boundaries, which is a binomial coefficient based on segment length and distances to boundaries.

4. Combine segments

Multiply the counts for each segment and then multiply by the multinomial coefficient to account for interleaving infections across different segments, since segments are independent.

5. Handle edge cases

Consider cases where there are no initially infected houses (impossible to infect all), or where all houses are initially infected (only one ordering). Also handle segments at the ends with only one boundary.

Key Points to Mention

Dynamic programming or combinatorial counting approach
Independence of segments separated by infected houses
Binomial coefficients for interleaving left and right spread within a segment
Multinomial coefficient for combining orderings across segments
Edge cases: no initial infection, all infected, single boundary segments
Time complexity: O(n) or O(n^2) depending on implementation

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.