Round 1

The first round involved a medium-level DSA problem. The interviewer was friendly and made the discussion comfortable.

Problem Statement:

You are given an integer n representing the number of houses in a line, and an array initial_infected indicating the houses infected on day 0.

Each day, an infected house spreads the infection to its immediate neighbors (i-1 and i+1, if valid).

Return the number of distinct sequences in which all houses become infected.

Example
n = 8
initial_infected = [2, 7]
Output: 48

Explanation:
Infection spreads outward from initially infected houses, forming segments of uninfected houses. Each segment can be infected in different valid orders.

Edge segments (like [1] and [8]) have only one way.
The middle segment [3,4,5,6] can be infected from both sides (2 and 7), so the infection order can interleave in multiple ways.

Counting all valid interleavings gives the total number of sequences = 48.