7 Python Beginner Level Greedy Interview Questions & Answers

This question is about a developer's knowledge of Python arrays and loops.

You are given an array. You need to convert the array in increasing order-- every next element must be strictly greater than the previous element. To change the array, you perform some operations on the array. In each operation, you choose an element in the array and increase its value by one. You need to return the minimum number of operations required to make the array in increasing order.

/*Example*/

nums = [1,5,2,4,1]
expected output = 14
1 and 5 are already in increasing order
we need to perform 4 operations on 2 make it greater than 4 i.e 6
the array becomes- [1,5,6,4,1]
we need to perform 3 operations on 4 make it greater than 6 i.e 7
the array becomes- [1,5,6,7,1]
we need to perform 7 operations on 1 make it greater than 7 i.e 8
the array becomes- [1,5,6,7,8]

so total number of operations = 14

Solution:

We can iterate over the whole array. We will check two consecutive elements. If the curr element is already greater than the previous element, we don’t need to perform any operation on it. If it is less than or equal to the previous element, we need to perform some operations on it to make it greater than the previous element.

Let’s say, a and b are two consecutive elements, and a is the preceding element of b. Also satisfying b <= a i.e. the current element is less than or equal to the previous element.

We need to make b strictly greater than a with the minimum number of operations. The only way to do so is to make b equal to a + 1. Thus the operations required for element b are-
a + 1 - b

In this way, we will calculate operations for all the elements and sum up them.

def findMinOperations(nums: List[int]) -> int:
	result = 0

	for i in range(len(nums) - 1):
		if nums[i] < nums[i + 1]:
			continue

		result += nums[i] + 1 - nums[i + 1]
		nums[i + 1] = nums[i] + 1

	return result

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

This interview question focuses on Python iteration.

You are given an array of strings. All the strings have the same length. Arrange the strings in such a way that there is one string in each line. The first string in the first line, the second string in the second line, and so on. So if, the array is ['abc', 'bce', 'cea'], the arrangement is:

abc
bce
cea

The characters at the same index in each string form one column. So 'a', 'b', 'c' form one column as they are at the same index 0. Your task is to find the number of unfit columns. An unfit column is that column that is not sorted lexicographically.

So in the above example, the expected output is 1 because there is only 1 column (at index 2) that is unfit.

Solution:

The solution is straightforward. We will check each column if it is unfit or not. To check the unfitness of an ith column, we will iterate over all strings and compare its character at index i with the character of the previous string at index i.

def findUnfitColumns(strings: List[str]) -> int:
	result = 0
	row, col = len(strings), len(strings[0])

	for i in range(col):
		for j in range(row - 1):
			if strings[j][i] > strings[j + 1][i]:
				result += 1
				break

	return result

n = number of strings
m = length of each string
Time complexity - O(n * m)
Space complexity - O(1)

This interview question concentrates on the developer's ability to work with Python frequency and iteration.

You are given an array of rectangles where rectangles[i] = [li, wi] represent the length and the width of the ith rectangle.

You can cut the rectangle to form a square of side ai such that ai <= li and ai <= wi. For each rectangle, you find the largest square that can be formed from that rectangle. Among these given rectangles, your favorite rectangles are those rectangles from which squares of maximum length can be formed. Your task is to count the number of your favorite rectangles.

/*Example*/

Given rectangles = [[5, 8], [3, 9], [5, 12], [16, 5]]
Expected output: 3
Explanation: The largest squares that can be formed from each rectangle are:- [5, 3, 5, 5]. The maximum length of these squares is 5 and their count is 2.

Given rectangles = [[2, 3], [10, 7], [2, 7], [7, 8], [7, 13]]
Expected output: 3
Explanation: The largest squares that can be formed from each rectangle are:- [2, 7, 2, 7, 7]. The maximum length of these squares is 7 and their count is 3.

Solution:

Approach I (using map):

In this approach, we will find the largest square for each rectangle and will store the count of those squares in the map freq. For example rectangles = [[2, 3], [2, 7], [7, 8], [10, 7], [7, 13]],
rectangle dimensions largest-square freq
rectangle[0] [2, 3] 2 freq[2] = 1
rectangle[1] [10, 7] 7 freq[7] = 1
rectangle[2] [2, 7] 2 freq[2] = 2
rectangle[3] [7, 8] 7 freq[7] = 2
rectangle[4] [7, 13] 7 freq[7] = 3
After counting the frequencies, we will check the maximum length and the corresponding count.

