DSA QUESTIONS (to practice programming)
Easy Difficulty (10 Problems)
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.
○ Example:
Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1] (because nums[0] + nums[1] = 2 + 7 = 9)
○ DSA Topic: Arrays, Hashing
○ Explanation: Use a hash map to store the difference between the target
and the current element. If the difference exists in the map, return the
indices.
2. Reverse a String
○ Problem Statement: Write a function to reverse a string in-place.
○ Example:
Input: s = "hello"
Output: "olleh"
○ DSA Topic: Strings, Two Pointers
○ Explanation: Use two pointers (one at the start and one at the end) to
swap characters until the entire string is reversed.
○
3. Valid Parentheses
○ Problem Statement: Given a string s containing just the characters (, ), {,
}, [, ], determine if the input string is valid.
○ Example:
Input: s = "()[]{}"
Output: true
○ DSA Topic: Stacks
○ Explanation: Use a stack to keep track of opening brackets. For every
closing bracket, check if it matches the top of the stack.
4. Merge Two Sorted Lists
○ Problem Statement: Merge two sorted linked lists and return them as a
single sorted list.
○ Example:
Input: l1 = [1, 2, 4], l2 = [1, 3, 4]
Output: [1, 1, 2, 3, 4, 4]
○ DSA Topic: Linked Lists, Two Pointers
○ Explanation: Use two pointers to traverse both lists and merge them in
sorted order.
○
5. Maximum Subarray
○ Problem Statement: Find the contiguous subarray (containing at least one
number) with the largest sum.
○ Example:
Input: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output: 6 (from subarray [4, -1, 2, 1])
○ DSA Topic: Arrays, Dynamic Programming (Kadane's Algorithm)
○ Explanation: Use Kadane's algorithm to keep track of the maximum
sum ending at each index.
○
6. Binary Search
○ Problem Statement: Implement binary search to find the index of a
target value in a sorted array.
○ Example:
Input: nums = [1, 2, 3, 4, 5], target = 3
Output: 2
○ DSA Topic: Arrays, Binary Search
○ Explanation: Repeatedly divide the array into two halves and search
for the target in the appropriate half.
○
7. Linked List Cycle
○ Problem Statement: Detect if a linked list has a cycle.
○ Example:
Input: head = [3, 2, 0, -4] (with a cycle)
Output: true
○ DSA Topic: Linked Lists, Two Pointers (Floyd's Cycle Detection)
○ Explanation: Use two pointers (slow and fast) to detect a cycle.
8. Count Primes
○ Problem Statement: Count the number of prime numbers less than a
non-negative number n.
○ Example:
Input: n = 10
Output: 4 (primes: 2, 3, 5, 7)
○ DSA Topic: Arrays, Sieve of Eratosthenes
○ Explanation: Use the Sieve of Eratosthenes algorithm to mark
non-prime numbers.
○
9. Palindrome Linked List
○ Problem Statement: Check if a linked list is a palindrome.
○ Example:
Input: head = [1, 2, 2, 1]
Output: true
○ DSA Topic: Linked Lists, Two Pointers
○ Explanation: Reverse the second half of the linked list and compare
it with the first half.
○
10. Remove Duplicates from Sorted Array
○ Problem Statement: Remove duplicates in-place from a sorted array
and return the new length.
○ Example:
Input: nums = [1, 1, 2]
Output: 2 (modified array: [1, 2])
○ DSA Topic: Arrays, Two Pointers
○ Explanation: Use two pointers to overwrite duplicates in-place.
Medium Difficulty (10 Problems)
11.Longest Substring Without Repeating Characters
○ Problem Statement: Find the length of the longest substring without
repeating characters.
○ Example:
Input: s = "abcabcbb"
Output: 3 (substring: "abc")
○ DSA Topic: Strings, Sliding Window, Hashing
○ Explanation: Use a sliding window with a hash set to track unique
characters.
○
12.Rotate Image
○ Problem Statement: Rotate an n x n 2D matrix by 90 degrees clockwise
in-place.
○ Example:
Input: matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
Output: [[7, 4, 1], [8, 5, 2], [9, 6, 3]]
○ DSA Topic: Arrays, Matrix Manipulation
○ Explanation: Transpose the matrix and then reverse each row.
○
13.Validate Binary Search Tree
○ Problem Statement: Check if a binary tree is a valid binary search tree
(BST).
○ Example:
Input: root = [2, 1, 3]
Output: true
○ DSA Topic: Trees, BST, Inorder Traversal
○ Explanation: Perform an inorder traversal and check if the sequence is
sorted.
○
14.Kth Largest Element in an Array
○ Problem Statement: Find the kth largest element in an unsorted array.
○ Example:
Input: nums = [3, 2, 1, 5, 6, 4], k = 2
Output: 5
○ DSA Topic: Arrays, Heaps, Quickselect
○ Explanation: Use a min-heap or the Quickselect algorithm to find the kth
largest element.
○
15.Merge Intervals
○ Problem Statement: Merge overlapping intervals in a list of intervals.
○ Example:
Input: intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
Output: [[1, 6], [8, 10], [15, 18]]
○ DSA Topic: Arrays, Sorting, Intervals
○ Explanation: Sort the intervals and merge overlapping ones.
○
16.Lowest Common Ancestor of a Binary Tree
○ Problem Statement: Find the lowest common ancestor (LCA) of two
nodes in a binary tree.
○ Example:
Input: root = [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4], p = 5, q =
1
Output: 3
○ DSA Topic: Trees, DFS
○ Explanation: Use DFS to traverse the tree and find the LCA.
○
17.Word Break
○ Problem Statement: Given a string s and a dictionary of words, determine
if s can be segmented into a space-separated sequence of dictionary
words.
○ Example:
Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true
○ DSA Topic: Dynamic Programming, Strings
○ Explanation: Use dynamic programming to check if the string can be
segmented.
○
18.Course Schedule
○ Problem Statement: Determine if you can finish all courses given
prerequisites represented as a directed graph.
○ Example:
Input: numCourses = 2, prerequisites = [[1, 0]]
Output: true
○ DSA Topic: Graphs, Topological Sorting
○ Explanation: Use topological sorting to detect cycles in the graph.
○
19.Find All Anagrams in a String
○ Problem Statement: Find all start indices of anagrams of string p in string
s.
○ Example:
Input: s = "cbaebabacd", p = "abc"
Output: [0, 6]
○ DSA Topic: Strings, Sliding Window, Hashing
○ Explanation: Use a sliding window to compare character counts.
○
20.Search in Rotated Sorted Array
○ Problem Statement: Search for a target value in a rotated sorted array.
○ Example:
Input: nums = [4, 5, 6, 7, 0, 1, 2], target = 0
Output: 4
○ DSA Topic: Arrays, Binary Search
○ Explanation: Modify binary search to handle the rotated array.
Hard Difficulty (10 Problems)
21.Trapping Rain Water
○ Problem Statement: Compute how much water can be trapped between
bars of different heights.
○ Example:
Input: height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
Output: 6
○ DSA Topic: Arrays, Two Pointers, Dynamic Programming
○ Explanation: Use two pointers or dynamic programming to calculate
trapped water.
○
22.Sliding Window Maximum
○ Problem Statement: Find the maximum in each sliding window of size k.
○ Example:
Input: nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
Output: [3, 3, 5, 5, 6, 7]
○ DSA Topic: Arrays, Sliding Window, Deque
○ Explanation: Use a deque to maintain the maximum in the current window.
○
23.Longest Consecutive Sequence
○ Problem Statement: Find the length of the longest consecutive sequence
of numbers in an unsorted array.
○ Example:
Input: nums = [100, 4, 200, 1, 3, 2]
Output: 4 (sequence: [1, 2, 3, 4])
○ DSA Topic: Arrays, Hashing
○ Explanation: Use a hash set to find sequences.
○
24.Serialize and Deserialize Binary Tree
○ Problem Statement: Design an algorithm to serialize and deserialize a
binary tree.
○ Example:
Input: root = [1, 2, 3, null, null, 4, 5]
Output: Serialized string and reconstructed tree.
○ DSA Topic: Trees, DFS, BFS
○ Explanation: Use DFS or BFS to serialize and deserialize the tree.
25.Minimum Window Substring
○ Problem Statement: Find the minimum window in s that contains all
characters of t.
○ Example:
Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
○ DSA Topic: Strings, Sliding Window, Hashing
○ Explanation: Use a sliding window to find the smallest substring
containing all characters of t.
○
26.Edit Distance
○ Problem Statement: Compute the minimum number of operations (insert,
delete, replace) to convert string s to string t.
○ Example:
Input: s = "horse", t = "ros"
Output: 3
○ DSA Topic: Dynamic Programming, Strings
○ Explanation: Use dynamic programming to compute the minimum edit
distance.
○
27.Regular Expression Matching
○ Problem Statement: Implement regular expression matching with support
for . and *.
○ Example:
Input: s = "aab", p = "c*a*b"
Output: true
○ DSA Topic: Dynamic Programming, Strings
○ Explanation: Use dynamic programming to handle pattern matching.
○
28.Maximum Profit in Job Scheduling
○ Problem Statement: Schedule jobs to maximize profit given start time, end
time, and profit.
○ Example:
Input: startTime = [1, 2, 3, 3], endTime = [3, 4, 5, 6], profit =
[50, 10, 40, 70]
Output: 120
○ DSA Topic: Dynamic Programming, Binary Search
○ Explanation: Use dynamic programming with binary search to maximize
profit.
29.Word Ladder
○ Problem Statement: Find the shortest transformation sequence from
beginWord to endWord using a dictionary.
○ Example:
Input: beginWord = "hit", endWord = "cog", wordList = ["hot",
"dot", "dog", "lot", "log", "cog"]
Output: 5 (path: "hit" -> "hot" -> "dot" -> "dog" -> "cog")
○ DSA Topic: Graphs, BFS
○ Explanation: Use BFS to find the shortest path in the word graph.
○
30.Median of Two Sorted Arrays
○ Problem Statement: Find the median of two sorted arrays.
○ Example:
Input: nums1 = [1, 3], nums2 = [2]
Output: 2.0
○ DSA Topic: Arrays, Binary Search
○ Explanation: Use binary search to partition the arrays and find the median.
