Katkat
Back

Find minimum tanks to cover all houses

Palo Alto NetworksSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question evaluates a candidate's proficiency in algorithm design, specifically greedy strategies and string/array manipulation for coverage and optimization under local adjacency constraints.

You are given a string S representing a street:

  • 'H' = a house
  • '-' = an empty plot where you may place a water tank

A house is considered covered (able to collect rainwater) if there is a water tank placed adjacent to it (either immediately to its left or right).

You may place tanks only on empty plots ('-'). Your task is to compute the minimum number of tanks needed so that every house in S is covered. If it is impossible to cover all houses, return -1.

Example:

  • Input: S = "-H-HH--"
  • One optimal placement is "-HTHHT-" (where 'T' denotes a tank), which uses 2 tanks.

Implement a function that returns the minimum number of tanks required (or -1 if impossible).