Data Structures Arrays and Strings 2 — Questions and Answers
Question 1: What is the space complexity of storing a string of length n?
- O(1)
- O(log n)
- O(n) (Correct answer)
- O(n²)
Correct answer: O(n)
A string of length n requires O(n) space to store all its characters.
Question 2: Which algorithm finds the longest palindromic substring in O(n) time?
- Brute force
- Dynamic programming
- Manacher's algorithm (Correct answer)
- KMP algorithm
Correct answer: Manacher's algorithm
Manacher's algorithm finds the longest palindromic substring in O(n) time by cleverly reusing previously computed palindrome lengths.
Question 3: What is the time complexity of the naive string matching algorithm?
- O(n)
- O(m)
- O(n+m)
- O(n×m) (Correct answer)
Correct answer: O(n×m)
The naive algorithm compares the pattern at each position in the text, resulting in O(n×m) time where n is text length and m is pattern length.
Question 4: Which data structure is commonly used to implement an anagram-checking algorithm efficiently?
- Stack
- Queue
- Hash map or frequency array (Correct answer)
- Linked list
Correct answer: Hash map or frequency array
A hash map or fixed-size frequency array counts character occurrences in O(n) time, enabling O(1) anagram verification after counting.
Question 5: What does amortized O(1) mean for dynamic array append operations?
- Every append is exactly O(1)
- The average cost per append over many operations is O(1) (Correct answer)
- Append is O(1) only for small arrays
- The worst case is always O(1)
Correct answer: The average cost per append over many operations is O(1)
Although occasional resizing costs O(n), the total work spread across n appends averages to O(1) per operation using amortized analysis.
Question 6: Which string algorithm preprocesses a failure function to skip redundant comparisons?
- Rabin-Karp
- Boyer-Moore
- KMP (Knuth-Morris-Pratt) (Correct answer)
- Aho-Corasick
Correct answer: KMP (Knuth-Morris-Pratt)
KMP builds a partial match (failure) table that tells the algorithm how far to shift the pattern after a mismatch, avoiding redundant comparisons.
Data Structures Arrays and Strings 2
What is the space complexity of storing a string of length n?