Google | Phone Screen | 2024

I got the following question in the phone screen at Google:

Given is a 2D array that describes the height of a landscape and the location of 2 cities within this 2D array. I am now looking for the highest position to place a water tower there so that both cities can be supplied with water.

Rules:

• The pipes of the tower are not allowed to run diagonally
• The pipes must always slope downwards (i.e. be lower than the previous cell) or be at the same height, otherwise the water would run upwards

Inputs:

heights = [
[4, 9, 7, 6, 5],
[2, 6, 5, 4, 3],
[6, 5, 1, 2, 8],
[3, 4, 7, 2, 5]
]

town1 = [1, 4]
town2 = [3, 1]

Output:

[0, 1]

Explanation:

• From [0, 1], which is 9, for example, a line runs via 9 -> 7 -> 6 -> 5 -> 3 (Town 1)
• A pipeline runs to Town 2 via 9 -> 6 -> 5 -> 4 (Town 2)

Other Example:

heights = [
[9, 0, 1, 0],
[0, 0, 1, 0],
[1, 1, 1, 0]
]

town1 = [1, 3]
town2 = [2, 3]

• Although 9 is the highest here, the water would run upwards to reach the cities, which is not possible
• In this example, a water tower could be placed at all locations where there is a 1