Sorting and searching are the bread and butter of algorithm interviews. This set checks your understanding of time and space complexity, stability, in-place sorting and how algorithms like binary search, quicksort and merge sort actually behave.
How to practise: read each question and tap the option you think is correct. You will see right away whether you got it, along with a short explanation, and your score is tracked at the bottom of the screen. This set has 16 questions.
Q1. Binary search requires the input to be:
a) Stored in a linked list
b) Sorted
c) Of even length
d) Free of negative numbers
Q2. What is the maximum number of comparisons binary search needs to find an element in a sorted array of 1024 elements?
a) 10
b) 11
c) 512
d) 1024
Q3. Why is mid = low + (high - low) / 2 preferred over mid = (low + high) / 2 in binary search?
a) It is faster to compute
b) It avoids integer overflow when low and high are large
c) It always finds the leftmost match
d) It works on unsorted arrays
Q4. What is the worst-case time complexity of quicksort?
a) O(n)
b) O(n log n)
c) O(n^2)
d) O(log n)
Q5. Which sorting algorithm guarantees O(n log n) time in every case but needs O(n) extra space for arrays?
a) Quicksort
b) Merge sort
c) Heapsort
d) Insertion sort
Q6. A sorting algorithm is called stable if:
a) It never crashes
b) It keeps equal elements in their original relative order
c) It always runs in O(n log n)
d) It uses no extra memory
Q7. Which of these sorting algorithms is NOT stable in its standard form?
a) Merge sort
b) Insertion sort
c) Bubble sort
d) Selection sort
Q8. Which algorithm runs in O(n) time on an array that is already sorted?
a) Selection sort
b) Insertion sort
c) Heapsort
d) Merge sort (standard)
Q9. How many swaps does selection sort make in the worst case on n elements?
a) O(1)
b) O(n)
c) O(n log n)
d) O(n^2)
Q10. Counting sort runs in O(n + k) time, where k is:
a) The number of swaps
b) The range of the input values
c) The number of passes
d) The recursion depth
Q11. What is the lower bound on the number of comparisons for any comparison-based sorting algorithm in the worst case?
a) Omega(n)
b) Omega(n log n)
c) Omega(n^2)
d) Omega(log n)
Q12. Which sorting algorithm is usually the fastest in practice for large in-memory arrays and is the basis of many library sort routines?
a) Bubble sort
b) Quicksort (or a hybrid based on it)
c) Selection sort
d) Counting sort for any data
Q13. Merge sort's running time follows which recurrence?
a) T(n) = T(n - 1) + O(1)
b) T(n) = 2T(n/2) + O(n)
c) T(n) = T(n/2) + O(1)
d) T(n) = 2T(n - 1) + O(1)
Q14. Binary search uses the recurrence T(n) = T(n/2) + O(1). What does it solve to?
a) O(1)
b) O(log n)
c) O(n)
d) O(n log n)
Q15. How many passes does bubble sort with an early-exit flag need for the array [1, 2, 3, 5, 4]?
a) 1
b) 2
c) 4
d) 5
Q16. To find the k-th smallest element of an unsorted array in average-case linear time, you would use:
a) Binary search
b) Quickselect
c) Bubble sort
d) Breadth-first search
Recommended MCQs
Comments
Post a Comment