Count the Number of Houses at a Certain Distance I

Count the Number of Houses at a Certain Distance I

What is this problem about?

The Count the Number of Houses at a Certain Distance I coding problem describes a street with $n$ houses arranged in a line. Additionally, a shortcut exists between two specific houses $x$ and $y$. For every distance $d$ from 1 to $n$, you need to find how many pairs of houses $(i, j)$ have a shortest path distance exactly equal to $d$.

Note that the path can follow the linear street or use the shortcut.

Why is this asked in interviews?

Oracle uses this problem to evaluate a candidate's ability to model a scenario as a graph. It tests knowledge of the BFS interview pattern or the shortest path pattern. Since $n$ is typically small in version I of this problem, it evaluates whether you can correctly identify the "shortcut" edges and run a standard graph algorithm efficiently.

Algorithmic pattern used

This problem is solved using Graph Construction and Breadth-First Search (BFS) (or the Floyd-Warshall algorithm).

1. Build an adjacency list where each house $i$ is connected to $i-1$ and $i+1$.
2. Add the bidirectional edge $(x, y)$.
3. For each house $i$ from 1 to $n$:
   • Run a BFS to find the shortest distance to all other houses $j$.
   • For every $j > i$, increment the result count for the found distance dist[j].
4. Output the results for all distances $1 \dots n$.

Example explanation

$n = 3$, $x=1, y=3$.

• Edges: (1,2), (2,3), (1,3) (the shortcut).
• House 1:
  • Dist to 2: 1. (Dist 1 count: 1)
  • Dist to 3: 1 (via shortcut). (Dist 1 count: 2)
• House 2:
  • Dist to 3: 1. (Dist 1 count: 3)
• Final: Dist 1 has 3 pairs. Dist 2 has 0. Dist 3 has 0. (Result usually doubled if direction matters, e.g., 6, 0, 0).

Common mistakes candidates make

• Not using the shortcut: Simply calculating $|i-j|$ without checking if the path $i o x o y o j$ is shorter.
• Redundant work: Running BFS $N$ times when $N$ is small is fine, but for very large $N$, a more mathematical approach is needed.
• Directionality: Failing to account for whether the problem asks for unique pairs $(i, j)$ where $i < j$ or ordered pairs where $(i, j)$ and $(j, i)$ are different.

Interview preparation tip

Always visualize "shortcut" problems as adding a single edge to a regular graph (like a line or a ring). Most of the distances will still follow the original pattern, and only those "near" the shortcut will change. This intuition helps in moving from BFS to $O(1)$ or $O(N)$ mathematical solutions.