How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Uber.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Uber during technical interviews.

Count Valid Infection Orders | Uber Coding Question

Quick Overview

This question evaluates combinatorial enumeration and algorithmic reasoning by counting valid sequences of state changes in a linear infection process. It is commonly asked in technical interviews because it measures the ability to model propagation constraints, count permutations under adjacency restrictions, and implement efficient solutions within the Coding & Algorithms domain, focusing on practical application rather than purely conceptual understanding.

Count Valid Infection Orders

Company: Uber

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

You are given an integer `n` representing houses arranged in a line and indexed from `0` to `n - 1`, and a sorted array `infected` containing the indices of houses that are already infected at time `0`. A healthy house can become infected only if at least one of its immediate neighbors is already infected. At each step, exactly one new house becomes infected. The process continues until all houses are infected. Two infection processes are considered different if the sequence of newly infected house indices differs at any step. Return the number of distinct valid infection sequences as an integer.

Quick Answer: This question evaluates combinatorial enumeration and algorithmic reasoning by counting valid sequences of state changes in a linear infection process. It is commonly asked in technical interviews because it measures the ability to model propagation constraints, count permutations under adjacency restrictions, and implement efficient solutions within the Coding & Algorithms domain, focusing on practical application rather than purely conceptual understanding.

You are given an integer n representing houses arranged in a line from 0 to n - 1, and a sorted array infected containing the indices of houses already infected at time 0. A healthy house can become infected only if at least one of its immediate neighbors is already infected. At each step, exactly one new house becomes infected, and the process continues until all houses are infected. Two infection processes are different if their sequence of newly infected house indices differs at any step. Return the exact number of distinct valid infection sequences. If all houses are already infected initially, the empty sequence counts as one valid sequence.

Constraints

1 <= n <= 100000
1 <= len(infected) <= n
0 <= infected[i] < n
infected is sorted in strictly increasing order
Use arbitrary-precision arithmetic if needed, since the answer can be large

Examples

Input: (5, [0, 4])

Expected Output: 4

Explanation: There is one internal gap of length 3: houses [1, 2, 3]. At each of the first 2 steps, you can infect from the left end or the right end of that gap, so the total is 2^(3-1) = 4.

Input: (5, [2])

Expected Output: 6

Explanation: The left segment [1, 0] has a forced local order, and the right segment [3, 4] also has a forced local order. Interleaving these two length-2 sequences gives 4! / (2! * 2!) = 6.

Input: (4, [0])

Expected Output: 1

Explanation: Only the right side exists, so the houses must be infected in order [1, 2, 3].

Input: (4, [0, 1, 2, 3])

Expected Output: 1

Explanation: All houses are already infected, so the only valid process is the empty sequence.

Input: (8, [1, 6])

Expected Output: 240

Explanation: The segments have lengths 1, 4, and 1. The middle internal gap contributes 2^(4-1) = 8 local orders. Interleavings contribute 6! / (1! * 4! * 1!) = 30, so the answer is 30 * 8 = 240.

Input: (10, [0, 3, 8])

Expected Output: 1680

Explanation: The healthy segments have lengths 2, 4, and 1. The two internal gaps contribute 2^(2-1) * 2^(4-1) = 2 * 8 = 16. Interleavings contribute 7! / (2! * 4! * 1!) = 105, so the total is 105 * 16 = 1680.

Input: (7, [1, 2, 5])

Expected Output: 24

Explanation: There is a zero-length gap between 1 and 2, which contributes nothing. The positive segments have lengths 1, 2, and 1, and the internal length-2 gap contributes 2 local orders. Interleavings contribute 4! / (1! * 2! * 1!) = 12, so the answer is 12 * 2 = 24.

Hints

Split the healthy houses into independent segments created by the initially infected houses. End segments behave differently from gaps that are surrounded by infected houses on both sides.
For an internal gap of length g, think about how many times you can choose between infecting from the left side or the right side before the last house is forced. After finding each segment's local count, count how many ways their steps can be interleaved.

Last updated: Apr 23, 2026

Loading coding console...

Quick Overview

Count Valid Infection Orders

Company: Uber

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Constraints

1 <= n <= 100000
1 <= len(infected) <= n
0 <= infected[i] < n
infected is sorted in strictly increasing order
Use arbitrary-precision arithmetic if needed, since the answer can be large

Examples

Input: (5, [0, 4])

Expected Output: 4

Explanation: There is one internal gap of length 3: houses [1, 2, 3]. At each of the first 2 steps, you can infect from the left end or the right end of that gap, so the total is 2^(3-1) = 4.

Input: (5, [2])

Expected Output: 6

Explanation: The left segment [1, 0] has a forced local order, and the right segment [3, 4] also has a forced local order. Interleaving these two length-2 sequences gives 4! / (2! * 2!) = 6.

Input: (4, [0])

Expected Output: 1

Explanation: Only the right side exists, so the houses must be infected in order [1, 2, 3].

Input: (4, [0, 1, 2, 3])

Expected Output: 1

Explanation: All houses are already infected, so the only valid process is the empty sequence.

Input: (8, [1, 6])

Expected Output: 240

Explanation: The segments have lengths 1, 4, and 1. The middle internal gap contributes 2^(4-1) = 8 local orders. Interleavings contribute 6! / (1! * 4! * 1!) = 30, so the answer is 30 * 8 = 240.

Input: (10, [0, 3, 8])

Expected Output: 1680

Input: (7, [1, 2, 5])

Expected Output: 24

Hints

Split the healthy houses into independent segments created by the initially infected houses. End segments behave differently from gaps that are surrounded by infected houses on both sides.
For an internal gap of length g, think about how many times you can choose between infecting from the left side or the right side before the last house is forced. After finding each segment's local count, count how many ways their steps can be interleaved.

Last updated: Apr 23, 2026

Loading coding console...