Practice DSA interview questions

Given two strings `text1` and `text2`, return the length of their longest common subsequence. A subsequence is a new string generated from the original string with zero or more characters deleted. This is a foundational 2D dynamic programming problem. `dp[i][j]` stores the LCS of `text1[:i]` and `text2[:j]`. This problem is often taught with strings as the primary data type.

The 'Count and Say' sequence is generated as follows: `countAndSay(1) = '1'`. `countAndSay(n)` is the 'saying' of `countAndSay(n-1)`. For `n=4`: `countAndSay(3) = '21'`, which is 'two 1s'. So `countAndSay(4) = '1211'`. This is a string simulation problem that is solved iteratively or recursively. You must 'read' the previous string, counting groups of identical characters.

Given a string `s` representing a valid expression, implement a basic calculator to evaluate it. The expression may contain `(`, `)`, `+`, `-`, non-negative integers, and spaces. This is a very common hard problem from FAANG interviews. It tests your ability to parse a string and handle operator precedence, which is naturally solved using a stack.

Given two non-negative integers `num1` and `num2` represented as strings, return their product, also as a string. You must not use any built-in BigInteger library or convert the inputs to integers directly. This problem tests your ability to simulate elementary school 'long multiplication' using an array (or list) to store the intermediate sums.

Given two strings `s` and `p`, return an array of all the start indices of `p`'s anagrams in `s`. This is a classic sliding window problem. It requires maintaining a fixed-size window in `s` (equal to the length of `p`) and using a hash map or frequency array to check if the characters in the window form an anagram of `p`. Efficiently updating the window's character counts is key to an O(n) solution, where n is the length of the string s.

Given two strings `s1` and `s2`, return `true` if `s2` contains a permutation (anagram) of `s1` as a substring, and `false` otherwise. This is identical in logic to 'Find All Anagrams', but we can return `true` as soon as the first match is found. It's a fundamental test of the sliding window with frequency maps technique. The window size is fixed to the length of `s1`, and we slide it across `s2`, comparing character counts.

Given a string `s`, return `true` if it can be a palindrome after deleting at most one character. This is a common follow-up to 'Valid Palindrome'. It's solved with a greedy two-pointer approach. When we find the first mismatch, we are forced to make a decision: either delete the left character or delete the right character. We then check if *either* of those resulting sub-problems is a valid palindrome.

Given a string `s`, find the first non-repeating character in it and return its index. If it does not exist, return -1. This is a common hash map problem. A simple solution involves two passes: the first pass to build a frequency map of all characters, and the second pass to iterate through the string again, returning the index of the first character that has a count of 1 in the map.

Implement a basic calculator to evaluate an expression string `s` containing non-negative integers, `+`, `-`, `*`, `/`, and spaces. The integer division should truncate. This is a classic parsing problem. The key is to handle operator precedence (`*` and `/` must be evaluated before `+` and `-`). A common solution uses a stack to store the operands. When `*` or `/` is seen, we immediately operate on the last number in the stack.

Given an encoded string, return its decoded string. The encoding rule is: `k[encoded_string]`, where the `encoded_string` inside the square brackets is repeated `k` times. This is a classic parsing problem, perfectly solved using one or two stacks. We need to store the `count` and the `string_so_far` when we encounter a `[`.

You are given a string `s`. A 'duplicate removal' consists of choosing two adjacent and equal letters and removing them. We repeatedly make removals until we no longer can. Return the final string. This is a classic stack problem. The stack is used to build the 'resulting' string. If the current character is the same as the top of the stack, it's a duplicate, so we pop. Otherwise, we push.

This is a harder follow-up to the previous problem. This time, you are given a string `s` and an integer `k`. A 'k duplicate removal' consists of choosing `k` adjacent and equal letters and removing them. Return the final string. This requires a modification to the stack: instead of just storing the character, the stack must store `(character, count)`.

Given a string `s`, rearrange the characters so that no two adjacent characters are the same. If this is not possible, return an empty string. This is a common, hard, greedy problem. The key is to always append the *most frequent* character that is *not* the same as the last character appended. This is solved efficiently using a Max-Heap.

Given two strings `text1` and `text2`, find the length of the *longest common substring*. A substring is a contiguous block of characters. This is a classic 2D Dynamic Programming problem, different from 'Longest Common Subsequence'. `dp[i][j]` stores the length of the longest common substring *ending* at `text1[i-1]` and `text2[j-1]`. This is a common variant of LCS.

Given a string `s`, find the length of the longest palindromic *subsequence*. A subsequence can be non-contiguous. For example, in `bbbab`, the LPS is `bbbb` (length 4). This is a classic DP problem. The key insight is that the LPS of `s` is the same as the Longest Common Subsequence (LCS) of `s` and `reverse(s)`.

