What is the time complexity of the binary search algorithm implemented on a sorted list in Python?
Answer: C
Binary search repeatedly divides the search space in half. At each step, the problem size reduces by half, giving a recurrence T(n)=T(n/2)+O(1), which solves to O(logn).
Q.2Medium
What will be the output of the following code implementing bubble sort?
```python
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
print(bubble_sort([64, 34, 25, 12, 22]))
```
Answer: A
Bubble sort repeatedly compares adjacent elements and swaps them if they are in the wrong order. After all passes over [64, 34, 25, 12, 22], the final sorted result is [12, 22, 25, 34, 64].
Q.3Medium
What is the worst-case time complexity of Quick Sort?
Answer: C
Quick Sort's worst case occurs when the pivot chosen is always the smallest or largest element (e.g., already sorted input with naive pivot selection), leading to n recursive calls each of size n−1. This gives T(n)=T(n−1)+O(n), which solves to O(n2).
Q.4Medium
What will be the output of the following code?
```python
def binary_search(arr, target):
low, high = 0, len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
print(binary_search([2, 5, 8, 12, 16, 23], 12))
```
Answer: A
The function performs binary search on [2, 5, 8, 12, 16, 23] looking for 12. The index of 12 in the list is 3 (0-based). The midpoints traced are index 2 (value 8), then index 4 (value 16), then index 3 (value 12) — match found at index 3.
Q.5Medium
Which of the following sorting algorithms has the best average-case time complexity?
Answer: C
Merge Sort divides the array into halves recursively and merges them in sorted order. Its recurrence is T(n)=2T(n/2)+O(n), which by the Master Theorem gives O(nlogn) in all cases (best, average, and worst).
Advertisement
Q.6Medium
What will be the output of the following code that uses recursion to compute the n-th Fibonacci number?
```python
def fib(n):
if n <= 1:
return n
return fib(n - 1) + fib(n - 2)
print(fib(6))
```
Answer: A
The Fibonacci sequence is: fib(0)=0, fib(1)=1, fib(2)=1, fib(3)=2, fib(4)=3, fib(5)=5, fib(6)=8. The naive recursive approach correctly computes fib(6) = 8, though its time complexity is O(2n).
Q.7Medium
What is the space complexity of Merge Sort?
Answer: C
Merge Sort requires auxiliary space proportional to the size of the input array to store the temporary merged subarrays. Additionally, the recursion stack uses O(logn) space, but the dominant term is the auxiliary array, making the total space complexity O(n).
Q.8Medium
What will be the output of the following Python code implementing linear search?
```python
def linear_search(arr, target):
for i, val in enumerate(arr):
if val == target:
return i
return -1
result = linear_search([10, 30, 20, 50, 40], 50)
print(result)
```
Answer: B
The linear search iterates through [10, 30, 20, 50, 40] using enumerate, which provides (index, value) pairs. The value 50 is found at index 3, so the function returns 3. Note that enumerate is 0-based, so index 3 corresponds to the 4th element.
Q.9Medium
Which of the following correctly describes the working principle of Insertion Sort?
Answer: C
Insertion Sort builds the sorted array one element at a time. For each element, it shifts larger elements in the sorted portion to the right and inserts the current element in the correct position. Its best-case time complexity is O(n) for a nearly sorted array, and worst case is O(n2).
Q.10Medium
What will be the output of the following code that implements a recursive binary search?
```python
def rec_binary_search(arr, low, high, target):
if low > high:
return -1
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
return rec_binary_search(arr, mid + 1, high, target)
else:
return rec_binary_search(arr, low, mid - 1, target)
arr = [1, 3, 5, 7, 9, 11]
print(rec_binary_search(arr, 0, len(arr) - 1, 7))
```
Answer: C
The function searches for 7 in [1, 3, 5, 7, 9, 11]. First call: mid = (0+5)//2 = 2, arr[2] = 5 < 7, so search right. Second call: low=3, high=5, mid=4, arr[4]=9 > 7, so search left. Third call: low=3, high=3, mid=3, arr[3]=7 == 7, returns index 3.
