Practice
1. Given the following recursive binary search code, what is the return value when searching for target = 3 in nums = [1, 3, 5] starting with low=0 and high=2?
def binary_search_recursive(nums, target, low, high):
if low > high:
return -1
mid = low + (high - low) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
return binary_search_recursive(nums, target, mid + 1, high)
else:
return binary_search_recursive(nums, target, low, mid - 1)
print(binary_search_recursive([1,3,5], 3, 0, 2))
easy
Solution
Step 1: Calculate mid for low=0, high=2
mid = 0 + (2-0)//2 = 1; nums[1] = 3 equals target -> return 1.Final Answer:
Option B -> Option BQuick Check:
Target found at index 1 on first recursion [OK]
Hint: Mid calculation picks index 1 with target 3 [OK]
Common Mistakes:
- Returning -1 if confused about base case
- Off-by-one errors in mid calculation
- Returning wrong index due to boundary errors
2. You are given a sorted array and a target number
x. The task is to find k elements closest to x in the array, with ties broken by choosing the smaller elements first. Which of the following approaches guarantees an optimal solution with logarithmic search complexity on the array?easy
Solution
Step 1: Understand problem constraints
The array is sorted, and we wantkclosest elements toxwith tie-breakers favoring smaller elements.Step 2: Identify approach with logarithmic complexity
Binary search on the left boundary of the window of sizekefficiently narrows down the candidate window inO(log(n-k))time, guaranteeing optimality.Final Answer:
Option C -> Option CQuick Check:
Binary search exploits sorted order and window size constraints [OK]
Hint: Binary search on window boundaries exploits sorted array [OK]
Common Mistakes:
- Assuming greedy selection always yields optimal window
- Using DP unnecessarily increasing complexity
- Two-pointer approach is linear, not logarithmic
3. Given the following code for fast exponentiation, what is the value of
result after the first iteration of the while loop when calling myPow(2.0, 3)?easy
Solution
Step 1: Trace first iteration with n=3
Initial values: result=1.0, current_product=2.0, n=3. Since n%2==1, result *= current_product -> result=2.0.Step 2: Update current_product and n
current_product *= current_product -> 4.0, n //= 2 -> 1. Loop continues.Final Answer:
Option D -> Option DQuick Check:
After first iteration, result updated once by current_product=2.0 [OK]
Hint: Check if n is odd to multiply result first [OK]
Common Mistakes:
- Forgetting to multiply result when n is odd
- Updating current_product before result
- Off-by-one in loop iterations
4. You need to find the largest integer
r such that r * r ≤ x for a given non-negative integer x. Which algorithmic approach guarantees an efficient and correct solution for this problem?easy
Solution
Step 1: Understand the problem constraints
The problem requires finding the integer square root efficiently without checking all numbers linearly.Step 2: Identify the suitable algorithm
Modified binary search efficiently narrows down the search space by comparing mid*mid withx, guaranteeing logarithmic time complexity.Final Answer:
Option D -> Option DQuick Check:
Binary search halves the search space each iteration [OK]
Hint: Binary search efficiently narrows down integer roots [OK]
Common Mistakes:
- Assuming greedy linear search is efficient
- Confusing DP with this problem
- Using sorting which is irrelevant
5. Consider the following buggy feasibility check code for Capacity to Ship Packages. Which line contains the subtle bug that can cause incorrect feasibility results?
def can_ship_early_stop(weights, days, capacity):
day_count = 1
current_load = 0
for w in weights:
if current_load + w > capacity:
day_count += 1
current_load = 0
if day_count > days:
return False
current_load += w
return Truemedium
Solution
Step 1: Identify order of operations in feasibility check
The bug is resetting current_load to 0 before incrementing day_count, which causes the current package weight to be lost.Step 2: Correct approach
Day count should increment first, then current_load reset to 0, then add current package weight to current_load.Final Answer:
Option C -> Option CQuick Check:
Resetting current_load before day_count causes lost package weight [OK]
Hint: Reset current_load after incrementing day_count and before adding weight [OK]
Common Mistakes:
- Swapping order of reset and increment
- Forgetting to increment day_count
- Adding weight before reset