Practice DSA interview questions

Given an array of integers, your task is to find the indices of two numbers within that array that add up to a specific target value. You can assume that each input will have exactly one solution, and you may not use the same element twice. The challenge lies in finding an efficient way to search for the required numbers. A brute-force approach of checking every pair of numbers would be too slow for large inputs, so a more performant algorithm is needed. This problem is a foundational exercise in using hash maps to optimize lookups.

You are given an array `prices` where `prices[i]` is the price of a given stock on the `i`th day. You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock. If you cannot achieve any profit, return 0. This problem is a classic example of a one-pass algorithm that efficiently finds the optimal solution.

Given a string `s` containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. A valid string must have open brackets closed by the same type of brackets, and open brackets must be closed in the correct order. This is a classic stack problem that tests your understanding of LIFO (Last-In, First-Out) data structures.

Given an integer array `nums`, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum. A subarray is a contiguous part of an array. This is a classic dynamic programming problem, and the most famous solution is Kadane's algorithm, which solves it in linear time.

Given an array of intervals where `intervals[i] = [starti, endi]`, merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals in the input. This problem requires a greedy approach where you sort the intervals and then merge them one by one.

Given an integer array `nums`, return an array `answer` such that `answer[i]` is equal to the product of all the elements of `nums` except `nums[i]`. The challenge is to solve this problem without using the division operator and in O(n) time. This can be achieved by computing prefix and suffix products.

Suppose a sorted array is rotated at some pivot unknown to you beforehand. For example, `[0,1,2,4,5,6,7]` might become `[4,5,6,7,0,1,2]`. You are given this rotated sorted array and your task is to find the minimum element in it. You can assume that no duplicate elements exist in the array. This is a classic binary search problem that requires careful handling of the search space.

You are given a rotated sorted array and a target value. Your task is to search for the target in the array and return its index. If the target is not in the array, return -1. The challenge is to solve this in O(log n) time, which suggests using a modified binary search algorithm. You must account for the rotation, as the standard binary search won't work.

Given an integer array `nums`, return all the unique triplets `[nums[i], nums[j], nums[k]]` such that `i != j`, `i != k`, and `j != k`, and `nums[i] + nums[j] + nums[k] == 0`. The solution set must not contain duplicate triplets. This is a classic two-pointer problem that builds upon the two-sum approach.

You are given an integer array `height` of length `n`. There are `n` vertical lines drawn such that the two endpoints of the `i`th line are `(i, 0)` and `(i, height[i])`. Find two lines that together with the x-axis form a container, such that the container contains the most water. Return the maximum amount of water a container can store. The problem requires a clever approach to find the optimal pair of lines.

You are climbing a staircase. It takes `n` steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top? This is a classic dynamic programming problem that can also be solved with a simple iterative approach.

Given a string `s`, find the length of the longest substring without repeating characters. A substring is a contiguous sequence of characters within a string. This is a very common interview question that demonstrates the power of the sliding window technique.

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 is a fundamental string and hash map problem.

Given an array of strings `strs`, group the anagrams together. You may return the answer in any order. 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 is a problem that uses hashing to group similar items.

Given the `root` of a binary tree, return its maximum depth. The maximum depth of a binary tree is the number of nodes along the longest path from the root node down to the farthest leaf node. This problem can be solved with a simple recursive or iterative traversal.

Given the roots of two binary trees, `p` and `q`, write a function to check if they are the same. Two binary trees are considered the same if they are structurally identical, and the nodes have the same value. This problem tests your ability to perform a simultaneous traversal of two trees.

Given the `root` of a binary tree, invert the tree, and return its root. Inverting a tree means for every node, its left and right children are swapped. This is a straightforward problem that can be solved with recursion or a level-order traversal.