The DNA sequence is represented by a string of 'A', 'C', 'G', 'T'. Find all 10-letter-long sequences (substrings) that occur more than once. This is a hashing problem. A naive solution using a hash map of substrings will work. A more "rolling hash" (Rabin-Karp) approach can optimize this by calculating the hash of each 10-letter window in O(1) time.

The KMP algorithm is an O(n+m) string searching algorithm. Its core component is the Longest Proper Prefix which is also a Suffix (LPS) array. Given a `needle` string, compute the LPS array. `lps[i]` is the length of the longest proper prefix of `needle[0...i]` which is also a suffix of `needle[0...i]`. For example, for 'AAAA', `lps = [0, 1, 2, 3]`. For 'ABCDE', `lps = [0, 0, 0, 0, 0]`.

Given a `haystack` and `needle`, find the first occurrence of `needle` in `haystack` using the Knuth-Morris-Pratt (KMP) algorithm. This is the O(n+m) solution to the 'strStr' problem. It uses a pre-computed LPS (Longest Proper Prefix which is also a Suffix) array to 'skip' unnecessary comparisons when a mismatch occurs.

Given a string `s`, you can convert it to a palindrome by adding characters *in front* of it. Return the shortest palindrome you can find. For `s = 'aacecaaa'`, the shortest is `'aaacecaaa'`. For `s = 'abcd'`, the shortest is `'dcbabcd'`. This is a hard problem. The key is to find the *longest palindromic prefix* of `s`. The non-palindromic part at the end must be reversed and prepended.

Given a string `s` and an integer `k`, find the length of the longest substring of `s` that contains at most `k` distinct characters. This is a classic sliding window problem where the 'validity' of the window is defined by the number of unique characters in it. We use a hash map to track the frequencies of characters in the current window.

Given a string `s`, find the length of the longest substring that contains at most *two* distinct characters. This is a specific case of the previous problem ('at most k'), where `k = 2`. The logic is identical, but the constraints are simpler. It's a common sliding window problem.

Two strings are 'close' if you can attain one from the other using these operations: 1) Swap any two existing characters. 2) Transform *every* occurrence of one character into another, and do the same for the other. This means they must have the same set of characters, and, more importantly, the *frequency counts* of their characters must be the same (e.g., 'cabbba' and 'abbccc' are close).

Implement a method to perform basic string compression. For example, 'aabcccccaaa' would become 'a2b1c5a3'. If the 'compressed' string would not be smaller than the original, return the original. This is a 'run-length encoding' problem. It requires iterating through the string and 'counting' groups of identical, consecutive characters.

Given a string `s`, partition `s` such that every substring in the partition is a palindrome. Return all possible palindrome partitionings. For example, `s = 'aab'` should return `[['a', 'a', 'b'], ['aa', 'b']]`. This is a classic recursive backtracking problem. We try to 'cut' the string at every possible position, and if the part we just cut is a palindrome, we recurse on the rest of the string.

Write a function to find the longest common prefix string amongst an array of strings. If there is no common prefix, return an empty string `"`. This is a common interview question that tests basic string manipulation. The 'vertical scanning' approach is simple and efficient. It compares all strings character by character at each index.

Implement the Rabin-Karp algorithm to find the first occurrence of a `needle` in a `haystack`. This algorithm uses 'hashing' to solve the string matching problem. It calculates a 'rolling hash' for a window in the `haystack` and compares it to the `needle`'s hash. If the hashes match, it performs a character-by-character check to confirm (to handle hash collisions).

Given a string `s`, find the longest duplicate substring. If no duplicate substring exists, return `"`. This is a hard problem that combines 'Binary Search on the Answer' with 'Rabin-Karp Hashing'. We binary search for the *length* of the substring. For a given `length`, we use a rolling hash to check if any substring of that `length` appears more than once.

Given two version strings `version1` and `version2`, return -1 if `version1 < version2`, 1 if `version1 > version2`, and 0 if they are equal. Version strings are dot-separated numbers (e.g., `1.0.1`). This is a parsing problem. We need to split both strings by the `.` and compare the integer values of each component, padding with zeros for lists of different lengths.

Convert a non-negative integer `num` to its English words representation. `num` is less than 2^31 - 1. This is a very hard simulation problem, often asked in interviews to check if you can break a large problem into smaller, manageable sub-problems. The key is to handle numbers in groups of three (hundreds, tens, ones) and then append the correct 'chunk' name (Thousand, Million, Billion).

Given strings `s1`, `s2`, and `s3`, find whether `s3` is formed by an interleaving of `s1` and `s2`. An interleaving means the characters from `s1` and `s2` are split and combined, *while maintaining their relative order*. This is a classic 2D Dynamic Programming problem. `dp[i][j]` represents if `s3[:i+j]` can be formed by `s1[:i]` and `s2[:j]`.