from collections import defaultdict
def countFavouriteRectangles(rectangles: List[List[int]]) -> int:
	freq = defaultdict(int)

	for rectangle in rectangles:
		largestSqaure = min(rectangle)
		freq[largestSqaure] += 1

	maxLen = max(freq.keys())
	return freq[maxLen]

Time complexity- O(n)
Space complexity- O(n)

Approach II (greedy):

One thing to note is that while iterating over when we get a new square with maximum length, we need not keep track of frequencies of squares of smaller lengths. For example rectangles = [[2, 3], [2, 7], [7, 8], [10, 7], [7, 13]],
rectangle dimensions largest-sq max-len freq
-Inf -Inf
rectangle[0] [2, 3] 2 2 1
rectangle[1] [10, 7] 7 7 1 #tag_1
rectangle[2] [2, 7] 2 7 1 #tag_2
rectangle[3] [7, 8] 7 7 2
rectangle[4] [7, 13] 7 7 3

#tag_1:- We got new max-len = 7, we will not track frequency for squares of length = 2
#tag_2:- The largest square has length = 2, but max-len = 7. Since we are not keeping track frequency for squares of length = 2, we don’t do anything there.

def countFavouriteRectangles(rectangles: List[List[int]]) -> int:
    count = float('-inf')
    maxLen = float('-inf')

    for rect in rectangles:
        largestSqaure = min(rect)

        if largestSqaure == maxLen:
            count += 1
        elif largestSqaure > maxLen:
            count = 1
            maxLen = largestSqaure

    return count

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

This question shows the developer's knowledge of Python indices.

You are given a string consisting of characters ‘0’ and ‘1’. In one operation, you can change ‘0’ to ‘1’ or ‘1’ to ‘0’. Your task is to find the minimum number of operations so that the resulting string is an alternating binary string.

An alternating binary string has ‘0’ and ‘1’ at alternating positions. For example:- “010101” is an alternating binary string while “00101” is not an alternating binary string.

/*Example*/

Given string = “0100”
Expected output: 1
Explanation: changing only the last character to ‘1’ makes the string an alternating binary string

Given string = “0101”
Expected output: 0
Explanation: already an alternating binary string

Given string = “1011”
Expected output: 1
Explanation: there are two ways to make the string alternating
1.	change to “0101”		operations required = 3
2.	change to “1010”		operations required = 1

Solution:

We will try to make all the characters at even indices equal to ‘0’ and odd indices equal to ‘1’. If at an odd index, the character is not equal to ‘0’ already, we will increase the count by 1. If at an even index, the character is not equal to ‘1’ already, we will increase the count by 1.

We are passing the bit at index i (which is a string) to an integer using int. Then we compare it with i % 2 i.e., odd or even parity.

Since we are always trying to put ‘0’ at even indices and ‘1’ at odd indices, it is not always optimal to have that solution (see example 3). If it takes a count number of operations to make the alternating string with ‘0’ at the first index, it will take len - count number of operations to make the alternating string with ‘1’ at the first index. We will check both at the last.

def minOperations(s: str) -> int:
    count = 0
    for i in range(len(s)):
        bit = int(s[i])
        if bit % 2 != i % 2:
            count += 1

    return min(count, len(s) - count)

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

This interview question tests the developer's skills with Python arrays.

You are given an integer array nums. In one operation, you can choose an index i, and replace nums[i] with -nums[i]. You have to perform exactly countOps number of operations such that the sum of the resulting array is the maximum possible. You can choose one i multiple times.

/*Example*/

Given nums = [4, 2, 3]			countOps = 1
Expected output: 5
Explanation: We replace 2 with -2. The array becomes [4, -2, 3].

Given nums = [3, -1, 0, 2]		countOps = 1
Expected output: 6
Explanation: We choose indices (1, 2, 2). The resulting array becomes [3, 1, 0, 2]

Solution:

