String interview questions, with answers

The questions, with answers

1. 1.Why are strings immutable in Java and Python, and what does it cost?

   An immutable string can never change after creation, which makes it safe to share between threads, safe as a hash-map key (its hash never goes stale), and cacheable — Java interns string literals so identical literals share one object. The cost is that every apparent modification creates a new string. Building a string of n characters by appending one at a time with s = s + c copies the growing string each round: 1 + 2 + ... + n characters, O(n²) in total. The fix is a mutable builder — StringBuilder in Java, a list of pieces joined once in Python, or a character array — which appends in amortised O(1) and gives O(n) overall. Recognising the quadratic loop on sight is the mark of a candidate who has been bitten by it.

   StringBuilder sb = new StringBuilder();
   for (char c : chars) sb.append(c);   // amortised O(1) each
   String s = sb.toString();            // one O(n) copy at the end

2. 2.What is the difference between == and equals() for strings in Java?

   == compares references — whether both variables point at the same object — while equals() compares contents character by character. Two literals "hello" == "hello" is true only because the compiler interns literals into one shared object; new String("hello") == "hello" is false even though equals() says true. So == on strings works by accident in tests and fails in production when a string arrives from input, a file or a database. The rule: always equals() (or equalsIgnoreCase) for content, and hashCode is consistent with it, which is why strings work as map keys. Python's == compares content and is is the identity check, with the same interning subtlety for short literals.

3. 3.How do you check whether a string is a palindrome, including the punctuation variant?

   Two pointers, one at each end, comparing characters and moving inward until they meet: O(n) time, O(1) space, and no reversed copy needed. "A man, a plan, a canal: Panama" is the variant interviewers add — skip characters that are not letters or digits, and compare case-insensitively, by advancing whichever pointer sits on a non-alphanumeric character before comparing. The recursive version is O(n) space because of the call stack, and reversing the string and comparing is O(n) space too; both are fine to mention, then give the two-pointer scan. The follow-up is the longest palindromic substring, which expands around each centre (2n - 1 centres, counting the gaps between characters) in O(n²).

   boolean isPalindrome(String s) {
       int i = 0, j = s.length() - 1;
       while (i < j) {
           while (i < j && !Character.isLetterOrDigit(s.charAt(i))) i++;
           while (i < j && !Character.isLetterOrDigit(s.charAt(j))) j--;
           if (Character.toLowerCase(s.charAt(i)) != Character.toLowerCase(s.charAt(j))) return false;
           i++; j--;
       }
       return true;
   }

4. 4.How do you check whether two strings are anagrams?

   Two strings are anagrams if they contain the same characters with the same counts. Sorting both and comparing is O(n log n) and the obvious first answer. The O(n) answer is a frequency table: count each character of the first string up and each character of the second down in an array of 26 (for lowercase letters) or a hash map (for Unicode), and check that every count ends at zero — or check the lengths first, since different lengths can never be anagrams. Say why the array is fixed-size: 26 counters cost O(1) space regardless of n. Grouping many words into anagram classes uses the same idea with the sorted word, or the count signature, as a map key.

5. 5.How do you find the first non-repeating character in a string?

   Two passes. First, count every character's occurrences in a fixed array or map. Second, walk the string from the left and return the first character whose count is 1. Both passes are O(n), and the counter is O(1) for a fixed alphabet. The reason a single pass is not enough is the question's real content: when you meet a character for the first time, you cannot yet know whether it will repeat later, so you must see the whole string before you can judge any position. A single-pass variant exists — keep the characters in an insertion-ordered map and delete on the second sighting — but it is O(n) space and no faster; the two-pass version is the cleaner answer.

6. 6.How do you reverse the words in a sentence in place?

   Reverse the entire character array, then reverse each word individually. "the sky is blue" reversed wholesale becomes "eulb si yks eht", and reversing each word restores them: "blue is sky the". Two O(n) passes, O(1) extra space, which is the point — the easy answer of splitting on spaces, reversing the list and joining allocates a copy and is O(n) space. Handle the edges the interviewer will raise: multiple spaces between words, and leading or trailing spaces, which the in-place version has to compact first. In Java, where String is immutable, work on a char array and build the result from it.

7. 7.How do you search for a pattern inside a text, and why is the naive way slow?

   The naive search tries the pattern at every position of the text and compares character by character, which is O(n × m) for a text of n and a pattern of m in the worst case — "aaaaab" searched in "aaaaaaaaaa" keeps matching five characters and failing on the sixth. Knuth-Morris-Pratt precomputes, for each prefix of the pattern, the length of its longest proper prefix that is also a suffix, so that after a mismatch the pattern slides forward without re-examining text characters; the total becomes O(n + m). Rabin-Karp hashes windows of the text and compares hash values, also O(n + m) on average, and extends naturally to searching for many patterns at once. In an interview, describe the naive version, name its worst case, and explain the failure-function idea of KMP; writing KMP from memory is rarely expected.

8. 8.How do you compress a string like aaabbc into a3b2c1, and when should you not?

   Scan with two indices: mark where a run starts, advance while the character repeats, then emit the character and the run length. O(n) time, and the output is built in a StringBuilder or a char array so it is O(n) rather than quadratic. The subtlety is the last run — emit it after the loop ends, which is the bug most people write. The design follow-up: run-length encoding can make a string longer (abc becomes a1b1c1), so the function should return the original when the compressed version is not shorter, and the interviewer may ask you to compute the compressed length first without building it. Say that real compression uses smarter models, and that this question is about scanning carefully, not about compression.

How the diagnostic asks it

One question from the DSA bank, exactly as a sitting would show it. The bank has 4 on strings and 60 across DSA.