Top 50 Searching Problems of DSA for Programming Interviews

Table of Contents#

1. Arrays
2. Strings
3. Linked Lists
4. Stacks & Queues
5. Trees
6. Graphs
7. Dynamic Programming
8. Sorting & Searching
9. Greedy Algorithms
10. Bit Manipulation
11. References

1. Arrays#

Arrays are the building blocks of DSA, and interviewers often use them to test foundational concepts like iteration, hashing, and two-pointer techniques.

1.1 Two Sum#

Problem Statement: Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
Why It’s Important: Tests your ability to optimize from brute-force (O(n²)) to O(n) time using hash maps.
Approach Hint: Use a hash map to store elements and their indices as you iterate. For each element num, check if target - num exists in the map.

1.2 Best Time to Buy and Sell Stock#

Problem Statement: You are given an array prices where prices[i] is the price of a stock on the i-th day. Find the maximum profit you can achieve by buying on one day and selling on a later day.
Why It’s Important: Teaches one-pass optimization and tracking of minimum/maximum values in real time.
Approach Hint: Track the minimum price encountered so far and compute the profit for each subsequent day. Update the maximum profit if the current profit exceeds it.

1.3 Contains Duplicate#

Problem Statement: Given an integer array nums, return true if any value appears at least twice, and false if every element is distinct.
Why It’s Important: Tests understanding of time-space tradeoffs (sorting vs. hash sets).
Approach Hint: Use a hash set to store seen elements. If an element is encountered again, return true; otherwise, return false after processing all elements.

1.4 Product of Array Except Self#

Problem Statement: Given an integer array nums, return an array answer such that answer[i] is equal to the product of all elements of nums except nums[i].
Why It’s Important: Challenges you to avoid division and optimize space (O(1) extra space, excluding output).
Approach Hint: Compute prefix products (product of elements before i) and suffix products (product of elements after i). Multiply prefix and suffix for each index to get the result.

1.5 Maximum Subarray#

Problem Statement: Find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Why It’s Important: Introduces dynamic programming and Kadane’s algorithm, a cornerstone for subarray problems.
Approach Hint: Use Kadane’s algorithm: track the maximum sum ending at the current position (current_max) and the global maximum sum (global_max). Update current_max as max(nums[i], current_max + nums[i]).

2. Strings#

Strings test your ability to manipulate sequences, handle edge cases, and use efficient algorithms for pattern matching or transformation.

2.1 Reverse a String#

Problem Statement: Reverse a string in-place (modify the input array directly) or return a new reversed string.
Why It’s Important: Tests two-pointer technique and understanding of mutable vs. immutable data types.
Approach Hint: Use two pointers (start and end of the string) and swap characters until they meet in the middle.

2.2 Valid Palindrome#

Problem Statement: Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
Why It’s Important: Teaches preprocessing (filtering non-alphanumeric characters) and two-pointer validation.
Approach Hint: Convert the string to lowercase, filter out non-alphanumeric characters, then use two pointers to check if the string reads the same forwards and backwards.

2.3 Longest Common Prefix#

Problem Statement: Write a function to find the longest common prefix string amongst an array of strings. If there is no common prefix, return an empty string.
Why It’s Important: Tests vertical/horizontal scanning and edge-case handling (e.g., empty input, single string).
Approach Hint: Compare characters of the first string with all other strings. Stop at the first mismatched character; the prefix up to that point is the answer.

2.4 String to Integer (atoi)#

Problem Statement: Implement the atoi function, which converts a string to a 32-bit signed integer.
Why It’s Important: Tests handling of edge cases (whitespace, signs, overflow, invalid characters).
Approach Hint: Skip whitespace, check for sign, read digits while converting to integer, and clamp the result to the 32-bit signed range [-2³¹, 2³¹ - 1].

2.5 Longest Substring Without Repeating Characters#

Problem Statement: Given a string s, find the length of the longest substring without repeating characters.
Why It’s Important: Introduces the sliding window technique with a hash set to track window boundaries.
Approach Hint: Use a sliding window with left and right pointers. Expand the right pointer, and if a duplicate is found, move the left pointer to the right of the last occurrence of the duplicate.

3. Linked Lists#

Linked lists test your understanding of pointers, recursion, and memory management—critical for low-level system design.

3.1 Reverse a Linked List#

Problem Statement: Reverse a singly linked list.
Why It’s Important: Fundamental for understanding pointer manipulation and recursion.
Approach Hint: Iterative: Use three pointers (prev, current, next) to reverse links. Recursive: Reverse the rest of the list first, then adjust pointers for the current node.

3.2 Merge Two Sorted Lists#

Problem Statement: Merge two sorted linked lists into a single sorted linked list.
Why It’s Important: Tests dummy nodes, traversal, and merge logic (foundational for merge sort).
Approach Hint: Use a dummy node to simplify edge cases. Compare nodes from both lists, append the smaller one to the result, and advance the corresponding pointer.

