Rose Garden Google OA

Rose Garden Google OA 2023 Solution

by

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.

Rose Garden Google OA

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

  1. if K * N > roses.Length, no result
  2. 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
  3. 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

Related:

Leave a Comment

9 + 14 =