In the competitive landscape of technical interviews, mastering Data Structures and Algorithms (DSA) is crucial. Recruiters often focus on a candidate’s problem-solving skills and ability to think critically. To help you prepare, we’ve compiled a list of 40 commonly asked DSA questions, categorized for your convenience.
Arrays and Strings
- Find the Maximum Sum Subarray: Identify the contiguous subarray within a one-dimensional array that has the largest sum.
- Find All Substrings that are Palindromes: Write a program to list all the substrings of a given string that are palindromic.
- Implement the “Two Sum” Problem: Given an array of integers, return indices of the two numbers such that they add up to a specific target.
- Implement Kadane’s Algorithm for Maximum Subarray Sum: Use this algorithm to find the maximum sum of a contiguous subarray in an array.
- Find the Missing Number in an Array of Integers: In a given range, determine the missing integer in the array.
- Merge Two Sorted Arrays into One Sorted Array: Combine two sorted arrays while maintaining the sorted order.
- Check if a String is a Palindrome: Create a function to determine if a string reads the same forwards and backwards.
- Find the First Non-Repeating Character in a String: Identify the first character in a string that does not repeat.
- Write a Program to Remove Duplicates from a Sorted Array: Eliminate duplicates from a sorted array in-place.
Linked Lists
- Reverse a Linked List: Write a function to reverse a singly linked list.
- Detect a Cycle in a Linked List: Determine if a linked list contains a cycle.
- Find the Middle of a Linked List: Identify the middle node of a linked list.
- Merge Two Sorted Linked Lists: Combine two sorted linked lists into one sorted linked list.
- Implement a Stack Using Linked List: Create a stack data structure using a linked list.
- Find the Intersection Point of Two Linked Lists: Identify the node at which two linked lists intersect.
Stacks and Queues
- Implement a Stack Using an Array: Design a stack data structure with an array.
- Implement a Stack that Supports Push, Pop, Top, and Retrieving the Minimum Element: Enhance stack functionality with additional operations.
- Implement a Circular Queue: Design a queue that wraps around to the beginning when it reaches the end.
- Design a Max Stack: Create a stack that supports retrieving the maximum element in constant time.
- Design a Queue Using Stacks: Implement a queue using two stacks.
Trees and Binary Search Trees
- Find the Height of a Binary Tree: Calculate the height of a binary tree.
- Find the Lowest Common Ancestor of Two Nodes in a Binary Tree: Determine the lowest common ancestor of two nodes.
- Validate if a Binary Tree is a Valid Binary Search Tree: Check if a binary tree follows the properties of a binary search tree.
- Serialize and Deserialize a Binary Tree: Convert a binary tree to a string and vice versa.
- Implement an Inorder Traversal of a Binary Tree: Write a function for inorder traversal.
- Find the Diameter of a Binary Tree: Calculate the longest path between any two nodes in a binary tree.
- Convert a Binary Tree to its Mirror Tree: Create a mirror image of the binary tree.
Graphs
- Implement Depth-First Search (DFS): Write a DFS algorithm to traverse a graph.
- Implement Breadth-First Search (BFS): Write a BFS algorithm for graph traversal.
- Find the Shortest Path Between Two Nodes in an Unweighted Graph: Determine the shortest path using BFS.
- Detect a Cycle in an Undirected Graph Using DFS: Identify cycles in an undirected graph.
- Check if a Graph is Bipartite: Determine if a graph can be colored using two colors.
- Find the Number of Connected Components in an Undirected Graph: Count the connected components using DFS/BFS.
- Find Bridges in a Graph: Identify edges that, when removed, increase the number of connected components.
Sorting and Searching
- Implement (Bubble, Insertion, Selection, Merge) Sort: Write sorting algorithms for different sorting techniques.
- Implement Quicksort: Create a function to sort an array using the quicksort algorithm.
- Implement Binary Search: Develop a binary search function to find an element in a sorted array.
- Implement Interpolation Search: Design an interpolation search algorithm.
- Find the Kth Smallest Element in an Array: Identify the kth smallest element in an unsorted array.
- Count the Number of Inversions in an Array: Determine how many pairs of elements are out of order in the array.
Authored by: Rajat Gajbhiye on Linkedin