3.3 Detect Cycle in a Linked List#

Problem Statement: Determine if a linked list has a cycle in it.
Why It’s Important: Introduces Floyd’s Tortoise and Hare algorithm (two pointers with different speeds).
Approach Hint: Use slow (1 step) and fast (2 steps) pointers. If they meet, a cycle exists; if fast reaches null, no cycle.

3.4 Remove Nth Node From End of List#

Problem Statement: Given a linked list, remove the n-th node from the end of the list and return its head.
Why It’s Important: Tests two-pointer technique to avoid multiple traversals.
Approach Hint: Use a dummy node and two pointers. Move the fast pointer n steps ahead, then move both pointers until fast reaches the end. The slow pointer will be at the node before the target.

3.5 Palindrome Linked List#

Problem Statement: Check if a singly linked list is a palindrome.
Why It’s Important: Combines reversing a linked list and two-pointer traversal.
Approach Hint: Find the middle of the list (slow/fast pointers), reverse the second half, then compare the first and reversed second halves.

4. Stacks & Queues#

Stacks (LIFO) and queues (FIFO) are essential for problems involving order-dependent operations (e.g., parentheses matching, breadth-first search).

4.1 Valid Parentheses#

Problem Statement: Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
Why It’s Important: Classic stack application for matching nested structures.
Approach Hint: Use a stack to track opening brackets. For each closing bracket, check if it matches the top of the stack. If not, return false.

4.2 Implement Stack using Queues#

Problem Statement: Implement a stack using only two queues.
Why It’s Important: Tests understanding of stack/queue properties and tradeoffs (push vs. pop efficiency).
Approach Hint: Use two queues q1 and q2. For push, add to q1. For pop, transfer all elements from q1 to q2 except the last, then swap q1 and q2.

4.3 Min Stack#

Problem Statement: Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
Why It’s Important: Tests auxiliary data structures to track metadata (e.g., minimum values).
Approach Hint: Use a main stack and a min stack. The min stack stores the minimum value up to each position in the main stack.

4.4 Largest Rectangle in Histogram#

Problem Statement: Given an array of integers heights representing the histogram’s bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.
Why It’s Important: Advanced stack application for finding boundaries (previous and next smaller elements).
Approach Hint: Use a stack to track bar indices. For each bar, calculate the area using the stack to find the previous smaller bar and current index as the next smaller bar.

4.5 Sliding Window Maximum#

Problem Statement: Given an array nums and an integer k, return the maximum sliding window of size k.
Why It’s Important: Introduces deque (double-ended queue) for efficient window management.
Approach Hint: Use a deque to store indices of elements in the current window, maintaining them in decreasing order. The front of the deque is the maximum for the window.

5. Trees#

Trees (especially binary trees) test recursion, traversal techniques, and problem decomposition.

5.1 Maximum Depth of Binary Tree#

Problem Statement: Given the root of a binary tree, return its maximum depth (number of nodes along the longest path from root to leaf).
Why It’s Important: Fundamental for understanding tree traversal (recursion or BFS).
Approach Hint: Recursive: max(depth(left), depth(right)) + 1. Iterative: Use BFS with a queue to track levels.

5.2 Validate Binary Search Tree#

Problem Statement: Determine if a binary tree is a valid binary search tree (BST), where left < root < right for all nodes.
Why It’s Important: Tests understanding of BST properties and in-order traversal.
Approach Hint: Use in-order traversal (should yield sorted values) or track valid ranges (min, max) for each node.

5.3 Symmetric Tree#

Problem Statement: Check if a binary tree is symmetric around its center.
Why It’s Important: Tests recursive comparison of subtrees and mirroring logic.
Approach Hint: Recursive: Compare left subtree of left node with right subtree of right node, and vice versa. Iterative: Use a queue to compare nodes in pairs.

5.4 Invert Binary Tree#

Problem Statement: Invert a binary tree (swap left and right children of every node).
Why It’s Important: Simple yet iconic problem for recursion and tree manipulation.
Approach Hint: Recursive: Swap left and right children, then recursively invert left and right subtrees. Iterative: Use a queue to process nodes level by level.

5.5 Lowest Common Ancestor (LCA) of a Binary Tree#

Problem Statement: Find the lowest common ancestor of two given nodes in a binary tree.
Why It’s Important: Tests tree traversal and backtracking to find common ancestors.
Approach Hint: Recursive: If current node is p or q, return it. Otherwise, search left and right subtrees. If both return non-null, current node is LCA; else, return the non-null result.

6. Graphs#

Graphs model relationships between entities and test algorithms like BFS, DFS, and topological sorting.

6.1 Number of Islands#

