Back to Subject

Unit 6: Searching techniques - Practice Quiz

CSE329 — Prelude To Competitive Coding 60 Questions
0 Correct 0 Wrong 60 Left
0/60

1 What is the time complexity of binary search on a sorted array of elements?

Iterative and recursive binary search Easy
A.
B.
C.
D.

2 Binary search requires the input array to be:

Iterative and recursive binary search Easy
A. Sorted
B. Filled with unique negative numbers
C. Unsorted
D. Reversed only

3 In binary search, how is the middle index typically computed to avoid integer overflow for indices and ?

Iterative and recursive binary search Easy
A.
B.
C.
D.

4 For an array of size , what is the optimal block (jump) size used in jump search?

Jump search Easy
A.
B.
C.
D.

5 Like binary search, jump search requires the array to be:

Jump search Easy
A. Containing only even numbers
B. Circular
C. Sorted
D. Empty

6 What does sublist search (list matching) determine?

Sublist search Easy
A. Whether a list is present as a contiguous part of another list
B. The largest element in a linked list
C. The sum of all elements in a list
D. Whether a list is sorted in ascending order and contains no duplicate values at all

7 For an array containing distinct numbers from to , which formula gives the missing number using the sum approach?

Find the missing number Easy
A.
B.
C.
D.

8 Which bitwise operation is commonly used to find a single missing number without risk of overflow?

Find the missing number Easy
A. AND
B. OR
C. NOT
D. XOR

9 What is the time complexity of searching an element in a sorted and rotated array using modified binary search?

Search an element in a sorted and rotated array Easy
A.
B.
C.
D.

10 In a sorted and rotated array, at each step of modified binary search we first check:

Search an element in a sorted and rotated array Easy
A. Which half is properly sorted
B. The average of the whole array
C. Whether the array is empty
D. The last element only

11 What does a substring search function return when the pattern is found in the text?

Recursive function to perform substring search Easy
A. The length of the text
B. The number of vowels in the pattern
C. The reversed pattern
D. The starting index of the match

12 In a naive recursive substring search, what happens at each recursive call?

Recursive function to perform substring search Easy
A. The entire text is deleted from memory and rebuilt each time before comparison
B. The function attempts to match the pattern starting at the next position
C. The pattern is doubled in length
D. The text is sorted alphabetically

13 Which data structure is most suitable for counting how many times each word appears in a string?

Find the K most frequent words from a string Easy
A. Queue
B. Stack
C. Hash map (dictionary)
D. Linked list

14 When two words have the same frequency, they are often ordered by:

Find the K most frequent words from a string Easy
A. Reverse insertion order always
B. Lexicographical (alphabetical) order
C. Number of vowels
D. String length only

15 For finding a pair with a given difference in a sorted array, which technique gives an efficient solution?

Find a pair with a given difference Easy
A. Matrix multiplication
B. Depth-first search
C. Two-pointer approach
D. Bubble sort

16 To find a pair with difference , if we fix an element , which value do we search for?

Find a pair with a given difference Easy
A.
B.
C.
D.

17 A peak element in an array is one that is:

Find a peak element Easy
A. Smaller than all other elements
B. Always at the last index
C. Greater than or equal to its neighbors
D. Equal to the array's average value

18 What is the time complexity of finding a peak element using binary search?

Find a peak element Easy
A.
B.
C.
D.

19 Which technique is commonly combined with prefix sums to efficiently handle subarray sum range problems?

Length of longest subarray having sum in given range l r Easy
A. Sliding window / two pointers
B. Graph coloring
C. Randomized quicksort
D. Recursion tree only

20 The naive brute-force method to print all subarrays with sum in a range has what time complexity?

Print all subarrays with sum in a given range Easy
A.
B.
C.
D.

21 In an iterative binary search, the mid index is computed as mid = low + (high - low) / 2 instead of mid = (low + high) / 2. What is the primary reason for this choice?

Iterative and recursive binary search Medium
A. To reduce the number of recursive calls made by the algorithm
B. To ensure the array remains sorted during the search
C. To make the search run in time instead of
D. To avoid integer overflow when low and high are large

