Practice DSA interview questions

Given a Binary Search Tree (BST), convert it into a *circular* doubly linked list *in-place*. The `left` pointer should be `prev` and `right` should be `next`. The nodes must be in in-order. This is a common Google/Facebook question. It's solved with an in-order traversal, carefully 'stitching' nodes together as you go.

Given the `root` of a binary tree, return all *duplicate subtrees*. A duplicate subtree is one that has the same structure and node values as another subtree. This is a hard problem. The key is to find a way to *serialize* each subtree. We can then use a hash map to count the occurrences of each serialized string.

Given a binary tree, check if it's a valid BST. This is an alternative solution to the min/max bounds method. The key property of a BST is that an *in-order traversal* visits the nodes in strictly increasing order. We can perform an in-order traversal and check if this property is violated at any point.

You are given a *perfect binary tree* (all leaves at same level, all non-leaves have 2 children). Populate each `next` pointer to point to its next right node. If no right node, set to `NULL`. This is a classic Facebook question. It can be solved with BFS, but a more clever O(1) space recursive solution is often sought.

This is the follow-up to the previous problem. Now, the given tree is *any* binary tree, not necessarily perfect. This breaks the O(1) space recursive solution, as `root.right.next` is no longer guaranteed to be `root.next.left`. The most robust solution is to use a standard Level Order (BFS) traversal.

Given an `m x n` grid of '1's (land) and '0's (water), return the number of islands. An island is formed by connected '1's (horizontally/vertically). This is a quintessential FAANG graph/tree problem. We traverse the grid. When we find 'land', we increment a counter and then use a recursive DFS to 'sink' the entire island (flip '1's to '0's) so we don't count it again.

Given a `node` in a connected undirected graph, return a deep copy (clone). Each node has a `val` and a `neighbors` list. A deep copy requires creating new nodes and new neighbor lists. This is a very common FAANG question that tests graph traversal (DFS or BFS) and the use of a hash map to avoid cycles and redundant copies.

Given an integer `n` (number of nodes) and a list of `edges`, find the number of connected components in the undirected graph. This is a foundational graph problem, often solved with a tree-like DFS or BFS traversal. We iterate through all nodes, and if a node hasn't been visited, we start a traversal from it and mark all reachable nodes as visited. Each new traversal we start is a new component.

Given two strings `s` and `t`, return `true` if `t` is an anagram of `s`, and `false` otherwise. An anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once. This fundamental problem tests your understanding of hash maps or frequency arrays. The core idea is to count the character frequencies in one string and then decrement the counts using the second string. If all counts are zero at the end, they are anagrams.

Given an array of strings `strs`, group the anagrams together. You can return the answer in any order. For example, `['eat', 'tea', 'tan', 'ate', 'nat', 'bat']` becomes `[['bat'], ['nat', 'tan'], ['ate', 'eat', 'tea']]`. This is a classic hash map problem. The key is to find a unique, canonical representation for all anagrams. The most common way is to use the *sorted* version of the string as the key in a hash map.

Given a string `s`, find the length of the *longest substring* without repeating characters. This is a classic 'sliding window' problem, a fundamental technique in FAANG interviews. We use two pointers, `left` and `right`, to define a 'window' and a hash set (or map) to keep track of the characters currently in that window. We expand the window with `right` and shrink it with `left` when a duplicate is found.

Given a string `s`, return the longest palindromic substring. A substring is a contiguous sequence of characters. This is a classic dynamic programming problem, but it's often solved more intuitively with an 'expand from center' approach. We iterate through every character and treat it (and the space between it and the next) as a potential 'center' of a palindrome. We then expand outwards.

Given two strings `s` and `t`, return the minimum window (contiguous substring) in `s` which will contain all the characters in `t`. If there is no such window, return an empty string. This is a very hard and very common 'sliding window' problem. It requires a window, two pointers, a hash map for `t`'s character counts, and a counter to track how many characters from `t` are 'needed' in the current window.

Given a string `s`, return `true` if it is a palindrome, or `false` otherwise. A palindrome is a string that reads the same forward and backward. This check should be made after converting all uppercase letters to lowercase and removing all non-alphanumeric characters. This is a classic two-pointer problem that tests string cleaning and pointer manipulation.

Implement the `atoi` function, which converts a string to a 32-bit signed integer. The function must first discard whitespace, then check for an optional `+` or `-` sign, and finally read in digits until a non-digit character is found. The result must be clamped to the 32-bit integer range `[-2^31, 2^31 - 1]`. This is a classic parsing problem that tests edge case handling.