Problem Statement: Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.
Why It’s Important: Classic DFS/BFS problem for connected component detection.
Approach Hint: Iterate through each cell. If it’s a '1', increment the island count and perform DFS/BFS to mark all connected '1's as visited (e.g., set to '0').

6.2 Course Schedule#

Problem Statement: There are numCourses courses to take, labeled 0 to numCourses-1. Given prerequisites [[a,b]] (a requires b), determine if it’s possible to finish all courses.
Why It’s Important: Tests topological sorting and cycle detection in directed graphs.
Approach Hint: Use Kahn’s algorithm (BFS) to compute in-degrees and process nodes with zero in-degree. If all nodes are processed, no cycle exists.

6.3 Clone Graph#

Problem Statement: Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph.
Why It’s Important: Tests graph traversal with a hash map to track cloned nodes.
Approach Hint: Use DFS or BFS. For each node, create a clone, store it in a hash map, and recursively clone its neighbors.

6.4 Pacific Atlantic Water Flow#

Problem Statement: Given an m x n matrix of non-negative integers representing heights, return the list of cell coordinates where water can flow to both the Pacific and Atlantic oceans.
Why It’s Important: Tests multi-source BFS/DFS to find reachable regions.
Approach Hint: Perform BFS/DFS from Pacific (top/left edges) and Atlantic (bottom/right edges) to mark reachable cells. The intersection of these sets is the answer.

6.5 Shortest Path in Binary Matrix#

Problem Statement: Given an n x n binary matrix, find the shortest path from top-left to bottom-right, moving to adjacent (8-directional) cells with value 0.
Why It’s Important: Tests BFS for shortest path in unweighted grids with multiple directions.
Approach Hint: Use BFS with a queue to track positions and distances. Mark visited cells to avoid revisiting.

7. Dynamic Programming (DP)#

DP solves complex problems by breaking them into subproblems and storing intermediate results (memoization).

7.1 Climbing Stairs#

Problem Statement: You are climbing a staircase. It takes n steps to reach the top. Each time you can climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Why It’s Important: Intro to DP with overlapping subproblems (fibonacci-like recurrence).
Approach Hint: dp[i] = dp[i-1] + dp[i-2] (ways to reach step i = ways to reach i-1 + ways to reach i-2). Use iterative DP with O(1) space.

7.2 Coin Change#

Problem Statement: Given an array of coins and an amount, return the fewest number of coins needed to make that amount. If impossible, return -1.
Why It’s Important: Tests unbounded knapsack DP and handling of minimum values.
Approach Hint: dp[i] = min coins for amount i. Initialize dp[0] = 0, and for each amount, iterate coins to update dp[i] = min(dp[i], dp[i - coin] + 1).

7.3 Longest Increasing Subsequence (LIS)#

Problem Statement: Given an integer array nums, return the length of the longest strictly increasing subsequence.
Why It’s Important: Tests O(n²) DP and optimized O(n log n) approaches (binary search).
Approach Hint: DP: dp[i] = length of LIS ending at i. For each i, compare with all j < i and update dp[i]. Optimized: Use a list to track the smallest possible tail of increasing subsequences.

7.4 Palindromic Substrings#

Problem Statement: Given a string s, return the number of palindromic substrings in it.
Why It’s Important: Tests expanding around centers (for odd/even length palindromes) or DP for substring problems.
Approach Hint: Expand around each character (odd length) and each pair of characters (even length), counting valid palindromes.

7.5 Edit Distance#

Problem Statement: Given two strings word1 and word2, return the minimum number of operations (insert, delete, replace) required to convert word1 to word2.
Why It’s Important: Classic DP problem with a 2D table to track subproblem solutions.
Approach Hint: dp[i][j] = min operations to convert word1[0..i-1] to word2[0..j-1]. If word1[i-1] == word2[j-1], dp[i][j] = dp[i-1][j-1]; else, min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1.

8. Sorting & Searching#

Sorting and searching algorithms are the backbone of efficient data processing.

8.1 Merge Intervals#

Problem Statement: Given an array of intervals [[start1, end1], [start2, end2], ...], merge all overlapping intervals.
Why It’s Important: Tests sorting and greedy merging of intervals.
Approach Hint: Sort intervals by start time. Iterate through intervals, merging with the last merged interval if they overlap.

8.2 Search in Rotated Sorted Array#

Problem Statement: Given a sorted array nums rotated at some pivot, search for a target value. Return its index or -1.
Why It’s Important: Tests modified binary search to handle rotated order.
Approach Hint: Determine if the left or right half is sorted. If target is in the sorted half, search there; else, search the other half.

8.3 Find First and Last Position of Element in Sorted Array#

Problem Statement: Given a sorted array of integers, find the starting and ending position of a given target value.
Why It’s Important: Tests binary search for boundary conditions (first and last occurrence).
Approach Hint: Use two binary searches: one to find the first index where nums[i] >= target, and another for nums[i] > target (adjust to get the last index).

