Top 25 Strings Interview Questions And Answers

Question 1

What is String in Data Structures?

Accepted Answer

A **string** is generally considered as a **data type** and is often implemented as an **array data structure** of bytes (or words) that stores a sequence of elements, typically characters, using some character encoding. String may also denote more general arrays or other sequence (or list) data types and structures.

Question 2

What is the difference between Strings vs. Char arrays?

Accepted Answer

**Char arrays**: 
* Static-sized
* Fast access
* Few built-in methods to manipulate strings
* A char array doesn’t define a data type

**Strings**:
* Slower access
* Define a data type
* Dynamic allocation
* More built-in functions to support string manipulations

Question 3

What is strings mutability and immutability?

Accepted Answer

Strings can either be **mutable** or **immutable**. 
* When a string is **immutable** it means that it's fixed allocated. So your string it's unique and can't be modified. If you change it, a copy of that string is created and the original string is deallocated instead. 
* When a string is **mutable** it means that it's dynamically allocated, so your string can be modified.

Question 4

Reverse a String using Stack

Accepted Answer

The followings are the steps to reversing a String using Stack:

1.  `String` to `char[]`.
2.  Create a `Stack`.
3.  **Push** all characters, one by one.
4.  Then **Pop** all characters, one by one and put into the `char[]`.
5.  Finally, convert to the `String`.

Question 5

What is a null-terminated String?

Accepted Answer

A "string" is really just an array of `char`s; a null-terminated string is one where a null character `'\0'` marks the end of the string (not necessarily the end of the array). All strings in code (delimited by double quotes `""`) are automatically null-terminated by the compiler.

So for example, `"hi"` is the same as `{'h', 'i', '\0'}`.

Null-terminated strings are often a _drain on performance_, for the obvious reason that the time taken to discover the length depends on the length. The usual solution is to do both - keep the length and maintain the null terminator. It's not much extra work and means that you are always ready to pass the string to any function.

Question 6

Reverse the ordering of words in a String

Accepted Answer

Reverse the entire string, then reverse the letters of each individual word.

After the first pass the string will be

s1 = "Z Y X si eman yM"

and after the second pass it will be

s1 = "Z Y X is name My"

Question 7

How to check if two Strings (words) are _Anagrams_?

Accepted Answer

Two words are anagrams of each other if they contain the same number of characters and the same characters. There are two solutions to mention:

1. You should only need to **sort** the characters in lexicographic order, and determine if all the characters in one string are equal to and in the same order as all of the characters in the other string. If you sort either array, the solution becomes `O(n log n)`.
2. **Hashmap** approach where key - letter and value - frequency of letter,
 * for first string populate the hashmap `O(n)`
 * for second string decrement count and remove element from hashmap `O(n)`
 * if hashmap is empty, the string is **anagram** otherwise not.

Question 8

Find all the _Permutations_ of a String

Accepted Answer

A **permutation**, also called an “arrangement number” or “order,” is a rearrangement of the elements of an ordered list S into a one-to-one correspondence with S itself (or in simple english: permutation is each of several possible ways in which a set or number of things can be ordered or arranged). A string of length `n` has `n!` permutation:

```js
ABC // original string (3)
ABC ACB BAC BCA CBA CAB // permutations 3! = 6
```

To print all permutations of a string use _backtracking_ implemented via _recursion_:

* Try each of the letters in turn as the _first letter_ and then find all the permutations of the _remaining letters_ using a recursive call.
* The _base case_ is when the input is an empty string the only permutation is the empty string.
* In other words, you simply traverse the tree, and when you reach the leaf you print the permutation. Then you backtrack one level up, and try another option. Moving one level up the tree is what we call the backtracking in this case.