You are given a string `s` and an integer `k`. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most `k` times. Return the length of the longest substring containing the same letter you can get after performing the operations. This is an advanced sliding window problem. The key is the window validity condition: `(window_length - max_frequency_in_window) <= k`.

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 `"`. For example, `['flower', 'flow', 'flight']` should return `'fl'`. This problem can be solved in several ways, but a simple and robust method is 'vertical scanning', where you compare the first character of all strings, then the second, and so on.

Given a string `s` containing just the characters `(`, `)`, `{`, `}`, `[` and `]`, determine if the input string is valid. An input string is valid if open brackets are closed by the same type and in the correct order. This is a quintessential 'Stack' problem, but it's one of the most common string-based questions in interviews. It tests your ability to use an auxiliary data structure to validate a string.

Given a string `s`, return the *number* of palindromic substrings in it. A substring is a contiguous sequence. `s = 'aaa'` has 6 palindromic substrings: 'a', 'a', 'a', 'aa', 'aa', 'aaa'. This is a variation of 'Longest Palindromic Substring'. We can use the same 'expand from center' approach. For each of the `2n - 1` possible centers, we expand outwards and count how many palindromes are formed.

Given a string `s` and a dictionary of strings `wordDict`, return `true` if `s` can be segmented into a space-separated sequence of one or more dictionary words. This is a classic dynamic programming problem. We want to find if `s[0...i]` can be broken down. This can be solved with a 1D DP array.

Design an algorithm to encode a list of strings to a single string, and a `decode` function to decode it back. This is a very common FAANG (especially Google) phone screen question. The challenge is handling edge cases like empty strings or strings containing special delimiters. A common solution is `length + delimiter + string` (e.g., `4#list3#and`).

Implement `strStr()`. Given two strings, `haystack` and `needle`, return the index of the first occurrence of `needle` in `haystack`, or -1 if `needle` is not part of `haystack`. This is a classic string searching problem. A naive O(n*m) solution is simple to implement. The famous O(n+m) solution uses the Knuth-Morris-Pratt (KMP) algorithm.

Write a function that reverses a string. The input string is given as an array of characters `s`. You must do this by modifying the input array *in-place* with O(1) extra memory. This is the most basic string (or array) manipulation problem, testing your understanding of in-place modification and the two-pointer technique.

Given an input string `s`, reverse the order of the words. A word is defined as a sequence of non-space characters. The words are separated by at least one space. The returned string should have a single space separating words. This problem is tricky, especially the O(1) space in-place solution (for a mutable string/char array). The Python solution is simpler.

Given a string `s`, find the minimum number of 'delete' operations to make the frequencies of all characters unique. For `s = 'aaabbbcc'`, frequencies are `a:3, b:3, c:2`. We can delete one 'b' to get `a:3, b:2, c:2`. Then delete one 'c' to get `a:3, b:2, c:1`. Total deletions: 2. This is a greedy problem using a hash map and a set.

Given an absolute path for a Unix-style file system (a string), simplify it. This involves resolving `.` (current directory), `..` (parent directory), and `//` (multiple slashes). The simplified path should be canonical. This is a classic string parsing problem that is perfectly solved using a stack to simulate the directory changes.

Given an array of strings `words` and a `maxWidth`, format the text such that each line has exactly `maxWidth` characters and is fully justified (both left and right). You must pack as many words as you can in each line. This is a very hard string manipulation and simulation problem. It's all about correctly calculating and distributing the spaces between words.

The string `PAYPALISHIRING` is written in a zigzag pattern on `numRows` rows. For `numRows = 3`, it's `P A H N`, `A P L S I I G`, `Y I R`. Then, read it line by line: `PAHNAPLSIIGYIR`. This is a string manipulation problem. The key is to find the pattern. We can create `numRows` lists (one for each row) and append characters to the correct list as we 'traverse' the zigzag pattern.

Given a string representing a Roman numeral, convert it to an integer. Roman numerals are represented by combinations of letters. The key feature is subtraction. `IV` is 4 (5 - 1) and `IX` is 9 (10 - 1). This rule applies to `I`, `X`, and `C`. This problem tests your ability to handle these special subtractive cases, which depend on the *next* character.

Given an integer, convert it to a Roman numeral. The integer is guaranteed to be within the range 1 to 3999. This is the reverse of the 'Roman to Integer' problem. The easiest way is to use a greedy approach. We store the "symbols" (like 'M', 'CM', 'D', 'CD', etc.) and their values in a descending list. We subtract the largest possible value from the number and append its symbol.