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

O(1)

Answer

O(log n)

Answer

O(n²)

Question 2

Which algorithm finds the longest palindromic substring in O(n) time?

Accepted Answer

Manacher's algorithm

Answer

Brute force

Answer

Dynamic programming

Answer

KMP algorithm

Question 3

What is the time complexity of the naive string matching algorithm?

Accepted Answer

O(n×m)

Answer

O(n)

Answer

O(m)

Answer

O(n+m)

Question 4

Which data structure is commonly used to implement an anagram-checking algorithm efficiently?

Accepted Answer

Hash map or frequency array

Answer

Stack

Answer

Queue

Answer

Linked list

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

Every append is exactly O(1)

Answer

Append is O(1) only for small arrays

Answer

The worst case is always O(1)

Question 6

Which string algorithm preprocesses a failure function to skip redundant comparisons?

Accepted Answer

KMP (Knuth-Morris-Pratt)

Answer

Rabin-Karp

Answer

Boyer-Moore

Answer

Aho-Corasick