GoHired: Max Sum in circularly situated Values

GoHired: Max Sum in circularly situated Values

This question was asked first in FACEBOOK On Campus for Internship.

There are N trees in a circle. Each tree has a fruit value associated with it.  

A bird can sit on a tree for 0.5 sec and then bird have to move to a neighboring tree. It takes the bird 0.5 seconds to move from one tree to another. The bird gets the fruit value when she sits on a tree. 

We are given N and M (the number of seconds the bird has), and the fruit values of the trees. We have to maximize the total fruit value that the bird can gather. The bird can start from any tree.

Solution 

First lets think for data structure to use.

Here we have a tree with fruit value. No need to think deep for tree and traversal, we can simply create a node with value.

They are in circular, hence we can think of circular queue or array or linkelist.

as Circular Array is easiest one, We can take it. 

Queue is also not needed as no need for front and rear.

Now In circular array we have fruit values.

What we need to find is maximum sum of fruits which bird can traverse.

As bird takes 0.5 seconds to fetch value of fruit and 0.5 seconds to move to another Tree.

We can say is bird can traverse 1 node in 1 sec.

So if bird has X seconds, bird can traverse to X Trees.

Main Problem Statement : Hence Finally we need to get a Window of size X in Circular Array such that sum of the values of the Window is maximum.

Read full article from GoHired: Max Sum in circularly situated Values