Rose Garden Google OA 2023 Solution
Given an array of roses
. roses[i]
means rose i
will bloom on day roses[i]
. Also given an int k
, which is the minimum number of adjacent bloom roses required for a bouquet, and an int n
, which is the number of bouquets we need. Return the earliest day that we can get n
bouquets of roses.
Example:
Input: roses = [1, 2, 4, 9, 3, 4, 1], k = 2, n = 2
Output: 4
Explanation:
day 1: [b, n, n, n, n, n, b]
The first and the last rose bloom.
day 2: [b, b, n, n, n, n, b]
The second rose blooms. Here the first two bloom roses make a bouquet.
day 3: [b, b, n, n, b, n, b]
day 4: [b, b, b, n, b, b, b]
Here the last three bloom roses make a bouquet, meeting the required n = 2 bouquets of bloom roses. So return day 4.

SOLUTION
Program: Rose Garden Google OA Solution in Python
import collections
def minDaysBloom(roses, k, n):
days = collections.defaultdict(set)
for i, d in enumerate(roses):
days[d].add(i)
startings = {}
endings = {}
count = 0
def boutiques(interval):
return (interval[1] - interval[0] + 1 // k)
for d in sorted(list(days.keys())):
for i in days[d]:
if i-1 in endings and i+1 in startings:
i1, i2 = endings[i-1], startings[i+1]
new_i = [i1[0], i2[1]]
del endings[i1[1]]
del endings[i2[1]]
del startings[i1[0]]
del startings[i2[0]]
endings[new_i[1]] = new_i
startings[new_i[1]] = new_i
count += boutiques(new_i) - boutiques(i1) - boutiques(i2)
continue
if i-1 in endings:
interval = endings[i-1]
count -= boutiques(interval)
interval[1] += 1
count += boutiques(interval)
del endings[i-1]
endings[i] = interval
continue
if i+1 in startings:
interval = startings[i+1]
count -= boutiques(interval)
interval[0] -= 1
count += boutiques(interval)
del startings[i+1]
startings[i] = interval
continue
new_i = [i, i]
endings[i] = new_i
startings[i] = new_i
count += boutiques(new_i)
print(d, count, endings, startings)
if count >= n:
return d
return -1
print(minDaysBloom([1, 2, 4, 9, 3, 4, 1],2,2)) # should print 4
Program: Rose Garden Google OA Solution in C++
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <algorithm>
using namespace std;
int getEarliestDay(const vector<int>& roses, int k, int n) {
vector<int> bloomStatus(roses.size(), 0);
std::unordered_map<int,vector<int>> dayToPosMap;
for (int i=0; i<roses.size(); i++) dayToPosMap[roses[i]].push_back(i);
int maxDay = *std::max_element(roses.begin(), roses.end());
for (int i=1; i<=maxDay; ++i) {
if (dayToPosMap.find(i) == dayToPosMap.end()) continue;
for (int j=0; j<dayToPosMap[i].size(); ++j) bloomStatus[dayToPosMap[i][j]] = 1;
int countBouquets = 0;
for (int j=0; j<bloomStatus.size(); ++j) {
if (bloomStatus[j] == 0) continue;
int numContinuousRoses = 0;
while ((j<bloomStatus.size()) && (bloomStatus[j]==1)) {
++numContinuousRoses;
if (numContinuousRoses == k) {
++countBouquets;
std::cout << "Day " << i << "\tNumber of Bouquets = " << countBouquets << "\n";
if (countBouquets == n) return i; //Earliest Day = i
numContinuousRoses = 0;
}
++j;
}
}
}
return maxDay;
}
int main() {
vector<int> roses = {1, 2, 4, 9, 3, 4, 1};
int earliestDay = getEarliestDay(roses, 2, 2);
std::cout << "\nEarliest Day: " << earliestDay << "\n";
return 0;
}
Program: Rose Garden Google OA Solution in Java
- if K * N > roses.Length, no result
- if can find Ns K adjacent roses before reach to the end of the array. For example minDaysBloom(roses, 2, 2), just return max roses[i], maintain one variable is enough
- for minDaysBloom(roses, 3, 2), will scan to the end of the array, and because we know if reached to the end, there will be a result anyway as K * N <= roses.Length, so need cache all maximum days for each roses[i, …i + K], then sort this list, and return Nth element from this list.
public static int minDaysBloom(int[] roses, int k, int n)
{
if (k * n > roses.Length) return -1;
int bouquets = 0;
int days = int.MinValue;
var daysSet = new HashSet<int>();
int i = 0;
while (i < roses.Length)
{
var adjacent = false;
var day = int.MinValue;
for (int j = i; j < i + k && j < roses.Length; j++)
{
day = Math.Max(day, roses[j]);
if (j < i + k - 1)
{
adjacent = Math.Abs(roses[j] - roses[j + 1]) == 1;
}
}
if (adjacent)
{
bouquets++;
days = Math.Max(days, day);
if (bouquets >= n) return days;
i += k;
}
else
{
daysSet.Add(day);
i++;
}
}
var arr = daysSet.ToArray();
Array.Sort(arr);
Array.Reverse(arr);
return arr[n - 1];
}
Google OA 2023 Questions
- Decreasing Subsequence Partitions Google OA 2023
- Compare Strings Google OA Solution
- Fill 2D Array Google OA Solution
- Largest Subarray Google OA Solution
- Pick Up Coupons Google OA 2023 Solution
- Maximum Area Serving Cake Google OA 2023
Related: