• 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

VMWare SDEII Interview

25 horses 5 tracks Find 3 fastest puzzle

Serialise Deserialise N-ary Tree

Print all nodes that are at distance k from a leaf node

Find an index i such that Arr [i] = i in array of n distinct integers sorted in ascending order.

System Design: Designing a LLD for Hotel Booking

Practo Hiring Experience

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

LeetCode: Container With Most Water

Trie Dictionary

Code Chef PRGIFT Solution

Closed Parentheses checker

The Magic HackerEarth Nirvana solutions Hiring Challenge

1014 Practice Question of New GRE – Princeton

building with N steps, we can take 1,2,3 steps calculate number of ways to reach at top of building

Maximum of all subarrays of size k

Rectangular chocolate bar Create at least one piece which consists of exactly nTiles tiles

Regular Expression Matching

Implement LRU Cache

Naurki.com Security Breach

Python List

Reverse a Linked List in groups of given size

K’th Largest Element in BST when modification to BST is not allowed

Reliance Jio Software Developer Interview Experience

simple sql injection

Binary Tree in Java

Word Break Problem

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

Given Set of words or A String find whether chain is possible from these words or not

Cisco Hiring Event 21st – 22nd Feb 2015

Copyright © 2025 · Genesis Framework · WordPress · Log in