Practice DSA interview questions

Given two strings `text1` and `text2`, return the length of their longest common subsequence. A subsequence is generated by deleting zero or more characters. A common subsequence is one that is a subsequence of both. This is a foundational DP problem, and the recursive (memoized) solution is very intuitive.

You are given an integer array `nums` and an integer `target`. You want to build an expression out of `nums` by adding one of two symbols, `+` or `-`, before each integer. Return the number of different expressions that you can build which evaluate to `target`. This is a backtracking problem, equivalent to finding a subset that sums to a specific value. It can be optimized with memoization.

A message containing letters A-Z is encoded to numbers using 'A' -> '1', 'B' -> '2', ..., 'Z' -> '26'. Given a string `s` containing only digits, return the number of ways to decode it. For example, '11106' can be 'AAJF' or 'KJF'. This is a DP problem. At each digit, we can decode it as a single digit (if not '0') or as a two-digit number (if between '10' and '26').

You are a robber planning to rob houses along a street. Each house has a certain amount of money. The constraint is that you cannot rob two adjacent houses. Given an array `nums` representing the money in each house, return the maximum amount you can rob. This is a classic DP problem. At each house, you have two choices: rob it (and skip the next) or skip it (and consider the next).

The houses are now arranged in a binary tree. You still cannot rob two *directly connected* houses (parent and child). Find the maximum amount of money you can rob. This is a more complex version of House Robber. The recursive function must return two values: the max money if we *rob* the current node, and the max money if we *don't rob* it.

Given a list `accounts` where `accounts[i] = [name, email1, email2, ...]`, merge these accounts. Two accounts belong to the same person if there is at least one common email. The result should be a list of merged accounts, sorted by name. This is a graph problem. Each email is a node, and an edge exists between emails in the same account. We need to find the connected components.

There are `n` cities. Some are connected, while others are not. `isConnected[i][j] = 1` means city `i` and `j` are directly connected. A 'province' is a group of directly or indirectly connected cities. Return the total number of provinces. This is another 'connected components' graph problem, identical in structure to 'Number of Islands' but on an adjacency matrix.

Suppose you have `n` integers labeled 1 to `n`. A 'beautiful arrangement' is an array `perm` (a permutation) where for every `i` (1-indexed), either `perm[i-1]` is divisible by `i`, or `i` is divisible by `perm[i-1]`. Return the number of beautiful arrangements. This is a backtracking problem where we try to build a valid permutation.

A valid IP address consists of four integers, each between 0 and 255, separated by dots. Given a string `s` containing only digits, return all possible valid IP addresses that can be formed. For example, '25525511135' -> ['255.255.11.135', '255.255.111.35']. This is a backtracking problem. We try to place 3 dots in the string.

The Tower of Hanoi is a mathematical puzzle. It consists of three rods and a number of disks of different sizes, which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top. The objective is to move the entire stack to another rod, obeying: 1. Only one disk can be moved at a time. 2. A disk is slid off the top and placed on top of another stack. 3. No disk may be placed on top of a smaller disk.

Given a stack, sort it using recursion. You are not allowed to use any explicit loops (like `while` or `for`) or any other data structure. The only operations allowed are the standard stack operations: `push`, `pop`, `isEmpty`, and `peek`. This problem is a great test of 'pure' recursion and uses the call stack as storage. It's solved in two recursive parts: sorting the stack, and inserting an element into a sorted stack.

Given the `head` of a singly linked list, reverse the list, and return the reversed list's head. This is one of the most fundamental linked list operations and a very common interview question. The iterative approach requires you to carefully manage three pointers as you traverse the list: one for the previous node, one for the current node, and one to hold the next node temporarily. The goal is to reverse the `next` pointer of each node to point to its previous node.

You are given the heads of two sorted linked lists, `list1` and `list2`. Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists. Return the head of the merged linked list. This problem is a cornerstone for understanding list manipulation and is a building block for more complex problems like 'Merge k Sorted Lists'. The iterative approach is often preferred for its O(1) space complexity.

Given `head`, the head of a linked list, determine if the list has a cycle in it. There is a cycle if some node in the list can be reached again by continuously following the `next` pointer. This is a classic problem solved using the 'Floyd's Tortoise and Hare' algorithm. This two-pointer technique is efficient and uses constant space, making it a very common interview question to test a candidate's understanding of pointers and algorithms.

Given the `head` of a linked list, return the node where the cycle begins. If there is no cycle, return `null`. This is a follow-up to 'Detect Linked List Cycle'. It uses a mathematical proof based on Floyd's algorithm. After the slow and fast pointers meet, one pointer (e.g., `slow`) is moved back to the `head`. Then, both pointers are moved one step at a time. The node where they meet *again* is the starting node of the cycle.

