← GEICO Interview Insights

GEICO·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
Jun 2026

Summary

Geico software engineer interview with a greedy algorithm problem on string manipulation. Pretty standard coding round, nothing too wild, but the problem had a subtle edge case that could trip you up if you weren't careful.

Questions Asked (1)

Q1

Given a string representing a street where each character is either a house ('H') or an empty space ('.'), find the minimum number of food buckets you need to place in empty spots so that every house has at least one bucket directly next to it. Return -1 if it's not possible.

Algorithms & Data Structures
Author's notes

The greedy angle is what makes this problem actually interesting.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a greedy algorithm that scans the street from left to right. When you encounter a house that doesn't already have a bucket next to it, place a bucket in the next available empty spot to the right (or if that's not possible, the previous spot). Count the buckets placed and return -1 if any house cannot be covered.

Pro tip: Always handle edge cases like houses at the ends of the string and consecutive houses. Also, consider that placing a bucket might cover two houses, so check both sides before placing a new one.

1. Understand the problem and constraints

Clarify that buckets can only be placed in empty spots ('.'), and each house ('H') must have at least one bucket in an adjacent position (left or right). If any house cannot be covered, return -1.

2. Choose a greedy strategy

Scan the string from left to right. When you find a house that is not yet covered, place a bucket as far right as possible (i.e., at the next empty spot) to maximize coverage of future houses.

3. Implement the scan and placement

Iterate through the string. For each house, check if it already has a bucket on its left or right. If not, try to place a bucket at the next empty spot to the right; if that's not possible, place it at the previous empty spot. If neither is possible, return -1.

4. Count and return the result

Keep a count of buckets placed. After scanning the entire string, return the count. If any house remains uncovered, return -1.

5. Test with edge cases

Verify the solution with cases like a single house at the start or end, consecutive houses, and strings with no empty spots. Ensure the algorithm handles all scenarios correctly.

Key Points to Mention

  • Greedy approach: placing buckets as far right as possible to cover future houses.
  • Time complexity: O(n) single pass, space complexity: O(1) if modifying in place or O(n) if using extra space.
  • Edge cases: houses at boundaries, consecutive houses, no empty spots, and impossible cases.
  • Coverage check: a house is covered if there is a bucket at index-1 or index+1.
  • Return -1 when a house cannot be covered.
  • Avoid unnecessary bucket placements by checking if a house is already covered before placing.

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