22 A recursive binary search is called on a sorted array of elements. In the worst case, how many recursive calls (including the initial call) are made before termination?

Iterative and recursive binary search Medium
A.
B.
C.
D.

23 For a sorted array of elements, what block (jump) size minimizes the worst-case number of comparisons in jump search?

Jump search Medium
A.
B.
C.
D.

24 Jump search is being applied to an array of 100 sorted elements using the optimal block size. Approximately how many total comparisons does it need in the worst case?

Jump search Medium
A. About 20
B. About 50
C. About 100
D. About 7

25 Sublist search checks whether a linked list of nodes appears as a contiguous sublist within a larger linked list of nodes. What is its worst-case time complexity using the naive approach?

Sublist search Medium
A.
B.
C.
D.

26 An array contains distinct numbers taken from the range to . Using the sum formula, which expression correctly gives the missing number?

Find the missing number Medium
A.
B.
C.
D.

27 Which technique finds the single missing number in a range to without risking overflow from summation and works in time?

Find the missing number Medium
A. XOR all array elements with all numbers from to
B. Use a hash set that maps each number to its frequency, then scan the whole map to detect which key is absent from the sequence
C. Sort the array and binary search for the gap
D. Repeatedly divide the range and count elements in each half

28 In a sorted and rotated array with no duplicates, after computing mid, how do you decide which half to search in modified binary search?

Search an element in a sorted and rotated array Medium
A. Determine which half is sorted, then check if the target lies within that sorted half's range
B. Search both halves recursively and merge the results
C. Compare the target only with the first and last elements
D. Always discard the right half if the target is greater than arr[mid]

29 Consider the rotated array [6, 7, 8, 1, 2, 3, 4, 5]. When searching for 3, the first mid (index 3, value 1) is examined. Which half is identified as sorted?

Search an element in a sorted and rotated array Medium
A. Both halves are equally sorted
B. Neither half is sorted
C. The right half [1, 2, 3, 4, 5] is sorted
D. The left half [6, 7, 8, 1] is sorted

30 A recursive substring search checks if pattern P occurs in text T starting at each index. What is the base case that returns success?

Recursive function to perform substring search Medium
A. All characters of P have been matched (pattern index reaches its length)
B. The text index reaches the end of T
C. The lengths of P and T become equal
D. The first characters of P and T are equal

31 To find the most frequent words in a string, a min-heap of size is maintained over word frequencies. What is the overall time complexity if there are distinct words?

Find the K most frequent words from a string Medium
A.
B.
C.
D.

32 When two words have the same frequency in the "K most frequent words" problem, the standard tie-breaking rule ranks them by which criterion?

Find the K most frequent words from a string Medium
A. Reverse alphabetical order
B. Length of the word, longest first
C. Lexicographical (alphabetical) order
D. Order of first appearance in the string

33 Given a sorted array, the two-pointer method finds a pair with difference . When arr[j] - arr[i] > d, what action is taken?

Find a pair with a given difference Medium
A. Reset both pointers to the start
B. Increment j to increase the larger element
C. Increment i to increase the smaller element
D. Decrement j to reduce the difference

34 For an unsorted array, which approach finds a pair with a given difference in average time using extra space?

Find a pair with a given difference Medium
A. Use two nested loops to compare every pair of elements
B. Sort the array first, then apply binary search for each element
C. Build a balanced BST and traverse it in order to detect the pair
D. Store elements in a hash set, then for each x check if x + d exists

35 A peak element is one that is not smaller than its neighbors. Using binary search, if arr[mid] < arr[mid+1], where is a peak guaranteed to exist?

Find a peak element Medium
A. Only at the boundaries of the array
B. In the right half, indices mid+1 to high
C. Exactly at index mid
D. In the left half, indices low to mid

36 What is the time complexity of finding a peak element in an unsorted array using the binary search approach?

Find a peak element Medium
A.
B.
C.
D.

37 To find the longest subarray whose sum lies in , prefix sums are used. For a fixed right index with prefix sum , the subarray sum condition becomes which inequality on an earlier prefix ?

Length of longest subarray having sum in given range l r Medium
A. only
B.
C.
D.