8.4 Kth Largest Element in an Array#

Problem Statement: Find the k-th largest element in an unsorted array.
Why It’s Important: Tests quickselect algorithm (average O(n) time) or heap usage (O(n log k) time).
Approach Hint: Quickselect: Partition the array around a pivot. If the pivot’s index is n - k, return it. Else, recurse on the left or right subarray.

8.5 Median of Two Sorted Arrays#

Problem Statement: Given two sorted arrays nums1 and nums2 of size m and n, return the median of the two sorted arrays.
Why It’s Important: Advanced binary search to find the median in O(log(min(m, n))) time.
Approach Hint: Partition both arrays such that the left partition has elements <= right partition. The median is derived from the maximum of left elements and minimum of right elements.

9. Greedy Algorithms#

Greedy algorithms make locally optimal choices to find a global optimum, often used for optimization problems.

9.1 Jump Game#

Problem Statement: Given an array of non-negative integers nums, you start at the first index. Each element represents the maximum jump length. Determine if you can reach the last index.
Why It’s Important: Tests greedy selection of the farthest reachable index.
Approach Hint: Track the maximum reachable index. Iterate through the array; if current index exceeds max reach, return false. Update max reach as max(max_reach, i + nums[i]).

9.2 Activity Selection Problem#

Problem Statement: Given n activities with start and end times, select the maximum number of non-overlapping activities.
Why It’s Important: Classic greedy problem for interval scheduling.
Approach Hint: Sort activities by end time. Select the first activity, then repeatedly select the next activity that starts after the previous one ends.

9.3 Gas Station#

Problem Statement: There are n gas stations arranged in a circle. Each station has gas[i] gas, and it costs cost[i] to travel from station i to i+1. Find the starting station where you can complete a circuit.
Why It’s Important: Tests greedy tracking of total gas and current tank.
Approach Hint: If total gas < total cost, return -1. Else, iterate to find the start station where the cumulative gas never drops below zero.

9.4 Minimum Number of Coins#

Problem Statement: Given a value V and coins of denominations [c1, c2, ..., cn], find the minimum number of coins that make up V.
Why It’s Important: Greedy approach works for canonical coin systems (e.g., US coins).
Approach Hint: Sort coins in descending order. Take as many of the largest coin as possible, then proceed to smaller coins.

9.5 Interval Scheduling (Maximize Profit)#

Problem Statement: Given intervals with start, end, and profit, select non-overlapping intervals to maximize profit.
Why It’s Important: Combines greedy selection with binary search for optimal substructure.
Approach Hint: Sort intervals by end time. Use DP where dp[i] = max(dp[i-1], profit[i] + dp[p[i]]), where p[i] is the last non-overlapping interval before i.

10. Bit Manipulation#

Bit manipulation tests low-level thinking and optimization using bitwise operations (AND, OR, XOR, shifts).

10.1 Number of 1 Bits#

Problem Statement: Write a function that returns the number of '1' bits in the binary representation of an integer.
Why It’s Important: Tests Brian Kernighan’s algorithm (efficiently count set bits).
Approach Hint: n & (n - 1) clears the least significant set bit. Repeat until n is 0, counting iterations.

10.2 Reverse Bits#

Problem Statement: Reverse the bits of a 32-bit unsigned integer.
Why It’s Important: Tests bitwise shifts and masking.
Approach Hint: Initialize result to 0. For each bit from 0 to 31, shift result left, add the least significant bit of n, then shift n right.

10.3 Single Number#

Problem Statement: Given a non-empty array of integers, every element appears twice except one. Find that single one.
Why It’s Important: Tests XOR properties (a ^ a = 0, a ^ 0 = a).
Approach Hint: XOR all elements. Duplicates cancel out, leaving the single number.

10.4 Missing Number#

Problem Statement: Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range missing from the array.
Why It’s Important: Tests XOR or sum-based approaches to find missing elements.
Approach Hint: XOR: res = n, then XOR res with i and nums[i] for all i. Sum: n*(n+1)/2 - sum(nums).

10.5 Subsets#

Problem Statement: Given an integer array nums, return all possible subsets (the power set).
Why It’s Important: Tests bit masking to generate all subsets.
Approach Hint: For n elements, there are 2ⁿ subsets. Each bitmask from 0 to 2ⁿ - 1 represents a subset (bit i indicates inclusion of nums[i]).

References#

• LeetCode: Top Interview Questions
• GeeksforGeeks: DSA Problems
• Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
• Gayle Laakmann McDowell. (2015). Cracking the Coding Interview (6th ed.). CareerCup, LLC.

This curated list of 50 DSA problems covers the core concepts tested in interviews. Mastering these will not only boost your problem-solving skills but also give you the confidence to tackle unexpected questions. Happy coding! 🚀