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.

Loading coding console...

Quick Overview

Count Valid Infection Orders

Constraints

Examples

Hints