38 For an array of all positive integers, why does the sliding-window technique work to enumerate subarrays with sum in a range?

Print all subarrays with sum in a given range Medium
A. Because the array must be sorted before sliding
B. Because the running sum increases monotonically as the window expands, so the window can be shrunk once the sum exceeds the range in a controlled manner that never requires re-examining discarded left elements
C. Because negative numbers cancel out the positives
D. Because prefix sums are unnecessary for positive arrays

39 Machines produce items at fixed rates. To find the minimum time to make items, binary search is applied on the answer (time ). What is checked for a candidate time ?

Minimum time required to produce m items Medium
A. Whether divides evenly among the machines
B. Whether the fastest machine alone can produce items
C. Whether the total items produced by all machines in time is at least
D. Whether each machine individually produces items in time

40 If the slowest machine takes max_rate minutes per item and there are machines producing items, what is a valid upper bound for the binary search on time?

Minimum time required to produce m items Medium
A.
B.
C.
D.

41 In a binary search implementation, using mid = (low + high) / 2 can cause a bug for very large arrays. Why does mid = low + (high - low) / 2 fix this?

Iterative and recursive binary search Hard
A. It prevents integer overflow when low + high exceeds the maximum integer value
B. It handles duplicate elements more correctly than the naive form
C. It guarantees the search always terminates in time
D. It reduces the number of comparisons per iteration by one

42 A recursive binary search is written with base case if (low > high) return -1. If instead a programmer writes if (low >= high) return -1, what is the consequence?

Iterative and recursive binary search Hard
A. An element at a position where low == high may be missed, causing false negatives
B. The recursion depth doubles, causing stack overflow
C. It converts the search into linear time complexity
D. It always returns the first element regardless of the target

43 For a sorted array of size , jump search uses a block size of . What block size minimizes the worst-case number of comparisons, and what is that optimal complexity?

Jump search Hard
A. , giving
B. , giving
C. , giving
D. , giving

44 Why is jump search generally preferred over binary search on systems where jumping backward is far costlier than jumping forward (e.g., certain tape/streaming media)?

Jump search Hard
A. Jump search only steps backward once during the final linear scan, minimizing costly reverse seeks
B. Jump search has a lower asymptotic complexity than binary search
C. Jump search requires the array to be unsorted, avoiding reordering
D. Jump search never needs to move backward at all

45 Sublist search checks whether a linked list S appears as a contiguous sublist of list L. What is the worst-case time complexity of the straightforward approach for lengths and ?

Sublist search Hard
A.
B.
C.
D.

46 During sublist search, a partial match fails after matching nodes of the pattern. In the naive algorithm, from which node of the main list does the next matching attempt begin?

Sublist search Hard
A. From the node where the mismatch occurred
B. From the head of the main list again
C. From nodes ahead of the current position
D. From the node immediately after the original start of the failed attempt

47 An array contains distinct numbers from the range with exactly one missing. Using XOR to find the missing number, what is XORed together?

Find the missing number Hard
A. XOR of all array elements XORed with XOR of all integers from to
B. XOR of all array indices XORed with the array sum
C. XOR of the first and last array elements only
D. XOR of all array elements XORed with

48 For finding one missing number in , the sum formula uses . Compared to the XOR method, what is the main practical drawback of the sum approach?

Find the missing number Hard
A. The sum can overflow for large , while XOR never overflows
B. The sum method has worse time complexity than XOR
C. The sum method fails when the array is sorted
D. The sum method requires extra space

49 In a sorted rotated array with no duplicates, at each step of the modified binary search you compute mid. How do you decide which half is normally sorted?

Search an element in a sorted and rotated array Hard
A. If arr[mid] <= arr[high], the left half is sorted; otherwise the right half
B. If arr[low] > arr[high], both halves are sorted
C. If arr[low] <= arr[mid], the left half is sorted; otherwise the right half is sorted
D. If arr[mid] == arr[low], neither half is sorted

50 When a sorted rotated array contains duplicates, why can the worst-case time complexity of the search degrade to ?