First, we will sort the given array.
=> We will flip all the negative numbers exactly once because they will increase the final sum. We will decrease countOps by 1 for each negative number.
=> There may or may not be some remaining countOps left.
=> Sum the array and find the minimum number (it is guaranteed that that minimum number is non-negative).
=> If some countOps is left and it is odd, we will flip the minimum number i.e. make it negative and subtract twice of it from the sum. For example:
● let nums = [-3, -2, -1, 2, 3, 4] countOps = 8
● array after flipping negative numbers = [3, 2, 1, 2, 3, 4] and countOps = 5
● sum = 15 minimum number = 1
● countOps is odd. So we flip the minimum number and subtract it’s twice from sum => sum = sum - 2 * minimum-number = 15 - 2 * 1 = 13 which is our final answer.
=> If some countOps is left and it is even or it is zero, we will return the sum directly because we can choose the minimum number and always flip it. Since countOps is even, there will be no effect. For example:
● let nums = [-3, -2, -1, 2, 3, 4] countOps = 7
● array after flipping negative numbers = [3, 2, 1, 2, 3, 4] and countOps = 4
● sum = 15 minimum number = 1
● countOps is even. So the answer is sum = 15.

def maximizeSum(nums: List[int], countOps: int) -> int:
	nums.sort()

	for i in range(len(nums)):
		if nums[i] > 0:
			break
		nums[i] = -nums[i]
		countOps -= 1

	total = sum(nums)
	minimum = min(nums)

	if countOps % 2 == 1:
		total = total - 2 * minimum

	return total

Time complexity- O(n logn)
Space complexity- O(1)

This interview question shows the developer's ability to work with Python iteration.

Your garden has a long flowerbed represented by the given array flowerbed. The flowerbed has n plots some which are planted and some not i.e. some of them have flowers and some don't. If flowerbed[i] = 0, the ith plot is not planted; if flowerbed[i] = 1, the ith plot is planted. The flowerbed looks beautiful if there are no two flowers that are adjacent.

More formally,
If flowerbed[i] = 1, then if flowerbed[i - 1] = 0 and flowerbed[i + 1] = 0 for all values of i, then the flowerbed is beautiful otherwise it is not.
You are given an integer desiredCount. Your task is to find if we can plant desiredCount more flowers in the flowerbed and the flowerbed remains beautiful.

/*Example*/

Given flowerbed = [1,0,0,0,1]		desiredCount = 1
Expected output: true
Explanation: one more flower is required and it can be planted in the slot with index 2.

Given flowerbed = [1,0,0,0,1]		desiredCount = 2
Expected output: false
Explanation: We can not place 2 more flowers such that the bed remains beautiful.

Solution:

We will iterate over each slot. For ith slot, we will check the previous and the next slot. If all these three slots are empty (i.e. are equal to 0), we can plant a flower at the ith slot. Otherwise, we can not. We will track the count of newly planted flowers and will break the loop as soon as we reach our desiredCount.

def canPlantFlowers(flowerbed: List[int], desiredCount: int) -> bool:
    count = 0
    n = len(flowerbed)

    for i in range(n):
        prev = flowerbed[i - 1] if i > 0 else 0
        next = flowerbed[i + 1] if i < n - 1 else 0
        curr = flowerbed[i]

        is_prev_empty = prev == 0
        is_next_empty = next == 0
        is_curr_empty = curr == 0

        if is_curr_empty and is_prev_empty and is_next_empty:
            flowerbed[i] = 1
            count += 1

            if count >= desiredCount:
                break

    return count >= desiredCount

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

This interview question tests the developer's knowledge of Python arrays.

You are a super parent. You have some cookies of the same or distinct sizes represented by array cookies. The greed factor of a child is the minimum size of the cookie they want. The greed factors of all of your children are given and are represented by array greed. You give at most one cookie to a child to satisfy them. There may be some children with no cookie or some cookies given to no child.

Your task is to find the maximum number of children that you can satisfy with the cookies.

/*Example*/

Given greeds = [1, 2, 3]		cookies = [1, 1]
Expected output: 1
Explanation: only one child at index 0 can be satisfied

Given greeds = [1, 2, 3]		cookies = [1, 2]
Expected output: 2
Explanation: two children at index 0 and 1 can be satisfied

Solution:

We will sort the given arrays. Then we will iterate over both the arrays. For the ith child, we find the smallest cookie which makes them satisfied. As soon as we find a cookie for the ith child, we will then check the cookie for the next child.

def satisfyChildren(greeds: List[int], cookies: List[int]) -> int:
	greeds.sort()
	cookies.sort()

	i, j = 0, 0
	n, m = len(greeds), len(cookies)
	while i < n and j < m:
		if greeds[i] <= cookies[j]:
			i += 1
		j += 1
	return i

n = length of greeds array
m = length of greeds array
Time complexity- O(n logn + m logm)
Space complexity- O(1)