Practice DSA interview questions

Given an array of non-negative integers `nums`, you are initially positioned at the first index. Each element represents your maximum jump length. Your goal is to reach the last index in the minimum number of jumps. This is a breadth-first search (BFS) problem on a graph, but can also be solved with a greedy approach.

Given a string `s` and an integer `k`, return the length of the longest substring of `s` that contains at most `k` distinct characters. This is a generalization of the "At Most Two Distinct Characters" problem and can be solved with a sliding window.

Given the `root` of a binary tree, flatten it into a "linked list". The "linked list" should be in the same order as a pre-order traversal. This can be done with a single pass by keeping track of the previous node in the pre-order traversal.

A tree is an undirected graph in which any two vertices are connected by exactly one path. In a tree, a rooted tree can be defined by choosing one of the nodes as the root. Given a tree of `n` nodes, find all `minimum height trees` (MHTs). The height of a rooted tree is the number of edges on the longest downward path from the root to a leaf. The MHT is a rooted tree with the minimum possible height. This problem is a graph traversal problem that can be solved by pruning leaves.

A message containing letters from A-Z is being encoded to numbers using the mapping: 'A' -> 1, 'B' -> 2, ..., 'Z' -> 26. Given a string of digits, return the total number of ways to decode it.

Given an array of coins and a total amount, find the number of combinations that make up that amount. Assume infinite supply of each coin type.

Given an m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path. Only moves down or right are allowed.

You are given an integer array 'nums' and an integer 'target'. Find the number of ways to assign '+' or '-' signs to form the target sum. This is a variation of the subset sum problem.

Given a positive integer 'n', find the least number of perfect square numbers (1, 4, 9, 16, ...) which sum to 'n'.

Given an m x n binary matrix filled with 0's and 1's, find the length of the side of the largest square containing only 1's.

Given three strings s1, s2, and s3, determine if s3 is formed by an interleaving of s1 and s2 (maintaining relative order).

A robot is located at the top-left corner of an m x n grid. Find the number of unique paths to the bottom-right corner, given that some cells are marked as obstacles.

Given a binary matrix, find the area of the largest rectangle that contains only 1's.

Given two strings s1 and s2, find the lowest ASCII sum of characters that need to be deleted to make two strings equal. This is related to LCS.

You are given an array of words. A word chain is formed by adding exactly one character to a word to get the next word. Find the length of the longest possible word chain.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Design an algorithm to find the maximum profit. You may complete at most k transactions.

Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1. A string can be scrambled by recursively splitting it into two non-empty substrings and swapping the two parts.

Given an integer n, count the number of strings of length n that can be formed using the vowels ('a', 'e', 'i', 'o', 'u') such that the rules for vowel sequences are followed (e.g., 'a' may only be followed by 'e').

Given a string s, partition s such that every substring of the partition is a palindrome. Return the minimum cuts needed.

Given an array of non-negative integers $\text{nums}$, where $\text{nums}[i]$ is the maximum jump length from position $i$. Find the minimum number of jumps to reach $\text{nums}[n-1]$.

A knight is traversing a dungeon. Find the minimum initial health the knight must have to reach the bottom-right corner, ensuring health is always positive (> 0).

Given two integer arrays $\text{A}$ and $\text{B}$ of equal length, find the minimum number of swaps so that $\text{A}$ and $\text{B}$ are strictly increasing.

Given two strings $\text{word1}$ and $\text{word2}$, find the minimum number of operations (insert, delete, or replace) required to convert $\text{word1}$ to $\text{word2}$.

Given an array $\text{nums}$ and a target $\text{target}$, return the number of non-empty subsequences such that the sum of the minimum and maximum element is less than or equal to $\text{target}$.

You have $N$ piles of stones, $\text{piles}[i]$ stones in the $i$-th pile. You can merge any $\text{K}$ consecutive piles into one, costing the total number of stones in those piles. Find the minimum cost to merge all piles into one.

Given an array $\text{nums}$ and an integer $\text{k}$, split $\text{nums}$ into $\text{k}$ non-empty continuous subarrays such that the largest sum among these $\text{k}$ subarrays is minimized.

Given an array $\text{nums}$ and two integers $\text{firstLen}$ and $\text{secondLen}$, return the maximum sum of elements in two non-overlapping subarrays of lengths $\text{firstLen}$ and $\text{secondLen}$. This involves calculating prefix sums and using DP to track the maximum possible sum of a subarray of a certain length *up to* or *from* a specific index, allowing for two non-overlapping segments.

Given a non-empty string s and a dictionary of words, add spaces in s to construct all possible sentences where each word is in the dictionary. Return all such sentences. This problem combines DP for feasibility (word-break) with backtracking; the DP sub-problem: dp[i] = true if s[:i] can be segmented. Then build sentences by exploring valid splits.

Given an array length n, you need to build the array with numbers from 1…m, such that exactly k times the current element is strictly greater than all previous elements. Count the number of ways. This uses DP with two-dimensional state: dp[i][j] = number of arrays of length i with j “new maxima”. It illustrates state-transition thinking in DP beyond simple linear cases.