Given the `root` of a binary tree, check whether it is a mirror of itself. A symmetric tree is one where the right side is a mirror image of the left side. This means that a simultaneous traversal of the left and right subtrees must yield identical values, but in a mirror fashion.

Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct. This problem is a foundational check for uniqueness in data structures. An efficient solution typically leverages a hash set to store elements as they are iterated. If an element is found to be already in the set, it means a duplicate exists, and we can immediately return true. Otherwise, we add the current element to the set and continue. If the loop completes without finding any duplicates, we return false.

Find the contiguous subarray with the largest product. The array can contain positive, negative, and zero values. The key challenge lies in handling negative numbers, as a negative multiplied by another negative becomes positive, potentially leading to a new maximum. This means we must track both the maximum and minimum products ending at the current position. This problem is a classic dynamic programming example, where the state at each step depends on the previous state in a non-obvious way.

Given an array of integers nums and an integer k, return the total number of continuous subarrays whose sum equals to k. This problem requires an efficient way to count subarrays without checking every possible combination, which would be too slow. A brute-force approach would check every possible subarray, leading to a time complexity of O(n^2). The optimized approach utilizes a hash map to store cumulative sums and their frequencies.

Given an array nums containing n + 1 integers where each integer is in the range [1, n] inclusive. There is only one repeated number in nums, return this repeated number. You are not allowed to modify the array and must use constant extra space. The problem is often framed to be solved without using extra space or a hash map, making it more challenging. The constraints point toward a solution that uses the array itself as a way to find the duplicate, similar to finding a cycle in a linked list.

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining. This problem is a classic and challenging one that requires careful thought about how to calculate the trapped water at each position. A simple way is to find the maximum height to the left and right for each bar and then calculate the water based on the minimum of these two heights. An even more optimal approach uses two pointers from both ends of the array, which allows for a single pass and constant space.

Given a string s, return the longest palindromic substring in s. A palindromic substring is a substring that reads the same backward as forward. The problem can be solved using dynamic programming or by expanding from the center. A brute-force approach would be to check every substring for palindromicity, which is highly inefficient. The dynamic programming approach builds a table to determine if substrings are palindromic. The center expansion method provides a more intuitive and often more performant solution.

Given a string s, return the number of palindromic substrings in it. A substring is a contiguous sequence of characters within a string. Unlike the previous problem, we need to count *all* palindromic substrings, not just the longest one. This can be solved by iterating through all possible substrings and checking if each one is a palindrome, but this is inefficient. A better approach again uses the "expand from center" method, which allows us to efficiently count all valid palindromes.

Given the root of a binary tree, determine if it is a valid binary search tree (BST). A valid BST is defined by the following rules: the left subtree of a node contains only nodes with values less than the node's value; the right subtree contains only nodes with values greater than the node's value; and both the left and right subtrees must also be valid BSTs. A common mistake is to only check a node's immediate children, but this is insufficient. The true check must consider the entire range of values from its parent nodes.

Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level). This problem is a classic application of Breadth-First Search (BFS). Instead of visiting nodes in a depth-first manner, we process all nodes at one level before moving on to the next. The structure of the problem naturally lends itself to using a queue data structure to manage the order of node visitation.

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes, p and q. The LCA is defined as the lowest node in the tree that has both p and q as descendants (where we allow a node to be a descendant of itself). This problem can be solved using various approaches, including a recursive solution that traverses the tree and returns the LCA when it finds both nodes in separate subtrees. It's a key concept in tree algorithms and is a common interview question.

Given the root of a binary search tree, and an integer k, return the kth smallest value (1-indexed) of all the values of the nodes in the tree. The property of a BST is that an in-order traversal yields the elements in sorted order. This is the key insight for solving this problem efficiently. A naive solution might be to perform an in-order traversal, store all elements in an array, and then return the k-th element. A more space-efficient solution avoids storing the entire list and simply counts the elements as they are visited.

You are given an integer array `coins` representing coins of different denominations and an integer `amount` representing a total amount of money. Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1. This is a classic dynamic programming problem. The optimal substructure and overlapping subproblems are key indicators for a DP solution.