Data Structures Arrays and Strings 2

Question 1

What is the space complexity of storing a string of length n?

Accepted Answer

O(n)

Answer

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?

Accepted Answer

Manacher's algorithm

Answer

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?

Accepted Answer

O(n×m)

Answer

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?

Accepted Answer

Hash map or frequency array

Answer

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?

Accepted Answer

The average cost per append over many operations is O(1)

Answer

Although occasional resizing costs O(n), the total work spread across n appends averages to O(1) per operation using amortized analysis.

Data Structures Practice Test