How to solve this Google Interview Graph Question

Problem statement-

There are N homes in a village, we have to facilitate water supply in each of them. We can either build a well in a home or connect it with pipe to some different home already having water supply. More formally, we can either build a new well in the home or connect it with a pipeline to some different home which either has it’s own well or further gets water supply from a different home and so on. There is some cost associated with both building a new well and laying down a new pipeline. We have to supply water in all homes and minimise the total cost.

Input-
First line contains an integer N, the number of homes.
The next line contains N integers, the ith integer denotes the cost of building a well in that home.
Next line contains an integer K, then K lines follows. Each of which contains 3 integers i, j and p. Which denotes the cost ‘p’ of laying down pipeline between homes i and j.

Output-
Output a single integer - the minimum cost to supply water to all the homes

Link to the problem- https://leetcode.com/problems/optimize-water-distribution-in-a-village/
Unfortunately, Leetcode has moved the problem to ‘for premium users only’ since the last time I tried it. So, you won’t be able to access it unless you have the premium subscription. But fortunately, I remember the problem statement.

Looking for help. @l_returns, @anon55659401 @ssjgz @vijju123

1 Like
Hint

It’s a graph problem (omg :D), what do you think what is needed here? (consider that it is a minimisation problem)

Hint2

How could we “add” the costs of creating wells in the homes into the graph?

Solution

The graph we need is as follows: take all edges already provided by the problem. Then create a new vertex, say “-1” and connect it to each home with the cost of building a well in that home.
Then calculate the minimum spanning tree, the cost of that will be the answer.

2 Likes

Makes sense. Thank you. Actually, when I couldn’t solve it(it was from Leetcode’s Biweekly contest that happened the last Saturday and I participated Virtually on Sunday morning. This was the 4th question and I had solved 3/4 questions. At that time this question was still public), I Googled for the solution and found this- Google | Phone screen | Water supply thread on Leetcode. Where people were talking that it’s a graph question. Infact my intuition was also for graph but I couldn’t formulate. :frowning:

1 Like