Given the `head` of a linked list, remove the `n`th node from the end of the list and return its head. For example, given `1->2->3->4->5` and `n = 2`, the list becomes `1->2->3->5`. This problem tests a candidate's ability to use the two-pointer technique in a single pass. The key is to create a 'gap' of `n` nodes between two pointers and then move them in tandem.

You are given the `head` of a singly linked list. The list can be represented as `L0 -> L1 -> ... -> Ln-1 -> Ln`. Reorder the list to be in the following form: `L0 -> Ln -> L1 -> Ln-1 -> L2 -> Ln-2 -> ...`. You may not modify the values in the nodes; only the nodes themselves may be changed. This problem is a combination of three sub-problems: 1) Find the middle of the list. 2) Reverse the second half of the list. 3) Merge the two halves.

Given the `head` of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list, sorted. This is a simple list traversal problem. Because the list is sorted, all duplicate nodes will be adjacent to each other. We just need to iterate through the list and, if we find a duplicate, skip over it by adjusting the `next` pointer.

Given the heads of two singly linked lists, `headA` and `headB`, return the node at which the two lists intersect. If the two lists do not intersect, return `null`. The intersection is defined by reference, not value. This problem has a clever O(n+m) time and O(1) space solution. The trick is to find a way to make both pointers traverse the same total distance.

Given the `head` of a singly linked list, return `true` if it is a palindrome and `false` otherwise. A palindrome reads the same forwards and backward. The challenge here is to do it in O(n) time and O(1) space. This requires modifying the list in-place by reversing the second half and then comparing the two halves.

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each node contains a single digit. Add the two numbers and return the sum as a linked list. For example, `(2 -> 4 -> 3) + (5 -> 6 -> 4)` is `342 + 465 = 807`, so the result is `7 -> 0 -> 8`. This problem requires simulating elementary school addition, complete with a 'carry' variable.

Given a linked list, swap every two adjacent nodes and return its head. For `1->2->3->4`, the result is `2->1->4->3`. This must be done without modifying values. The iterative solution is a bit more complex than the recursive one, as it requires careful pointer management, often using a 'dummy' head node to simplify the logic for swapping the first two nodes.

Given the `head` of a linked list, reverse the nodes of the list `k` at a time, and return the modified list. `k` is a positive integer. If the number of nodes is not a multiple of `k`, the remaining nodes at the end should be left as-is. This is one of the hardest linked list problems. It requires reversing a sub-list and then 'stitching' the reversed sub-list back to the main list.

A linked list is given where each node contains a `next` pointer and a `random` pointer. The `random` pointer may point to any node in the list or `null`. Construct a deep copy of the list. A deep copy means creating a new node for each original node. The main challenge is to correctly set the `random` pointers in the new list. An O(n) solution uses a hash map to map old nodes to their new copies.

Given the `head` of a linked list, rotate the list to the right by `k` places. `k` is non-negative. For example, `1->2->3->4->5` rotated by `k=2` becomes `4->5->1->2->3`. The key insight is that this is equivalent to moving the last `k` nodes to the front. We can do this by finding the new tail and new head, and then relinking them.

You are given a doubly linked list, which, in addition to `next` and `prev` pointers, might have a `child` pointer. A `child` pointer may or may not point to a separate doubly linked list. These child lists may have their own children, and so on. Flatten the list so that all nodes appear in a single-level, doubly linked list. The nodes should be in the order of a pre-order traversal.

You are given an array of `k` linked-lists `lists`, each sorted in ascending order. Merge all the linked lists into one sorted linked list and return its head. This problem has two main solutions: 1) A divide-and-conquer (recursive) approach where you merge lists pairwise (like Merge Sort). 2) An optimized approach using a Min-Heap (Priority Queue) to efficiently find the smallest node among all `k` list heads.

Design your own implementation of a singly linked list. Your `MyLinkedList` class should support: `get(index)`, `addAtHead(val)`, `addAtTail(val)`, `addAtIndex(index, val)`, and `deleteAtIndex(index)`. This is a foundational 'design' question. It tests your ability to manage pointers, especially the `head`, `tail`, and `size`, and to handle all the edge cases involved in list manipulation.

Given the `head` of a singly linked list, group all nodes with odd indices together followed by the nodes with even indices, and return the reordered list. The first node is odd, the second is even, and so on. This must be done in-place with O(1) extra space. The problem is about 'un-weaving' the list into two separate lists (odd and even) and then re-linking them at the end.

Given the `head` of a sorted linked list, delete all nodes that have duplicate numbers, leaving only *distinct* numbers from the original list. Return the linked list, sorted. For example, `1->2->3->3->4->4->5` becomes `1->2->5`. This is much trickier than the first 'Remove Duplicates' problem. It requires a way to skip over *all* nodes of a certain value if a duplicate is found.