Count Houses in a Circular Street

Count Houses in a Circular Street

What is this problem about?

This is an "Interactive" problem where you are placed in a house on a circular street. You don't know how many houses are on the street. You have two actions: move to the next house (clockwise) or "open/close" the door of the current house. The goal is to count the total number of houses. There is a limit on the number of moves/actions you can perform.

Why is this asked in interviews?

Google uses interactive problems to test a candidate's ability to think about state and consistency. Unlike static array problems, you must modify the environment to "mark" your progress. This specific problem tests your ability to create a "reset" point and measure the distance back to it, a technique used in many circular buffer and linked list scenarios.

Algorithmic pattern used

The pattern used is Environmental Marking. To count the houses, you first need to ensure the street is in a known state. A common strategy is to walk along the street for a "sufficiently large" number of steps (given by the constraints) and close every door. Then, open the door of the house you are currently in. Move house by house, counting each step, until you encounter a house with an open door. That count is the number of houses.

Example explanation

Imagine a street with 3 houses.

1. Start at House A. Close its door. Move to House B, close it. Move to House C, close it. (Do this for many steps to be sure all are closed).
2. Now at some House $X$. Open its door. Count = 0.
3. Move to the next house. Count = 1. Door is closed.
4. Move to the next house. Count = 2. Door is closed.
5. Move to the next house. Count = 3. Door is OPEN!
6. You have returned to the start. The count is 3.

Common mistakes candidates make

A common mistake is forgetting to initialize the environment (closing all doors first). Without this, you might see an open door that was already open, giving an incorrect count. Another error is not understanding the circular nature—thinking the street has an "end" rather than wrapping around.

Interview preparation tip

In interactive problems, always look for a way to "anchor" yourself. Since you can't see the whole data structure, modifying a piece of it (like opening a door or changing a value) becomes your way of detecting when you've returned to a specific point.