Codenation Test Questions jul 15, 2019 topic 1.2

tihs in continue to topic 1.1

There are better screenshots available in Watsapp groups. See if you can find one of those.

My take after reading this Q is to try the following-

  1. Find all SCC in the graph with indegree 0 . An outlet must be opened in each of them. Open 1 outlet in the highest valued node there.
  2. Find average.
  3. Sort all remaining nodes acc to value. Since we need to give priority to maximizing average instead of minimizing outlets, open an outlet at every node which seems to increase average. Recompute average after every new outlet.

But thats just my take, can be right or wrong.