DSA Interview Questions

Given an array of integers and a target sum, return indices of two numbers that add up to the target. You may assume that each input has exactly one solution.

Reverse a singly linked list iteratively and recursively. This is a fundamental linked list problem.

Given a string containing just the characters '(', ')', ', ', '[' and ']', determine if the input string is valid. Brackets must close in the correct order.

Find the contiguous subarray within an array which has the largest sum. This is solved efficiently using Kadane's algorithm.

Traverse a binary tree level by level from left to right using Breadth-First Search (BFS).

Find the length of the longest substring without repeating characters using sliding window technique.

Given a collection of intervals, merge all overlapping intervals.

Find the lowest common ancestor (LCA) of two nodes in a binary tree.

Determine if you can finish all courses given prerequisites. This is a graph cycle detection problem.

Design and implement a Least Recently Used (LRU) cache with O(1) time complexity for both get and put operations.

Implement binary search to find the index of a target value in a sorted array.

You're climbing a staircase with n steps. Each time you can climb 1 or 2 steps. How many distinct ways can you climb to the top?

Given an array, return an array where each element is the product of all elements except itself, without using division and in O(n) time.

Find the kth largest element in an unsorted array using QuickSelect algorithm.

Search for a target in a rotated sorted array in O(log n) time.

Given a string s and a dictionary of words, determine if s can be segmented into space-separated sequence of dictionary words.

Count the number of islands in a 2D grid where '1' represents land and '0' represents water.

Find the minimum number of coins needed to make up a given amount using unlimited coins of given denominations.

Determine if a binary tree is a valid Binary Search Tree (BST).

Given an elevation map where the width of each bar is 1, compute how much water can be trapped after raining.

Given a string s, return the first non-repeating character. If none exists, return -1.
Input: "swiss" → Output: 'w'

Check if a string containing {}, [], () is valid.
Input: "{'[()]'}" → Output: true

Return indices of two numbers that add up to target.
Input: [2,7,11,15], target = 9 → Output: [0,1]

Return true if t is an anagram of s.
Input: s = "anagram", t = "nagaram" → true

Return true if linked list has a cycle using Floyd's slow & fast pointer technique.
Time: O(n), Space: O(1)

Find maximum sum of any contiguous subarray of size k.
Input: [2,1,5,1,3,2], k=3 → Output: 9 (subarray [5,1,3])

Array of size n-1 contains numbers 1..n. Find the missing number.
Input: [1,2,4,5] → Output: 3

Find the longest common prefix among an array of strings.
Input: ["flower","flow","flight"] → Output: "fl"

Given API isBadVersion(version), find the first bad version.
Input: n = 10, bad = 4 → Output: 4

Compress a string by counting consecutive characters. Return original if compressed is longer.
Input: "aabcccccaaa" → Output: "a2b1c5a3"

Return length of longest substring without duplicate characters.
Input: "abcabcbb" → Output: 3 ("abc")

Find kth largest element in an unsorted array.
Input: [3,2,1,5,6,4], k = 2 → Output: 5

Group strings that are anagrams together.
Input: ["eat","tea","tan","ate","nat","bat"]
Output: [["eat","tea","ate"],["tan","nat"],["bat"]]

Find the contiguous subarray with the largest sum.
Input: [-2,1,-3,4,-1,2,1,-5,4] → Output: 6 (subarray [4,-1,2,1])

Return array where answer[i] is product of all elements except nums[i]. No division allowed.
Input: [1,2,3,4] → Output: [24,12,8,6]

Merge overlapping intervals.
Input: [[1,3],[2,6],[8,10]] → Output: [[1,6],[8,10]]

Find all unique triplets [nums[i], nums[j], nums[k]] that sum to 0.
Input: [-1,0,1,2,-1,-4] → [[-1,-1,2],[-1,0,1]]

Find two lines that together with x-axis form a container that holds the most water.
Input: [1,8,6,2,5,4,8,3,7] → Output: 49

Can string be segmented into dictionary words?
Input: s = "leetcode", wordDict = ["leet","code"] → true

Return the longest palindromic substring.
Input: "babad" → "bab" or "aba"

Implement a rate limiter that allows max N requests per second per user. Common in screening interviews.

Return all possible letter combinations from digits 2-9 (phone keypad).
Input: "23" → ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Return level order traversal of binary tree (left to right, level by level).

Given numCourses and prerequisites, return true if you can finish all courses.
This is essentially detecting if a directed graph has a cycle.

Implement a Trie with insert, search, and startsWith methods.

Count number of islands in a 2D grid where '1' is land and '0' is water.
Input: [["1","1","0"],["1","1","0"],["0","0","1"]] → Output: 2

Find minimum number of coins to make up the amount.
Input: coins = [1,2,5], amount = 11 → Output: 3 (5+5+1)

Rotate an n×n 2D matrix by 90 degrees clockwise in-place.

Return all elements of the matrix in spiral order.
Input: [[1,2,3],[4,5,6],[7,8,9]] → [1,2,3,6,9,8,7,4,5]

Given a reference to a node in a connected undirected graph, return a deep copy of the graph.

Return the k most frequent elements.
Input: nums = [1,1,1,2,2,3], k = 2 → Output: [1,2]

Design a Least Recently Used (LRU) cache with get and put operations in O(1) time.

Given n non-negative integers representing an elevation map, compute how much water can be trapped after raining.
Input: [0,1,0,2,1,0,1,3,2,1,2,1] → Output: 6

Find the largest rectangle area in a histogram.
Input: [2,1,5,6,2,3] → Output: 10

Find the minimum window in s which contains all characters of t.
Input: s = "ADOBECODEBANC", t = "ABC" → Output: "BANC"

Transform beginWord to endWord, changing one letter at a time. Each transformed word must be in wordList.
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] → 5

Merge k sorted linked lists into one sorted list.

Find the maximum path sum in a binary tree. Path can start and end at any node.
Input: [-10,9,20,null,null,15,7] → Output: 42 (15→20→7)

Design an algorithm to serialize and deserialize a binary tree.

Find the length of the longest valid parentheses substring.
Input: "(()" → 2, ")()())" → 4

Place N queens on an N×N chessboard such that no two queens attack each other.

Implement regex matching with '.' (matches any char) and '*' (matches zero or more of preceding element).
Input: s = "aab", p = "c*a*b" → true

Design a data structure that supports adding numbers and finding the median in O(log n) add, O(1) find.

Given a sorted dictionary of an alien language, find the order of characters.
Input: ["wrt","wrf","er","ett","rftt"] → "wertf"

Find the longest increasing path in a matrix.
Input: [[9,9,4],[6,6,8],[2,1,1]] → 4 (1→2→6→9)

Find minimum operations (insert, delete, replace) to convert word1 to word2.
Input: "horse", "ros" → 3

Return max value in each sliding window of size k.
Input: [1,3,-1,-3,5,3,6,7], k = 3 → [3,3,5,5,6,7]

Burst balloons to maximize coins. Burst balloon i to get nums[i-1] * nums[i] * nums[i+1] coins.
Input: [3,1,5,8] → 167