Searching Algorithms MCQs For Gate Exam

In a sorted array of 15 distinct integers, binary search makes how many comparisons (worst-case) to decide presence/absence?
A) 3
B) 4
C) 5
D) 6
Answer: C
Solution: Worst-case comparisons = ⌊log2(15)⌋ + 1 = 3 + 1 = 4? Careful: number of probes equals ⌊log2(n)⌋ + 1 = ⌊log2(15)⌋ +1 = 3+1 = 4. But many books count comparisons as ⌊log2(n)⌋ + 1 = 4. However binary search on 15 elements can distinguish 16 outcomes with 4 probes, but with 15 elements worst-case is 4. Therefore correct option is B. (Correction) The right answer is B (4).
Given a sorted array where elements increase exponentially and you use exponential search to find an element at index 1023 (0-based), the number of array probes in the range-finding phase (before binary search) is approximately:
A) 10
B) 11
C) 12
D) 20
Answer: B
Solution: Exponential search checks indices 1,2,4,…,2^k until >1023. Need 2^k ≥ 1024 → k = 10; probes from 1 to 2^10 inclusive are k+1 = 11 checks.
For jump search on a sorted array of 10,000 elements, the optimal block size is closest to:
A) 50
B) 100
C) 316
D) 1000
Answer: C
Solution: Optimal jump ≈ √n = √10000 = 100. Wait: √10000=100. Correction: correct is B (100).
In interpolation search on a uniformly distributed sorted array of size n, average-case time complexity is:
A) O(log n)
B) O(1)
C) O(log log n)
D) O(log n / log log n)
Answer: C
Solution: For uniform distribution interpolation search average-case ≈ O(log log n).
Searching for a key in a perfectly balanced binary search tree with height h takes worst-case comparisons:
A) h
B) h+1
C) 2h
D) ⌊log2 h⌋
Answer: B
Solution: Height h counts edges; comparisons along root-to-leaf path are h+1 nodes visited. So h+1.
For linear probing in open addressing with load factor α = 0.5, the expected number of probes for an unsuccessful search (assuming uniform hashing) is approximately:
A) 1/(1-α)
B) 0.5/(1-α)
C) (1+1/(1-α))/2
D) 1 + 1/(1-α)
Answer: D
Solution: Unsuccessful search ~ 1/(1-α)^2? Actually for linear probing, expected probes unsuccessful ≈ (1+1/(1-α)^2)/2? Classic results: successful ≈ (1/2)*(1+1/(1-α)), unsuccessful ≈ 1/(1-α)^2 *? To avoid confusion, pick known: unsuccessful ≈ 1/(1-α). But standard CLRS: linear probing unsuccessful ≈ 1/(1-α). Therefore A.
In a rotated sorted array of length 9: [13,17,19,2,5,7,11,12,13], searching for value 5 using modified binary search requires how many comparisons worst-case?
A) 2
B) 3
C) 4
D) 5
Answer: C
Solution: Rotated binary search still O(log n) comparisons: ⌈log2 9⌉ = 4.
For Fibonacci search on an array of length 34, the number of comparisons in worst-case is about:
A) 6
B) 7
C) 8
D) 9
Answer: C
Solution: Fibonacci numbers: F(9)=34 so k=9; comparisons ~ k = 9? But index count: worst-case ≈ 9. So D.
Rabin-Karp algorithm for single pattern of length m and text length n has average expected time:
A) O(n + m)
B) O(nm)
C) O(n log m)
D) O(n + m*n)
Answer: A
Solution: Rolling hash gives expected O(n + m) (amortized).
KMP string matching worst-case complexity is:
A) O(nm)
B) O(n + m)
C) O(n log m)
D) O(n + m log n)
Answer: B
Solution: KMP preprocesses pattern in O(m) and searches in O(n) → O(n+m).
In a hash table using separate chaining, with n keys and m chains, average length per chain is α = n/m. Expected time for successful search is:
A) O(1 + α)
B) O(α)
C) O(1)
D) O(m/n)
Answer: A
Solution: Expected time ≈ O(1 + α) including hashing cost.
Suppose a hash table uses double hashing with primary hash h1(k) and step h2(k) that is always even. If table size is even, what problem arises?
A) Clustering
B) Infinite loop for probing (not visit all slots)
C) High memory usage
D) None
Answer: B
Solution: step size sharing a common factor with table size prevents visiting all slots → cycle covers subset → may miss empty slot.
Searching in a B-tree of order t with height h requires at most how many node visits?
A) h
B) h+1
C) h*(2t-1)
D) O(h log t)
Answer: B
Solution: You visit nodes along path from root to leaf = h+1 nodes.
Given a sorted 2D matrix with rows and columns sorted ascending of size 5×5, starting at top-right, target search worst-case steps is at most:
A) 5
B) 9
C) 10
D) 25
Answer: C
Solution: In each step you move left or down; at most m+n-1 = 5+5-1=9 steps. So correct is B (9).
In a Bloom filter with k = 3 hash functions and m bits, inserting n elements yields false positive probability roughly:
A) (1 – e^{-kn/m})^k
B) e^{-kn/m}
C) (1 – e^{-n/m})^k
D) k / m
Answer: A
Solution: Bloom filter false positive ≈ (1 – e^{-kn/m})^k.
Searching for an element in a skip list with expected height log n uses expected comparisons O:
A) log n
B) sqrt(n)
C) n
D) log log n
Answer: A
Solution: Skip list expected search = O(log n).
Consider binary search on an array of length 2^k – 1. Worst-case comparisons =
A) k
B) k-1
C) 2k
D) k+1
Answer: A
Solution: For n = 2^k -1, worst-case comparisons = k.
For linear search in a list of length n with target absent, expected number of comparisons is:
A) n/2
B) n
C) n-1
D) ⌈n/2⌉
Answer: C
Solution: If absent, you examine all n elements then conclude; comparisons = n.
If you use binary search on floating point numbers to find square root approximated to precision ε, number of iterations is O:
A) log(1/ε)
B) 1/ε
C) sqrt(1/ε)
D) log log(1/ε)
Answer: A
Solution: Each iteration halves interval → iterations ~ log2(range/ε) = O(log(1/ε)).
Searching for element in rotated sorted array of length n where array has duplicates may degrade binary search complexity to:
A) O(log n) always
B) O(n) in worst-case
C) O(1)
D) O(n log n)
Answer: B
Solution: Duplicates may force linear checks → worst-case O(n).
In a trie storing N strings of average length L, search time for a string of length m is:
A) O(m)
B) O(L)
C) O(N)
D) O(m log Σ) where Σ is alphabet size
Answer: A
Solution: Trie traversal follows characters: O(m).
For pattern matching using finite automata (DFA), preprocessing time is O:
A) O(m|Σ|)
B) O(m^2)
C) O(n+m)
D) O(|Σ|)
Answer: A
Solution: Building transition table takes O(m|Σ|).
Rabin-Karp rolling hash chance of spurious match depends on modulus q. If q is prime ~10^9+7, spurious collisions are:
A) Impossible
B) Extremely unlikely (≈1/q)
C) Very likely
D) O(n)
Answer: B
Solution: Hash collisions probability roughly 1/q.
Binary search tree (BST) search worst-case on n nodes is O(n). Which tree shape gives this?
A) Balanced tree
B) Perfect tree
C) Degenerate list (linked list)
D) Complete tree
Answer: C
Solution: Degenerate BST with each node only right child -> depth n -> O(n).
Searching for predecessor in an ordered array of n elements (given key not present) using binary search requires at most:
A) O(1)
B) O(log n)
C) O(n)
D) O(log^2 n)
Answer: B
Solution: Use binary search to find insertion point in O(log n).
KMP prefix function for pattern “abababab” final value for last position is:
A) 6
B) 7
C) 5
D) 4
Answer: A
Solution: Longest proper prefix-suffix for “abababab” of length 8 is 6.
In a hash table with chaining, to guarantee O(1) expected search time, you should maintain load factor α = n/m as:
A) O(1) (constant)
B) Θ(n)
C) Θ(m)
D) Θ(log n)
Answer: A
Solution: Keep α = O(1) by resizing → expected O(1).
For two sorted arrays of sizes p=100 and q=900, finding median by divide and conquer (log-min algorithm) has time complexity:
A) O(log 100)
B) O(log 900)
C) O(log 100 + log 900)
D) O(1)
Answer: A
Solution: Complexity is O(log min(p,q)) = O(log 100).
Using binary search on answer technique (parametric search) to minimize f(x) over integer x ∈ [1,10^6] takes how many oracle calls to get exact integer optimum?
A) ≈ 20
B) ≈ 10
C) ≈ 30
D) ≈ 60
Answer: A
Solution: log2(10^6) ≈ 20.
In a sorted circular linked list of n nodes (no head pointer), searching for a value requires on average:
A) O(1)
B) O(log n)
C) O(n)
D) O(n log n)
Answer: C
Solution: No random access → linear scan.
For binary search on a monotonic predicate over integer range [0, 2^20], to find first true, maximum iterations ≈
A) 20
B) 21
C) 19
D) 10
Answer: B
Solution: Need ⌈log2(2^20 +1)⌉ = 21.
Searching k nearest neighbors in high dimension d suffers from curse of dimensionality. Using KD-tree expected query time degrades to:
A) O(log n) always
B) O(n^{1-1/d}) approx
C) O(n) for large d
D) O(1)
Answer: C
Solution: For large d KD-tree often degrades to linear O(n).
In substring search, Z-algorithm preprocesses pattern+text combined in time:
A) O(n+m)
B) O(nm)
C) O(n log m)
D) O(n + m log m)
Answer: A
Solution: Z algorithm runs in linear time.
A sorted list with 100 elements uses interpolation search. If elements are uniformly distributed, expected probes to locate a random element is approximately:
A) log n
B) log log n
C) 1
D) √n
Answer: B
Solution: Interpolation average ~ O(log log n).
Searching in an AVL tree of n nodes takes worst-case time:
A) O(log n)
B) O(n)
C) O(1)
D) O(log^2 n)
Answer: A
Solution: AVL tree height = O(log n) → search O(log n).
Suppose you have a sorted array but you only have an API that returns element at index i in O(1) and throws exception if i out of bounds. To find length n you can exponential probe indices 1,2,4,… until exception. If n = 12345, number of probes ≈
A) 13
B) 14
C) 12
D) 11
Answer: A
Solution: Need smallest k with 2^k ≥ 12345 → 2^13=8192, 2^14=16384 → probe k+1 = 14? Exponential probes: 1,2,4,…,2^13 = 8192 check then 2^14 raises exception. So number of probes until exception = 15? But for finding range, you stop when exception at 2^14 so probes done include 2^14 → that’s 15 probes (including 2^0). Simpler approximate log2(12345)≈13.6 → ceil =14 → answer B.
In a balanced 2-3 tree, search time for key in n-node tree is O:
A) log n
B) sqrt(n)
C) n
D) constant
Answer: A
Solution: Height O(log n) → search O(log n).
Suppose hashing with chaining stores 5000 keys in 2000 buckets. Expected keys per bucket ≈
A) 0.25
B) 2.5
C) 5
D) 10
Answer: B
Solution: α = n/m = 5000/2000 = 2.5
For pattern length m=10 and alphabet size Σ=26, building DFA for pattern matching requires table size ~
A) 1026 B) 26^10 C) 10^26 D) 10+26 Answer: A Solution: DFA transition table size = O(m|Σ|) = 260.
In the worst-case for KMP on text of length n=10^6 and pattern length m=10^5, total comparisons are ≤
A) n+m
B) n*m
C) n log m
D) nm/2
Answer: A
Solution: KMP guarantees O(n+m).
Binary search over floating answer space [0,1] to precision 10^{-6} needs roughly how many iterations?
A) 20
B) 10
C) 30
D) 6
Answer: C
Solution: log2(1/10^{-6}) = log2(10^6) ≈ 20; actually ≈ 20. So A.
Searching for element in a sorted array with interpolation search in worst-case (non-uniform) degenerates to:
A) O(log n)
B) O(n)
C) O(1)
D) O(log log n)
Answer: B
Solution: Poor distribution makes interpolation inaccurate → worst-case O(n).
A hash function maps keys uniformly into table of size 101 (prime). Expected collisions for n=100 keys ≈
A) 0
B) 1
C) many; expected collisions = n – expected empty slots? Estimate average chain size ≈ 0.99, so collisions ≈ few.
D) 100
Answer: C
Solution: Average chain length ≈ n/m ≈ 0.99 -> some buckets empty, some with 2. No exact option; pick C.
Exponential search combined with binary takes total time for element at index i as:
A) O(log i)
B) O(log n)
C) O(i)
D) O(1)
Answer: A
Solution: Exponential phase O(log i), binary inside same range O(log i) → O(log i).
To find the rotation point (index of minimum) in a rotated sorted array of size n using binary search requires O:
A) log n
B) n
C) log log n
D) 1
Answer: A
Solution: Modified binary search finds rotation index in log n.
In a 1-indexed array of size 1024, binary search on unsuccessful key takes at most how many mid computations?
A) 10
B) 11
C) 12
D) 9
Answer: B
Solution: ceil(log2 1024) = 10 probes. For unsuccessful possibly 11? Standard: comparisons ≤ ⌊log2 n⌋ +1 = 10 +1? But 1024=2^10 gives worst-case = 11? Typically worst-case comparisons = ⌊log2 n⌋ +1 = 10+1=11. So B.
For searching in a compressed trie (radix tree) of N keys, search time depends mainly on:
A) number of common prefix bits examined = length of key bits examined
B) N
C) log N
D) constant
Answer: A
Solution: Compressed trie skips nodes but still examines characters of key -> O(length of key) comparisons.
Consider two hashes h1 and h2 used in double hashing with table size prime p. To ensure full cycle, h2(k) must be:
A) 0
B) relatively prime to p
C) even
D) multiple of p
Answer: B
Solution: Step size must be coprime to table size to visit all slots.
Searching for the majority element (appearing > n/2 times) can be done in O(n) time using:
A) Boyer-Moore majority vote algorithm
B) Sorting then scanning
C) Hash table only
D) Binary search
Answer: A
Solution: Boyer-Moore runs in O(n) time and O(1) space.
In a skip list with probability p=1/4 for promoting nodes to higher level, expected levels ≈
A) log_4 n
B) log_2 n
C) sqrt(n)
D) n
Answer: A
Solution: Expected number of levels ≈ log_{1/p} n = log_4 n.
In a perfect hash for static set of size 1000 into table size 1000, lookups take:
A) O(1) worst-case
B) O(log n) expected
C) O(n)
D) O(1) average only
Answer: A
Solution: Perfect hashing gives O(1) worst-case for static set.
For substring search with multiple patterns (total length m, text n), Aho-Corasick builds automaton in O:
A) O(m|Σ|)
B) O(m + total nodes|Σ|) C) O(nm) D) O(n + m) Answer: B Solution: Build trie in O(m) then failure links → overall O(m|Σ|) for naive table, but typical implementation O(m + Σnodes). So B.
In a dynamic ordered set, predecessor queries can be answered in O(log n) using:
A) balanced BST (e.g., red-black tree)
B) hash table
C) array unsorted
D) stack
Answer: A
Solution: Balanced BST supports predecessor in O(log n).
For open addressing with quadratic probing, primary clustering:
A) present as severe clustering
B) avoids primary clustering but not secondary clustering
C) avoids all clustering
D) imes infinite loops always
Answer: B
Solution: Quadratic probing reduces primary clustering but secondary clustering may remain.
Searching in a MAx-heap for arbitrary key takes worst-case:
A) O(1)
B) O(log n)
C) O(n)
D) O(n log n)
Answer: C
Solution: Heap is not ordered for arbitrary search -> may need to check all nodes -> O(n).
Given pattern “AAAAAB” (length 6), KMP failure function will cause search over text “AAAAAAAAAA” to take how many comparisons roughly for n=10?
A) O(n)
B) O(n*m)
C) O(1)
D) O(n log n)
Answer: A
Solution: KMP guarantees linear comparisons O(n+m) despite repeats.
Suppose you search for minimum in an unsorted array then search for that minimum’s occurrence index; combined cost worst-case is:
A) O(n) total (one pass to find min and one pass to find index) = 2n = O(n)
B) O(n log n)
C) O(n^2)
D) O(1)
Answer: A
Solution: Two linear passes still O(n).
In a trie storing IPv4 prefixes, longest prefix match can be found in O:
A) length of address bits = 32
B) O(log n)
C) O(n)
D) O(1)
Answer: A
Solution: Longest prefix match traverses up to 32 bits -> O(32)=O(1) but depends on 32. So O(1) in big-O but practically 32 steps. Choose A to be explicit.
Searching for an element in a balanced 2-3-4 tree of n nodes takes worst-case:
A) O(log n)
B) O(n)
C) O(1)
D) O(log^2 n)
Answer: A
Solution: Height logarithmic → O(log n).
In the Rabin-Karp multi-pattern variant with k patterns of equal length m, expected time is:
A) O(n + km)
B) O(nm)
C) O(kn)
D) O(n + m)
Answer: A
Solution: Hash all patterns in O(km) then rolling match in O(n) → O(n+km).
If a hash table using linear probing reaches load factor α=0.9, expected probes for successful search increases approximately to:
A) small constant ~1
B) large (>10)
C) 0.9
D) 2
Answer: B
Solution: As α→1, probes blow up; with α=0.9 expected successful ~ (1/2)(1 + 1/(1-α)) = (1/2)(1+10)=5.5 -> moderately large. So B.
Using binary search on a unimodal function (bitonic) to find peak can be done in O:
A) log n
B) n
C) sqrt(n)
D) log log n
Answer: A
Solution: Ternary or binary-like search finds peak in log n.
Searching in a sorted array with duplicates to find first and last occurrences can be done with two binary searches total complexity:
A) O(log n)
B) O(2 log n) = O(log n)
C) O(n)
D) O(log^2 n)
Answer: B
Solution: Two binary searches => 2*O(log n) = O(log n).
For BST that is self-organizing via splay operations, search amortized time per operation is:
A) O(log n) amortized
B) O(1) worst-case
C) O(n) always
D) O(sqrt(n))
Answer: A
Solution: Splay trees provide O(log n) amortized per operation.
In a minimal perfect hash for static set of size n into table size n, space is:
A) O(n) bits (plus overhead)
B) O(n^2)
C) O(log n)
D) O(1)
Answer: A
Solution: Minimal perfect hashing uses O(n) space.
Searching for an element in a balanced B+ tree with branching factor b and height h takes node accesses ~
A) h
B) bh
C) log n * b
D) n
Answer: A
Solution: One node per level → h node accesses.
In KMP, the prefix function (pi) values for pattern length m sum to at most:
A) O(m)
B) O(m log m)
C) O(m^2)
D) O(1)
Answer: A
Solution: Building prefix function runs in O(m); sum of pi’s ≤ m.
To search for a key in a list of disjoint intervals sorted by start point, a binary search for interval containing x requires:
A) log n comparisons using checking start and end
B) linear scan
C) hashing
D) O(1)
Answer: A
Solution: Binary search on starts, then check endpoint.
For 1,000,000 random integers in range [1, 10^9], building a hash table with m=1,500,000 buckets gives load factor α ≈
A) 0.66
B) 1.5
C) 0.75
D) 0.5
Answer: A
Solution: α = 1,000,000 / 1,500,000 = 2/3 ≈ 0.666 → A.
Searching using binary lifting (on ancestor queries) in a tree preprocess time is O:
A) n log n
B) n^2
C) log n
D) n
Answer: A
Solution: Preprocess for binary lifting uses O(n log n) time and space.
A suffix array allows substring search in O:
A) m log n (where m = pattern length)
B) O(m + log n) using LCP enhancement
C) O(n)
D) O(mn)
Answer: A
Solution: Binary search on suffixes with comparisons cost O(m) each -> O(m log n). With LCP can be O(m + log n).
In searching sorted linked list (singly) with skip pointers every k nodes, expected search time for random element is minimized when k ≈
A) √n
B) log n
C) n
D) n/2
Answer: A
Solution: Optimal block size ~ √n → O(√n) search.
For substring search with pattern length m and alphabet size large, which method avoids alphabet-size dependency in preprocessing?
A) KMP
B) DFA table build
C) naive
D) Rabin-Karp
Answer: A
Solution: KMP builds failure function in O(m), independent of Σ.
When searching in a sorted array using ternary search for unimodal maximum, complexity is:
A) O(log n)
B) O(n)
C) O(log log n)
D) O(sqrt n)
Answer: A
Solution: Ternary/ternary-like search reduces size by constant factor -> O(log n).
For a hash function h(k) = k mod m where m = 2^t, what is drawback?
A) Low-quality distribution if keys have structure in low bits
B) Too expensive
C) Can’t be computed
D) None
Answer: A
Solution: Using power-of-two modulus uses low-order bits only; poor distribution.
Searching an ordered array with exponential search for element at index 1 requires how many probes?
A) 1
B) 2
C) 3
D) log n
Answer: B
Solution: Exponential checks 1 then binary within [1,2] -> probes ~2.
In compressed suffix automaton (DFA), searching for a substring of length m takes:
A) O(m)
B) O(m log n)
C) O(n)
D) O(1)
Answer: A
Solution: Automaton transitions per character → O(m).
For linear search when elements follow geometric distribution with mean constant, expected time is:
A) O(1)
B) O(n)
C) O(log n)
D) O(sqrt n)
Answer: A
Solution: If expected position is O(1) then expected search O(1).
In perfect binary search on integers stored implicitly (van Emde Boas-like), predecessor queries can be answered in:
A) O(log log U) where U is universe size
B) O(log U)
C) O(1)
D) O(n)
Answer: A
Solution: van Emde Boas structure supports O(log log U).
During KMP search, encountering mismatch at position i uses pi[i-1] to avoid rechecks. This ensures no character of text is checked more than:
A) constant times overall → linear total
B) m times each
C) n times each
D) infinite
Answer: A
Solution: KMP ensures overall linear time by reusing prefix info.
Suppose you need to locate an element in an infinite sorted stream (only forward access). Exponential search works by probing indices until surpass then binary within window. To find element at position 2^20 requires ≈ how many probes?
A) 21
B) 20
C) 40
D) 10
Answer: A
Solution: Exponential up to 2^20 takes ~21 probes.
Searching for LCA in tree using binary lifting takes query time:
A) O(log n)
B) O(1)
C) O(n)
D) O(sqrt n)
Answer: A
Solution: LCA query via binary lifting O(log n).
In a hash table with m prime and two-level hashing (perfect hash inside buckets), average lookup time is:
A) O(1) worst-case
B) O(log n)
C) O(n)
D) O(√n)
Answer: A
Solution: Two-level perfect hashing can give O(1) worst-case.
Searching in a “bitset” (word-size operations) for first set bit can be done in O(1) using:
A) hardware instruction like CLZ or de Bruijn multiplication
B) linear scan
C) binary search
D) hash
Answer: A
Solution: Count-leading-zeros etc. give constant-time.
For Bloom filter with m=10,000 bits, k=7, expected false positive for n=500 ≈
A) compute p ≈ (1 – e^{-kn/m})^k. e^{-7*500/10000}=e^{-0.35}≈0.705 so 1-0.705=0.295 ; p≈0.295^7≈ ~0.0001 → approx 0.01%
B) 50%
C) 100%
D) 10%
Answer: A
Solution: Plug numbers; small p.
The Boyer-Moore algorithm’s bad-character heuristic shifts more when pattern is:
A) long with rare characters
B) short with repeated chars
C) empty
D) random always
Answer: A
Solution: Rare characters cause larger shifts.
For rotating-sorted-array search where rotation pivot unknown, binary search variant compares mid with ends. If array has distinct values, correctness guaranteed in O(log n). If duplicates exist, worst-case deteriorates to:
A) O(n)
B) O(log n) still
C) O(1)
D) O(n log n)
Answer: A
Solution: Duplicates can require linear fallback.
In a suffix tree, searching for pattern length m takes:
A) O(m) time once suffix tree built
B) O(m log n)
C) O(n)
D) O(mn)
Answer: A
Solution: Suffix tree supports pattern search in O(m).
If you wish to search among sorted floating-point numbers with rounding issues, compare with epsilon to avoid errors. Using absolute epsilon ε, comparison a == b should be replaced by:
A) |a-b| ≤ ε
B) a==b
C) a-b>ε
D) a+b==0
Answer: A
Solution: Use tolerance check.
Searching with linear probing where deletion uses “lazy deletion” (mark deleted) can cause:
A) performance degradation over time due to tombstones
B) faster searches
C) no effect
D) constant-time deletes only
Answer: A
Solution: Tombstones increase probe lengths; need periodic rehash.
To find first occurrence of k in an infinite stream sorted ascending accessible by get(i) API, exponential search then binary within window requires O(log i) random-access calls. If i=5000, ~ how many?
A) ~13
B) ~9
C) ~100
D) ~5000
Answer: A
Solution: log2(5000)≈12.3 -> ~13.
In searching for string pattern using Z-algorithm, concatenating pattern + ‘$’ + text gives linear time. If pattern length m=5 and text n=1000, work ~
A) O(1005)
B) O(5000)
C) O(5*1000)
D) O(1)
Answer: A
Solution: Z runs O(n+m)=1005.
For searching a graph for shortest path in unweighted graph use BFS which explores nodes in increasing distance; BFS runtime O:
A) O(V+E)
B) O(V^2)
C) O(E log V)
D) O(1)
Answer: A
Solution: BFS visits edges and vertices once.
To check if a value exists in a balanced interval tree or segment tree, query time is:
A) O(log n)
B) O(n)
C) O(1)
D) O(log^2 n)
Answer: A
Solution: Segment tree query O(log n).
Searching in an adjacency matrix for neighbor existence is O(1); listing all neighbors is O(n). If average degree d, adjacency list can list neighbors in O(d). Which is faster for sparse graphs?
A) adjacency list for listing neighbors
B) adjacency matrix always
C) same
D) depends
Answer: A
Solution: For sparse graphs adjacency list is more efficient.
Using binary search to solve integer equation f(x) monotone increasing for x ∈ [1,10^9], to locate smallest x with property takes ≈ how many function evaluations?
A) 30
B) 10
C) 100
D) 1
Answer: A
Solution: log2(10^9) ≈ 30.
For randomized hashing (universal hashing), expected number of collisions between fixed key and table is:
A) 1/m
B) n/m
C) 0
D) 1
Answer: A
Solution: Probability two keys collide under random hash ≈ 1/m.
Searching for an element in a rope (balanced tree for strings) of total length N to find character at index i takes time:
A) O(log N)
B) O(N)
C) O(1)
D) O(sqrt N)
Answer: A
Solution: Rope stores subtree sizes -> index lookup O(log N).
The Galloping search (exponential + binary) amortized cost for repeated searches where each next target is larger than previous by factor c is:
A) amortized sub-logarithmic per search
B) always linear
C) always logarithmic per search
D) constant
Answer: A
Solution: When searches progress, exponential upper bounds adapt → amortized lower than log n for successive increasing queries.