Why Divide and Conquer and What It Gives You in DSA Python - Test Your Knowledge

Practice - 5 Tasks

1fill in blank

easy

Complete the code to split the list into two halves.

DSA Python

mid = len(arr) [1] 2

Drag options to blanks, or click blank then click option'

A+

B-

C*

D//

Attempts:

3 left

💡 Hint

Common Mistakes

Using '/' which returns a float, causing errors in indexing.

Using integer division (//) splits the list into two equal halves without decimals.

2fill in blank

medium

Complete the code to recursively sort the left half of the list.

DSA Python

left_sorted = divide_and_conquer(arr[:[1]])

Drag options to blanks, or click blank then click option'

Amid

Blen(arr)

C0

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Using full length instead of midpoint for slicing.

We pass the left half slice up to the midpoint to sort it recursively.

3fill in blank

hard

Fix the error in the merge function to combine two sorted lists.

DSA Python

while i < len(left) and j [1] len(right):

Drag options to blanks, or click blank then click option'

A==

B>=

C<

D!=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '>=' causes the loop to run out of bounds.

The loop continues while both indices are within their list lengths, so use <.

4fill in blank

hard

Fill both blanks to complete the base case and recursive call in divide and conquer.

DSA Python

if len(arr) [1] 1:
    return arr
mid = len(arr) [2] 2
return merge(divide_and_conquer(arr[:mid]), divide_and_conquer(arr[mid:]))

Drag options to blanks, or click blank then click option'

A<=

B==

C//

D+

Attempts:

3 left

💡 Hint

Common Mistakes

Using '==' for base case misses empty list.

Using '+' instead of '//' for midpoint.

The base case returns when the list has 1 or fewer elements (<= 1). The midpoint uses integer division (//) to split the list.

5fill in blank

hard

Fill all three blanks to complete the merge function that combines two sorted lists.

DSA Python

result = []
i, j = 0, 0
while i < len(left) and j < len(right):
    if left[i] [1] right[j]:
        result.append(left[i])
        i += 1
    else:
        result.append(right[j])
        j += 1
result.extend(left[[2]:])
result.extend(right[[3]:])
return result

Drag options to blanks, or click blank then click option'

A<=

B<

Ci

Dj

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<=' causes duplicates in merge.

Using wrong indices for extending leftover elements.

Use '<' to compare elements. Extend the result with remaining elements starting from index i in left and j in right.

Practice

1. What is the main advantage of using the Divide and Conquer approach in algorithms?

easy

A. It breaks a problem into smaller subproblems to solve them independently

B. It uses more memory to store intermediate results

C. It always uses iterative loops instead of recursion

D. It avoids sorting data completely

Solution

1. Step 1: Understand the divide and conquer method

   Divide and conquer splits a big problem into smaller parts that are easier to solve.

2. Step 2: Identify the main benefit

   By solving smaller subproblems independently, the overall problem becomes simpler and often faster to solve.

3. Final Answer:

   It breaks a problem into smaller subproblems to solve them independently -> Option A

4. Quick Check:

   Divide and conquer = break problem into smaller parts [OK]

Hint: Divide big problems into smaller parts to solve easily [OK]

Common Mistakes:

• Thinking divide and conquer avoids recursion
• Confusing divide and conquer with dynamic programming
• Believing it always uses more memory

2. Which of the following is the correct syntax to start a recursive divide and conquer function in Python?

easy

A. def divide_and_conquer(data) ->

B. function divide_and_conquer(data) {

C. def divide_and_conquer[data]:

D. def divide_and_conquer(data):

Solution

1. Step 1: Recall Python function syntax

   In Python, functions start with def, followed by the function name and parentheses with parameters.

2. Step 2: Identify the correct syntax

   def divide_and_conquer(data): uses correct Python syntax: def divide_and_conquer(data): with colon at the end.

3. Final Answer:

   def divide_and_conquer(data): -> Option D

4. Quick Check:

   Python function = def name(params): [OK]

Hint: Python functions start with def and end with colon [OK]

Common Mistakes:

• Using curly braces instead of colon
• Using square brackets for parameters
• Missing colon at function end

3. What will be the output of the following Python code using divide and conquer to sum a list?

def sum_list(arr):
    if len(arr) == 1:
        return arr[0]
    mid = len(arr) // 2
    left_sum = sum_list(arr[:mid])
    right_sum = sum_list(arr[mid:])
    return left_sum + right_sum

print(sum_list([2, 4, 6, 8]))

medium

A. 10

B. 24

C. 20

D. Error

Solution

1. Step 1: Understand the base case and recursion

   If the list has one element, return it. Otherwise, split the list into two halves and sum each half recursively.

2. Step 2: Trace the recursive calls for [2,4,6,8]

   Split into [2,4] and [6,8]. Sum [2,4]: split into [2] and [4], sums 2+4=6. Sum [6,8]: split into [6] and [8], sums 6+8=14. Total sum = 6 + 14 = 20.

3. Final Answer:

   20 -> Option C

4. Quick Check:

   2+4+6+8 = 20 [OK]

Hint: Sum halves separately then add for total sum [OK]

Common Mistakes:

• Adding length instead of values
• Returning list slices instead of sums
• Confusing mid index calculation

4. Identify the error in this divide and conquer function to find the maximum element:

def find_max(arr):
    if len(arr) == 1:
        return arr[0]
    mid = len(arr) // 2
    left_max = find_max(arr[:mid])
    right_max = find_max(arr[mid:])
    if left_max > right_max:
        return left_max
    else:
        return right_max

print(find_max([]))

medium

A. Function does not handle empty list input

B. Incorrect base case condition

C. Wrong comparison operator used

D. Mid index calculation is wrong

Solution

1. Step 1: Check base case for empty list

   The function only handles lists with length 1 or more. It does not check if the list is empty, so calling with [] causes an error.

2. Step 2: Understand the error cause

   Calling len(arr) == 1 fails for empty list, and slicing empty list still returns empty list, causing infinite recursion or error.

3. Final Answer:

   Function does not handle empty list input -> Option A

4. Quick Check:

   Empty input needs special handling [OK]

Hint: Check for empty input before recursion [OK]

Common Mistakes:

• Ignoring empty list edge case
• Assuming input always has elements
• Not adding input validation

5. You want to count how many times a number appears in a large list using divide and conquer. Which approach correctly applies divide and conquer to solve this?

hard

A. Iterate the whole list once and count directly without splitting

B. Split the list into halves, count occurrences in each half recursively, then add counts

C. Sort the list first, then count occurrences using a loop

D. Use a dictionary to store counts without recursion

Solution

1. Step 1: Understand divide and conquer for counting

   Divide and conquer means splitting the problem into smaller parts, solving each part, then combining results.

2. Step 2: Apply to counting occurrences

   Split the list into two halves, count how many times the number appears in each half recursively, then add the two counts for total.

3. Final Answer:

   Split the list into halves, count occurrences in each half recursively, then add counts -> Option B

4. Quick Check:

   Divide, count halves, combine counts [OK]

Hint: Count halves separately then add for total count [OK]

Common Mistakes:

• Counting without splitting (not divide and conquer)
• Sorting first (not needed here)
• Using dictionary without recursion