Google | OA 2019 | Rose Garden
2358

N rose bushes in garden. Roses are planted in a row and are numberd from 1 to N (left to right). Exacltly one rose will start blooming every day. Find latest day on which there is some blossoming group of size K.
Write function:
def solution(P,K)
that,given a zero-indexed array P containing N intergers (a permutation of number from 1 to N), where P[i] denotes the number of the rose which will start blooming on day number i+1 , and integer K, return the latest day on which there is some blossoming group of size K. If there is no such day funtion should return -1.
Assume that:

  • N is an integer within the range [1...100,000]
  • K is an integer within range [1..N]
  • Array P is a permutation of integers from 1 to N
Example:
P=[3,1,5,4,2] ,  K=1  your function should return 4.
P=[3,1,5,4,2] ,  K=2  your function should return -1.
Means,
3rd rose blooms on Day 1
1st rose blooms on Day 2
5th rose blooms on Day 3
4th rose blooms on Day 4
2nd rose blooms on Day 5

Explaination:
Day1: - - R - -       -> one group [3]
Day2: R - R - -       -> two group [1], [3]
Day3: R - R - R       -> three group [1], [3], [5]
Day4: R - R R R       -> two group [1], [3,4,5]
Day5: R R R R R       -> one group [1,2,3,4,5]
Rose: 1 2 3 4 5 

Comments (9)