Geico·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jun 2026

Summary

Had a technical phone screen for a software engineer role at Geico. One coding question, greedy approach, not too bad once you see the pattern.

Questions Asked (1)

Given a string of houses ('H') and empty spaces ('.'), find the minimum number of food buckets to place in empty positions so every house has at least one adjacent bucket. Return -1 if it's not possible.

Algorithms & Data Structures

Author's notes

Took me a minute to realize you should always try to place the bucket to the right of a house first, not the left.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a greedy algorithm that scans the string from left to right. When you encounter a house that is not yet covered, place a bucket in the rightmost available empty spot that covers it (either the house's right neighbor if empty, otherwise its left neighbor). If no such spot exists, return -1.

Pro tip: After placing a bucket, mark all houses it covers as covered to avoid redundant placements. Also, handle edge cases like houses at the ends of the string and consecutive houses carefully.

1. Understand the problem

Clarify that each bucket covers adjacent houses (left and right). The goal is to minimize buckets while ensuring every house is covered.

2. Choose a greedy strategy

Scan left to right. For each uncovered house, place a bucket as far right as possible to maximize coverage of future houses.

3. Determine bucket placement

For an uncovered house at index i, check if i+1 is empty; if so, place bucket there. Else, check if i-1 is empty; if so, place bucket there. If neither, return -1.

4. Mark covered houses

After placing a bucket, mark the house and its adjacent houses (if any) as covered to avoid redundant checks.

5. Handle edge cases and return result

After scanning, return the total bucket count. If any house remains uncovered, return -1.

Key Points to Mention

Greedy choice: placing a bucket to the right of an uncovered house maximizes future coverage.
Time complexity: O(n) single pass, space complexity: O(1) if we modify input or use a boolean array.
Edge cases: houses at the beginning or end, consecutive houses, all empty spaces, no houses.
Proof of optimality: exchange argument showing that any optimal solution can be transformed to match the greedy choice.
Implementation details: using a loop with index manipulation to skip covered houses.
Return -1 when a house cannot be covered (e.g., 'H.H' with no adjacent empty).

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.