Practice DSA interview questions

Given an integer array `nums`, return the length of the longest strictly increasing subsequence. A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. This problem is another classic dynamic programming problem that can be solved with an O(n^2) DP approach or a more advanced O(n log n) solution using binary search. The simpler DP solution involves building an array to store the lengths of the longest increasing subsequences ending at each index.

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. The only constraint stopping you from robbing each house is that adjacent houses have security systems connected, and it will automatically contact the police if two adjacent houses are broken into on the same night. Given an integer array `nums` representing the amount of money in each house, return the maximum amount of money you can rob without alerting the police.

There is a robot on an m x n grid. The robot is initially located at the top-left corner (grid[0][0]). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (grid[m-1][n-1]). How many unique paths are there? This problem is a classic example of dynamic programming and combinatorial mathematics. The number of unique paths to a cell is the sum of the unique paths to the cell above it and the cell to its left.

Given a 2D binary grid of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water. This problem is a classic graph traversal problem that can be solved using either Breadth-First Search (BFS) or Depth-First Search (DFS). The goal is to traverse each island and "sink" it (change '1's to '0's) so it is not counted again.

Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph. Each node in the graph contains a value and a list of its neighbors. This problem requires us to create a new graph with the same structure and node values as the original, but with new nodes. A common challenge is to handle cycles in the graph, as a simple recursive copy could lead to an infinite loop. We need a way to keep track of nodes we have already visited and copied.

Find the length of the longest common subsequence between two strings. This is a classic dynamic programming problem with a straightforward recursive definition. The problem is characterized by overlapping subproblems and optimal substructure. A common approach involves building a 2D DP table.

Given a set of candidate numbers and a target number, find all unique combinations in candidates where the candidate numbers sum to target. The same number can be used multiple times. This is a classic backtracking problem that can be solved with a recursive approach.

Given an array of distinct integers, return all the possible permutations. You can return the answer in any order. A permutation is an arrangement of objects in a specific order. This is another classic backtracking problem where we explore all possible arrangements.

Given an integer array nums of unique elements, return all possible subsets (the power set). The solution set must not contain duplicate subsets. This is a classic example of backtracking where we must decide at each element whether to include it in our current subset or not.

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. The same word in the dictionary can be reused multiple times. This is a classic dynamic programming problem, and it can also be solved with memoization.

You are given an integer array `nums`. You are initially positioned at the first index, and each element in the array represents your maximum jump length at that position. Return `true` if you can reach the last index, or `false` otherwise. This problem can be solved with dynamic programming, but a greedy approach is more efficient and provides a single-pass solution.

You are given two binary trees `root1` and `root2`. Imagine that you are putting one of them to cover the other. The two trees are merged into a new binary tree. The merge rule is that if two nodes overlap, their values are summed up as the new node's value. Otherwise, the non-null node will be the new node. This problem can be solved with a recursive approach that traverses both trees simultaneously.

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment. Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to be able to serialize a binary tree to a string and deserialize the string back to the original tree.

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. The path sum is the sum of the node's values in the path. Given the root of a binary tree, return the maximum path sum of any non-empty path. This is a challenging problem that requires a recursive approach to calculate and track both the maximum path sum within a subtree and the maximum path sum that can be formed by a path that passes through the root of the subtree.

Given an array of meeting time intervals `intervals` where `intervals[i] = [starti, endi]`, return the minimum number of conference rooms required. This problem is about managing resources (meeting rooms) over time. It can be solved efficiently by sorting and using a min-heap to keep track of room availability. A simpler approach is to use a sweep-line algorithm that increments a counter at each start time and decrements at each end time.

Given an array of meeting time intervals, determine if a person could attend all meetings. This is a simple problem compared to Meeting Rooms II. You need to check for any overlaps. The key insight is that if you sort the meetings by their start times, you only need to check for overlap between consecutive meetings.

Given a collection of intervals, find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping. The key is to sort the intervals and then greedily select the ones that cause the least overlap. A simple strategy is to always choose the interval that finishes earliest to leave the most room for subsequent intervals.

Given a 1-indexed array of integers that is already sorted in non-decreasing order, find two numbers that add up to a specific target number. The key is to leverage the sorted nature of the array to solve this problem more efficiently than a brute-force approach or a hash map. The two-pointer technique is perfect for this, as it allows for a single pass with constant space.

Given an array of integers `nums` and a target, find three integers in `nums` such that the sum is closest to the target. Return the sum of the three integers. Assume that there is exactly one solution. This is a variation of the 3Sum problem that also benefits from sorting and a two-pointer approach.

Implement the `myAtoi(string s)` function, which converts a string to a 32-bit signed integer. The function must discard leading whitespace, check for a sign, and then read digits until a non-digit character is found. Handle edge cases like overflow and invalid input.

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 fundamental string searching problem. A simple solution uses brute force, while more advanced algorithms like KMP (Knuth-Morris-Pratt) offer better performance.

Given a string s which consists of lowercase or uppercase letters, find the length of the longest palindrome that can be built with those letters. This is a counting problem rather than a search or DP problem. It's about efficiently using the available characters to form a palindrome.

Given two strings `s1` and `s2`, return true if `s2` contains a permutation of `s1`, or false otherwise. In other words, return true if one of `s1`'s permutations is the substring of `s2`. This can be solved with a sliding window and a frequency map or an array to track character counts.

Given two strings `s` and `p`, return an array of all the start indices of `p`'s anagrams in `s`. The order of the output does not matter. An anagram is a word or phrase formed by rearranging the letters of a different word or phrase. This is another sliding window problem similar to Permutation in String.

Given two strings `s` and `t`, return the minimum window substring of `s` such that every character in `t` (including duplicates) is included in the window. If there is no such substring, return an empty string. This is a classic sliding window problem that requires careful management of character counts.

Given two words, `beginWord` and `endWord`, and a dictionary `wordList`, return the length of the shortest transformation sequence from `beginWord` to `endWord`, such that: only one letter can be changed at a time, and each transformed word must exist in `wordList`. This problem can be modeled as finding the shortest path in an unweighted graph, making Breadth-First Search (BFS) a suitable algorithm.

There are a total of `numCourses` courses you have to take, labeled from `0` to `numCourses - 1`. You are given an array `prerequisites` where `prerequisites[i] = [ai, bi]` indicates that you must take course `bi` first if you want to take course `ai`. Return `true` if you can finish all courses, or `false` otherwise. This is a classic topological sort problem on a directed graph.

Given an `m x n` matrix of positive integers representing an elevation map, find a list of grid coordinates `(r, c)` where water can flow to both the Pacific and Atlantic oceans. Water can only flow from a cell to an adjacent cell with a height less than or equal to the current cell's height. This is a graph traversal problem that can be solved with multiple DFS or BFS runs.

Given `n` nodes labeled from `0` to `n-1` and a list of undirected edges, write a function to check whether these edges form a valid tree. A valid tree is a connected graph with no cycles. This is a classic graph problem that can be solved with DFS/BFS or Union-Find.

Given `n` nodes labeled from `0` to `n-1` and a list of undirected edges, find the number of connected components in the graph. A connected component is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices in the supergraph.