![](https://media.geeksforgeeks.org/wp-content/cdn-uploads/NewPermutation.gif)

Question 9

Mentions some pros and cons of immutable vs mutable Strings

Accepted Answer

**Immutability** has several _advantages_, including (but not limited to): - Programs with immutable objects are less complicated to think about, since you don't need to worry about how an object may evolve over time. - You don't need to make defensive copies of immutable objects when returning or passing to other functions, since there is no possibility an immutable object will be modified behind your back. - One copy of an object is just as good as another, so you can cache objects or re-use the same object multiple times. - Immutable objects are good for sharing information between threads in a multi-threaded environment since they don't need to be synchronized and no locking shall be performed - Operations on immutable objects return new immutable objects while operations that cause side-effects on mutable objects usually return `void`. This means several operations can be chained together. For instance `("foo" + "bar" + "baz").length()` - In languages where functions are first class values, operations like `map`, `reduce`, `filter`, etc. are basic operations on collections. These can be combined in many ways, and can replace most loops in a program. - Runtime safety. In some languages like Java strings are immutable and cannot be subclassed. This means that the Java runtime can pass around and receive strings from the user while guaranteeing that the string's value will remain constant. There are of course some _disadvantages_: - Cyclic data structures such as graphs are difficult to build. If you have two objects which can't be modified after initialization, how can you get them to point to each other? - Allocating lots and lots of small objects rather than modifying ones you already have can have a performance impact. Usually the complexity of either the allocator or the garbage collector depends on the number of objects on the heap. - Naive implementations of immutable data structures can result in extremely poor performance. For instance, concatenating many immutable strings (like in Java) is `O(n²)` when the best algorithm is `O(n)`. It is possible to write efficient immutable data structures, it just takes a little more thought.

Question 10

How to check if String is a Palindrome?

Accepted Answer

A **palindrome** is a word, phrase, number or other sequence of units that _can be read the same way in either direction_. You can check if a string is a palindrome by comparing it to the reverse of itself either using simple _loop_ or _recursion_.

Top 25 Strings Interview Questions

What is String in Data Structures?

What is the difference between Strings vs. Char arrays?

What is strings mutability and immutability?

What is a null-terminated String?

Mentions some pros and cons of immutable vs mutable Strings

Explain Boyer-Moore Algorithm with Example

Check for balanced parentheses in linear time using constant space

What is Rope Data Structure is used for?

Why is `char[]` preferred over String for passwords?

What are some advantages of Rope data structure?

What are Pascal Strings?

What are some limitations of Ropes?

When to use Ropes over StringBuilders?

Compare Strings vs Ropes from the Performance Analysis

What's the rationale for `null` terminated strings?

When is Rabin-Karp more effective than KMP or Boyer-Moore?

What are the main differences between the Knuth-Morris-Pratt search algorithm and the Boyer-Moore search algorithm?

Reverse a String using Stack

How to check if String is a Palindrome?

Reverse the ordering of words in a String

How to check if two Strings (words) are Anagrams?

Remove Invalid Parentheses

Find all the Permutations of a String

Explain Knuth-Morris-Pratt (KMP) Algorithm in Plain English

Find all the repeating substrings in a given String (or DNA chromosome sequence)

Top 25 Strings Interview Questions

What is String in Data Structures?

What is the difference between Strings vs. Char arrays?

What is strings mutability and immutability?

What is a null-terminated String?

Mentions some pros and cons of immutable vs mutable Strings

Explain Boyer-Moore Algorithm with Example

Check for balanced parentheses in linear time using constant space

What is Rope Data Structure is used for?

Why is char[] preferred over String for passwords?

What are some advantages of Rope data structure?

What are Pascal Strings?

What are some limitations of Ropes?

When to use Ropes over StringBuilders?

Compare Strings vs Ropes from the Performance Analysis

What's the rationale for null terminated strings?

When is Rabin-Karp more effective than KMP or Boyer-Moore?

What are the main differences between the Knuth-Morris-Pratt search algorithm and the Boyer-Moore search algorithm?

Reverse a String using Stack

How to check if String is a Palindrome?

Reverse the ordering of words in a String

How to check if two Strings (words) are Anagrams?

Remove Invalid Parentheses

Find all the Permutations of a String

Explain Knuth-Morris-Pratt (KMP) Algorithm in Plain English

Find all the repeating substrings in a given String (or DNA chromosome sequence)

Why is `char[]` preferred over String for passwords?

What's the rationale for `null` terminated strings?