← Uber Interview Insights

Uber·Backend Engineer·Technical Phone Screen·Intermediate

Intermediate
May 2026

Summary

Uber backend interview with a combinatorics-heavy coding question. The problem was deceptively math-y for what I expected to be a straightforward algorithms round.

Questions Asked (1)

Q1

Given a 1D array of houses where some are initially infected, and each day an infected house can spread to one of its immediate neighbors, count the total number of distinct orderings in which all healthy houses become infected.

Algorithms & Data Structures
Author's notes

I stared at this for a bit before realizing it's a counting problem, not a simulation.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as independent infection spreads from each initially infected house, where each healthy house is infected by the nearest source; the total number of orderings is the product of binomial interleavings of the infection sequences from each source. Use combinatorics and modular arithmetic to compute the product efficiently.

Pro tip: Clarify the problem constraints and edge cases (e.g., multiple sources, no healthy houses) before diving into the combinatorial formula, and mention that the result can be computed modulo 10^9+7 to handle large numbers.

1. Clarify the problem and constraints

Confirm the interpretation: each day, every infected house can spread to one neighbor, and we count distinct orderings of all infections. Ask about constraints (array size, number of sources) and whether the answer should be modulo a prime.

2. Partition houses by nearest source

For each initially infected house, determine the contiguous segment of healthy houses it will infect (based on distance). This partitions the healthy houses into independent groups.

3. Compute infection orderings per segment

For a segment of length L infected by a single source, the number of valid infection orders is 2^(L-1) (each house except the source can be infected from left or right). Use this to get the count for each segment.

4. Combine orderings via binomial coefficients

The total number of orderings is the product over segments of (binomial(total_infected_so_far + L, L) * ways_for_segment), where ways_for_segment is 2^(L-1). Compute using precomputed factorials and modular inverses.

5. Handle edge cases and return result

If there are no healthy houses, return 1. If there are no initially infected houses, return 0. Otherwise, return the computed product modulo 10^9+7.

Key Points to Mention

  • Independence of infection spreads from different sources
  • Combinatorial interleaving of sequences using binomial coefficients
  • Formula for single-source segment: 2^(L-1) orderings
  • Modular arithmetic with precomputed factorials and inverse factorials
  • Edge cases: no healthy houses, no infected houses, multiple sources
  • Time complexity: O(n) after precomputation, space complexity: O(n)

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