• Skip to primary navigation
  • Skip to content
  • Skip to primary sidebar
  • Skip to secondary sidebar

GoHired

Interview Questions asked in Google, Microsoft, Amazon

Join WeekEnd Online Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

  • Home
  • Best Java Books
  • Algorithm
  • Internship
  • Certificates
  • About Us
  • Contact Us
  • Privacy Policy
  • Array
  • Stack
  • Queue
  • LinkedList
  • DP
  • Strings
  • Tree
  • Mathametical
  • Puzzles
  • Graph

Max Sum in circularly situated Values

September 1, 2014 by Dhaval Dave

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.

Solution :

#include<stdio.h>
#include<math.h>
 
int maxTreeSum(int a[], int size, int windowsize)
{
   int max_so_far = 0, max_wind_start = -1;
   int i,j,sum=0;
   int w = windowsize;
   int n = size;
   for(i=0;i<n;i++){
       for(j=0;j<w;j++){
           sum=sum+a[(j+i)%n];
       }
       if(max_so_far < sum){ max_wind_start=i ;max_so_far = sum; }
       sum=0;
 
   }
   printf("Max sum resulting window");
   j=max_wind_start;
   
   while(w--){
        printf(" %d",a[j%n]);
        j++;
    }
    printf("n");
   return max_so_far;
}
 
int main()
{
   int a[] = {2, 3, 4, 1, 2, 1, 5, 3}; //fruit values
   int n = sizeof(a)/sizeof(a[0]); // n
   int s = 3; //Bird has 3 seconds
 
   /* As Bird has 3 seconds it can stay at node for 0.5 sec + 0.5 sec to go to 
   next node so bird can traverse 1 node in 1 sec 
   hence in 3 seconds bird can traverse 3 node*/
 
   int max_sum = maxTreeSum(a, n, s);
   printf("Maximum contiguous sum is %dn", max_sum);
   return 0;
}
 See code at http://ideone.com/f7IdMR
 O(NM) is time complexity for above code.
Solution 2)
Optimized Solution with DP : 
– Keep one Array of size of N
– Each index will carry the fruit value of next S values.
– Instead of Loop
 for(i=0;i<n;i++){
       for(j=0;j<w;j++){
           sum=sum+a[(j+i)%n];
        }
 }
Try to keep a loop with another Array as explained in Below diagram.
First circular array is with fruit value.
Second circular array is with next all fruit values which a window of size S contains.

Instead storing smaller values as shown in diagram, we can store always maximum
eg 9,9,9..10,10

Idea here is to eliminate second loop of j to calculate sum of fruit values every time.
When we know that in next sum only last index value subtracted and next index value will be added

Solution from users awaited.

Solution 3 : 
Instead using Another array in Solution 2) Keep only one variable max_so_far.
For i=0, calculate sum of fruits for next windows ( ie. if window is set 3 , then do)

for i=0,1,2 calculate 
   max_so_far = a[0]+a[1]+a[2];  
   then for each i = 1 to n do following
        sum = max_so_far - a[i-1] + a[i+w-1];
        if (sum < max_so_far ) {
        ....
        }

-> Basically instead searching every time in loop for sum or storing into auxiliary array. we fetched sum in one variable.

Complexity : O(N)
Space Complexity : O(1)

Similar Articles

Filed Under: Interview Questions, problem Tagged With: Array

Reader Interactions

Primary Sidebar

Join WeekEnd Online/Offline Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

Join WeekEnd Online/Offline Batch from 4-April-2020

WhatsApp us

Secondary Sidebar

Custom Search

  • How I cracked AMAZON
  • LeetCode
  • Adobe
  • Amazon
  • Facebook
  • Microsoft
  • Hacker Earth
  • CSE Interview

Top Rated Questions

Implement a generic binary search algorithm for Integer Double String etc

Stock Buy Sell to Maximize Profit

Count number of ways to reach a given score in a game

Find and print longest consecutive number sequence in a given sequence in O(n)

Find shortest distances between every pair of vertices ( Dynamic Programming Floyd Warshall Algorithm)

flattens 2 D linked list to a single sorted link list

Apriori algorithm C Code Data Mining

Find if two rectangles overlap

Count Possible Decodings of a given Digit Sequence

SAP Hiring Off-Campus General Aptitude

Knight Tour Problem (Graph – Breadth First Search)

Practo Hiring Experience

Regular Expression Matching

Code Chef PRGIFT Solution

BFS (Breath First Search)

Word Break Problem

BlueStone E-commerce Interview Experience

Flipkart SDET Interview Experience

Print vertical sum of all the axis in the given binary tree

Print Power Set of a Set

Top 10 Interviews Techniqes for Campus Interview in IIT NIT BITS for MTech

Search element in a matrix with all rows and columns in sorted order

How strtok() Works

Puzzle : 100 doors in a row Visit and Toggle the door. What state the door will be after nth pass ?

Wrong Directions given find minimum moves so that he can reach to the destination

Amazon Interview Experience – SDE Chennai

Maximum sum contiguous subarray of an Array

Find two non repeating elements in an array of repeating elements

Number of Islands BFS/DFS

Possible sizes of bus to carry n groups of friends

Copyright © 2025 · Genesis Framework · WordPress · Log in