Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Fruits into Baskets (medium)

.....

.....

.....

Like the course? Get enrolled and start learning!
A

Anonymous

· 2 years ago

Title???

A

Anonymous

· 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
A

Anonymous

· 4 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 1 reply
A

Anonymous

· 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; }

A

Anonymous

· 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
A

Anonymous

· 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
A

Anonymous

· 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
A

Anonymous

· 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

A

Anonymous

· 5 years ago

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

Show 1 reply

Reading Progress

0%

Vote for new content