No results found for the specified position. What are the minimum number of days to mak... Python Intermediate Level Binary Search Mock Interview

MockQuestions

Python Intermediate Level Binary Search Mock Interview

Question 2 of 15 for our Python Intermediate Level Binary Search Mock Interview

Get More Information About Our Python Intermediate Level Binary Search Interview Questions

Question 2 of 15

What are the minimum number of days to make bouquets?

This question focuses on the developer's knowledge of Python binary search and loops.

You own a garden which has flowers arranged in a row. The flowers have not bloomed yet. You need to make m bouquets. To make one bouquet, you need k adjacent flowers from the garden. For the ith flower, the adjacent flowers are (i - 1)th and (i + 1)th flowers.
The garden has n flowers. You are given an array bloomDay of size n. The ith flower will bloom on day bloomDay[i]. One flower can be used to make at most one bouquet.
Your task is to find the minimum number of days you need to wait so that enough flowers have bloomed to make m bouquets. If it is impossible to make m bouquets, return -1.

/*Example*/

bloomDay = [1, 10, 3, 10, 2]	m = 3		k = 1
expected output = 3
explanation:- x represents that the flower at that position has bloomed
after day 1:- [x, _, _, _, _]
after day 2:- [x, _, _, _, x]
after day 3:- [x, _, x, _, x]	After 3 days, we can make 3 bouquets.

Solution:

We can use binary search for it. Let’s say min is the minimum of days required. If we are asked:-
● Can we make m bouquets in days less than min? The answer is definitely no.
● Can we make m bouquets in days greater than or equal to min? The answer is definitely yes.

0 1 … min - 1 min min + 1 … max-possible
F F F F T T T T

We can do the binary search from 0 to max-possible. We will check if we can make m bouquets in a mid number of days or not. We will update the variables accordingly as in the code. The value of max-possible is the maximum of bloomDay array i.e. the maximum number of days that a flower will take to bloom.

To check if we can make m bouquets in a mid number of days or not, we will use canMake function. We will see which flowers will bloom on or before the day days. After checking bloomed flowers, we see the number of adjacent flowers and then count the number of bouquets that can be formed using those adjacent flowers.

def canMake(limit, bloomDay, m, k):
	'''
		return True if we can make m bouquets with 
		k adj flower within 'limit' days 
	'''
	bouquetsMade, adjFlowers = 0, 0
	
	for day in bloomDay:
		# if there is a day which is not reached yet then
		# mark the adjacent flower count to 0
		if day > limit:
			adjFlowers = 0
			continue

		# if day is reached then increase the bouquetsMade
		# and adjacent flower
		bouquetsMade += (adjFlowers + 1) // k
		adjFlowers = (adjFlowers + 1) % k
	
	return bouquetsMade >= m


def minDays(bloomDay, m, k):
	if m * k > len(bloomDay):
		return -1
	
	mini, maxi = 1, max(bloomDay)

	while mini < maxi:
		mid = (mini + maxi) // 2

		if canMake(mid, bloomDay, m, k):
			maxi = mid
		else:
			mini = mid + 1
	return mini

Time complexity- O(n log(max_of_bloomDay))
Space complexity- O(1)

Written by on May 22nd, 2021

Next Question

How to Answer: What are the minimum number of days to make bouquets?

Advice and answer examples written specifically for a Python Intermediate Level Binary Search job interview.

  • 2. What are the minimum number of days to make bouquets?

      This question focuses on the developer's knowledge of Python binary search and loops.

      You own a garden which has flowers arranged in a row. The flowers have not bloomed yet. You need to make m bouquets. To make one bouquet, you need k adjacent flowers from the garden. For the ith flower, the adjacent flowers are (i - 1)th and (i + 1)th flowers.
      The garden has n flowers. You are given an array bloomDay of size n. The ith flower will bloom on day bloomDay[i]. One flower can be used to make at most one bouquet.
      Your task is to find the minimum number of days you need to wait so that enough flowers have bloomed to make m bouquets. If it is impossible to make m bouquets, return -1.

      /*Example*/
      
      bloomDay = [1, 10, 3, 10, 2]	m = 3		k = 1
      expected output = 3
      explanation:- x represents that the flower at that position has bloomed
      after day 1:- [x, _, _, _, _]
      after day 2:- [x, _, _, _, x]
      after day 3:- [x, _, x, _, x]	After 3 days, we can make 3 bouquets.

      Solution:

      We can use binary search for it. Let’s say min is the minimum of days required. If we are asked:-
      ● Can we make m bouquets in days less than min? The answer is definitely no.
      ● Can we make m bouquets in days greater than or equal to min? The answer is definitely yes.

      0 1 … min - 1 min min + 1 … max-possible
      F F F F T T T T

      We can do the binary search from 0 to max-possible. We will check if we can make m bouquets in a mid number of days or not. We will update the variables accordingly as in the code. The value of max-possible is the maximum of bloomDay array i.e. the maximum number of days that a flower will take to bloom.

      To check if we can make m bouquets in a mid number of days or not, we will use canMake function. We will see which flowers will bloom on or before the day days. After checking bloomed flowers, we see the number of adjacent flowers and then count the number of bouquets that can be formed using those adjacent flowers.

      def canMake(limit, bloomDay, m, k):
      	'''
      		return True if we can make m bouquets with 
      		k adj flower within 'limit' days 
      	'''
      	bouquetsMade, adjFlowers = 0, 0
      	
      	for day in bloomDay:
      		# if there is a day which is not reached yet then
      		# mark the adjacent flower count to 0
      		if day > limit:
      			adjFlowers = 0
      			continue
      
      		# if day is reached then increase the bouquetsMade
      		# and adjacent flower
      		bouquetsMade += (adjFlowers + 1) // k
      		adjFlowers = (adjFlowers + 1) % k
      	
      	return bouquetsMade >= m
      
      
      def minDays(bloomDay, m, k):
      	if m * k > len(bloomDay):
      		return -1
      	
      	mini, maxi = 1, max(bloomDay)
      
      	while mini < maxi:
      		mid = (mini + maxi) // 2
      
      		if canMake(mid, bloomDay, m, k):
      			maxi = mid
      		else:
      			mini = mid + 1
      	return mini

      Time complexity- O(n log(max_of_bloomDay))
      Space complexity- O(1)

      Written by S. Kumar on May 22nd, 2021