Search an element in a sorted and rotated array Hard
A. Duplicates double the recursion depth of the search
B. Duplicates make integer overflow in the midpoint unavoidable
C. When arr[low] == arr[mid] == arr[high], neither half can be determined as sorted, forcing a linear shrink
D. Duplicates cause the array to become unsorted, requiring a full sort first

51 A recursive substring search matches pattern P inside text T. The base cases are: pattern exhausted (return true) and text exhausted with pattern remaining (return false). What recursive relation correctly continues a match?

Recursive function to perform substring search Hard
A. If P[0] == T[0], return true; else recurse on P[1:] and T
B. If P[0] == T[0], recurse on P[1:] and T[1:]; else recurse on the same P with T[1:]
C. Always recurse on both P[1:] and T[1:] regardless of match
D. If P[0] == T[0], recurse on P and T[1:]; else return false immediately

52 For a recursive naive substring search over text of length and pattern of length , what is the worst-case time complexity, and which inputs trigger it?

Recursive function to perform substring search Hard
A. , e.g. text "aaaa...a" with pattern "aaa...b"
B. , when text is shorter than the pattern
C. , always, due to recursion memoization
D. , when the pattern is a palindrome

53 To find the most frequent words (ties broken by lexicographic order) from a string with distinct words, using a min-heap of size , what is the time complexity?

Find the K most frequent words from a string Hard
A.
B.
C.
D.

54 When using a min-heap to keep the top- frequent words, the comparator must order words so the least desirable candidate sits at the root for eviction. For equal frequencies, how should the comparator rank words?

Find the K most frequent words from a string Hard
A. Words that are lexicographically larger should be treated as smaller so they are evicted first
B. Ties should be broken by insertion order into the heap
C. Words that are lexicographically smaller should be treated as smaller so they are evicted first
D. Ties should be broken by word length, shorter first

55 Given a sorted array, to find a pair with difference using two pointers i and j, how are the pointers advanced?

Find a pair with a given difference Hard
A. Move both pointers inward from the two ends until they meet
B. If arr[j] - arr[i] < d increment i; if > d increment j; if == d report success
C. Increment j only, checking arr[j] - arr[0] each time
D. If arr[j] - arr[i] < d increment j; if > d increment i; if == d (and i != j) report success

56 For an unsorted array, a hash-set method finds a pair with difference by checking, for each element , whether or was seen. What subtle case must be handled when ?

Find a pair with a given difference Hard
A. The set must be sorted before insertion
B. The value overflows and must be skipped
C. A number must appear at least twice; a single occurrence must not falsely report a pair
D. Only even numbers can form a valid zero-difference pair

57 In an array where arr[i] != arr[i+1] for all i, a peak is an element not smaller than its neighbors. Binary search finds a peak in . Which decision rule is correct at index mid?

Find a peak element Hard
A. Always search the half with the smaller boundary value
B. If arr[mid] < arr[mid+1], a peak must exist to the right; else search left including mid
C. If arr[mid] < arr[mid+1], a peak must exist to the left; else search right
D. If arr[mid] > arr[mid-1], always return mid as the peak

58 Why does the peak-finding binary search always guarantee a peak exists in the chosen half, even without global sorting?

Find a peak element Hard
A. Moving toward a larger neighbor guarantees a boundary that eventually turns down, forcing a peak in that direction
B. Because every array of distinct elements has exactly one peak
C. Because the midpoint is always a local minimum
D. Because the array is implicitly sorted after each halving step

59 For an array with negative numbers, why does the simple sliding-window (two-pointer) technique fail to find the longest subarray with sum in range ?

Length of longest subarray having sum in given range l r Hard
A. Sliding window only works for fixed-length subarrays
B. The array must be sorted before applying sliding window
C. Prefix sums are not monotonic, so expanding or shrinking the window does not move the sum predictably
D. Negative numbers make all subarray sums negative

60 Given machines where machine produces one item every minutes, binary search on time finds the minimum to make items. What monotonic predicate is searched?

Minimum time required to produce m items Hard
A. , monotonic in
B. , true only at the largest
C. exactly, for a unique
D. , which is false for small and true for large
Previous MCQ
Unit 5