Grokking the Coding Interview: Patterns for Coding Questions

0% completed

​

Solution: Fruits into Baskets

Problem Statement

You are visiting a farm to collect fruits. The farm has a single row of fruit trees. You will be given two baskets, and your goal is to pick as many fruits as possible to be placed in the given baskets.

You will be given an array of characters where each character represents a fruit tree. The farm has following restrictions:

  1. Each basket can have only one type of fruit. There is no limit to how many fruit a basket can hold.
  2. You can start with any tree, but you can’t skip a tree once you have started. 1

.....

.....

.....

Like the course? Get enrolled and start learning!
K

K Curtis

· 4 years ago

The solution I came up with just uses a HashSet.

public static int getFruitCount(char[] fruitTrees) { int maxFruit = 0; int windowStart = 0; HashSet fruitBasket = new HashSet(); for(int windowEnd = 0; windowEnd < fruitTrees.length; windowEnd++) { char currentFruit = fruitTrees[windowEnd]; fruitBasket.add(currentFruit); while (fruitBasket.size() > 2) { fruitBasket.remove(fruitTrees[windowStart]); windowStart++; } maxFruit = Math.max(maxFruit, windowEnd - windowStart+1); }

return maxFruit; }

J

Jeff Goyette

· 4 years ago

I found the map solution a bit hard to follow. Here is an alternative if it helps anyone. In this, I use a list to keep track of the added fruit, and a set to keep track of types of fruit. Functionally this isn't much different than using a map. This does get rid of the windows though.

char[] fruitArr1 = new char[] {'A', 'B', 'C', 'B', 'B', 'C'};

int maxLength = 0;

List fruitBasket = new ArrayList(); Set uniqueFruit = new HashSet();

for (char fruit1 : fruitArr1) { fruitBasket.add(fruit1); uniqueFruit.add(fruit1);

while (uniqueFruit.size() > 2) { uniqueFruit.remove(fruitBasket.remove(0)); } maxLength = Math.max(maxLength, fruitBasket.size()); System.out.println(fruitBasket); System.out.println(maxLength); }

Show 1 reply
S

Sukumar

· 4 years ago

Similar to my comment on previous problem, I am unable to understand why we need to use Map and also reduce is it while loop? what input will not work if we simply remove it? so something like below:

public static int findLength(char[] arr) { int windowStart = 0, maxLength = 0; Map fruitFrequencyMap = new HashMap(); // try to extend the range [windowStart, windowEnd] for (int windowEnd = 0; windowEnd < arr.length; windowEnd++) { fruitFrequencyMap.put(arr[windowEnd], fruitFrequencyMap.getOrDefault(arr[windowEnd], 0) + 1); // shrink the sliding window, until we're left with '2' fruits in the frequency map while (fruitFrequencyMap.size() > 2) { fruitFrequencyMap.remove(arr[windowStart]); windowStart++; // shrink the window } maxLength = Math.max(maxLength, windowEnd - windowStart + 1); } ret

C

CS

· 5 years ago

Hi. Wondering how to deduce that "Fruits into Baskets" is sliding window pattern? Any pointers?

Show 1 reply
A

ag

· 4 years ago

Why is Space Complexity for the fruit basket not O(K) like the parent problem? I didn't get the below part -> "The algorithm runs in constant space O(1)O(1) as there can be a maximum of three types of fruits stored in the frequency map."

Show 1 reply
M

manulorenzop@gmail.com

· 4 years ago

I'm wondering: do we really need the while loop to check if the fruitFrequencyMap is bigger than 2? We are increasing the size of the fruitFrequencyMap with 1 each time. So, is there really the need for the while?

Show 1 reply
K

Keila Mohan

· 3 years ago

I am confused why the algorithm is O(N) running time if there is a for loop and a while loop inside.

Show 2 replies
Abdullah AlKheshen

Abdullah AlKheshen

· 3 years ago

// What's the goal or the reason behind using:

maxLength = max(maxLength, windowEnd - windowStart + 1); return maxLength;

while we can simply return j-i?

Show 1 reply
Hoang Le

Hoang Le

· 2 years ago

Title???