Strings

Question 1

What is a string?

Answer 1

A sequence of characters used to represent text.

Question 2

What is the time complexity of accessing a character in a string?

Answer 2

O(1), since strings are indexed.

Question 3

What is string concatenation?

Answer 3

Combining two or more strings into one.

Question 4

What is the time complexity of string concatenation?

Answer 4

O(n + m), where n and m are the lengths of the strings.

Question 5

What is a substring?

Answer 5

A contiguous sequence of characters within a string.

Question 6

What is string slicing?

Answer 6

Extracting a substring using index ranges.

Question 7

What is the time complexity of checking if a substring exists?

Answer 7

O(n) for brute force, O(n + m) using KMP.

Question 8

What is the KMP algorithm?

Answer 8

An efficient string matching algorithm with O(n + m) time complexity.

Question 9

What is the Rabin-Karp algorithm?

Answer 9

A string matching algorithm using hashing.

Question 10

What is the Boyer-Moore algorithm?

Answer 10

A fast string matching algorithm that skips sections of the text.

Question 11

What is the time complexity of reversing a string?

Answer 11

O(n), where n is the length of the string.

Question 12

What is a palindrome?

Answer 12

A string that reads the same forwards and backwards.

Question 13

How do you check if a string is a palindrome?

Answer 13

Compare characters from both ends moving inward.

Question 14

What is string immutability?

Answer 14

Once created, a string cannot be changed.

Question 15

Are strings mutable in Python?

Answer 15

No, strings are immutable.

Question 16

How do you compare two strings?

Answer 16

Lexicographically, character by character.

Question 17

What is a character array?

Answer 17

An array of characters, often used to manipulate strings.

Question 18

How do you find the longest common prefix?

Answer 18

Compare characters from the start of each string.

Question 19

What is the longest palindromic substring problem?

Answer 19

Finding the longest contiguous palindrome in a string.

Question 20

What is the sliding window technique?

Answer 20

A method for tracking a subset of characters in a string during iteration.

Question 21

What is the two-pointer technique?

Answer 21

Using two indices to compare or manipulate parts of a string.

Question 22

What is the time complexity of finding all substrings?

Answer 22

O(n^2)

Question 23

What is string hashing?

Answer 23

Converting a string into a numeric hash value.

Question 24

What is a rolling hash?

Answer 24

A hash function that updates efficiently when characters are added or removed.

Question 25

What is the use of a trie with strings?

Answer 25

Efficient prefix-based operations like autocomplete.

Question 26

How do you convert a string to lowercase or uppercase?

Answer 26

Use built-in functions like lower() or upper().

Question 27

What is the difference between isalpha and isdigit?

Answer 27

isalpha checks for letters; isdigit checks for numeric digits.

Question 28

What is string interpolation?

Answer 28

Inserting variables into a string using formatting.

Question 29

What is an anagram?

Answer 29

Two strings that use the same characters in a different order.

Question 30

How do you check if two strings are anagrams?

Answer 30

Sort both or use frequency maps.

Question 31

What is the time complexity of sorting a string?

Answer 31

O(n log n)

Question 32

What is the edit distance between two strings?

Answer 32

The minimum number of operations to convert one string into another.

Question 33

What is the Levenshtein distance?

Answer 33

A type of edit distance allowing insert, delete, and replace.

Question 34

What is dynamic programming used for in strings?

Answer 34

Solving problems like edit distance or longest common subsequence.

Question 35

What is a suffix array?

Answer 35

An array of all suffixes of a string sorted lexicographically.

Question 36

What is a longest common subsequence (LCS)?

Answer 36

The longest sequence that appears in both strings, not necessarily contiguously.

Question 37

What is string compression?

Answer 37

Reducing the size of a string by encoding repeating patterns.

Question 38

What is run-length encoding?

Answer 38

A basic compression method storing repeated characters as counts.

Question 39

What is pattern matching?

Answer 39

Finding occurrences of a pattern within a string.

Question 40

What is the time complexity of brute-force pattern matching?

Answer 40

O(n * m)

Question 41

What is a Unicode string?

Answer 41

A string that supports a large set of characters from many languages.

Question 42

What is ASCII?

Answer 42

A character encoding standard for English characters.

Question 43

What is UTF-8?

Answer 43

A variable-width character encoding capable of encoding all Unicode characters.

Question 44

What is string parsing?

Answer 44

Processing and analyzing the contents of a string.

Question 45

What is a delimiter in a string?

Answer 45

A character or sequence that separates parts of the string.

Question 46

What is the difference between split and join?

Answer 46

split divides a string; join combines list elements into a string.

Question 47

What are escape characters?

Answer 47

Special characters used to represent things like newlines or tabs.

Question 48

What is a null-terminated string?

Answer 48

A string that ends with a special null character '\0'.