DSA Questions - AdarshTheki/mern-stack-learn GitHub Wiki

DSA interview questions, categorized by topic.

  1. Arrays and Strings

    • Find the missing number in an array of size n containing numbers from 1 to n+1
    • Find the largest sum contiguous subarray (Kadane's Algorithm)
    • Given an array of integers, return indices of the two numbers such that they add up to a specific target (Two Sum )
    • Rotate an array by k steps to the right
    • Merge two sorted arrays
    • Check if a string is a palindrome
    • Implement an algorithm to find the longest common prefix among a set of strings
    • Find the first non-repeating character in a string
    • Find the length of the longest substring without repeating characters
    • Implement strStr() function (needle in a haystack problem )

  2. Linked Lists

    • Reverse a linked list
    • Detect a cycle in a linked list (Floyd’s Tortoise and Hare )
    • Find the middle of a linked list
    • Merge two sorted linked lists
    • Remove N-th node from the end of a linked list
    • Add two numbers represented by linked lists
    • Find the intersection point of two linked lists
    • Flatten a multilevel linked list
    • Sort a linked list (Merge Sort )
    • Check if a linked list is a palindrome

  3. Stacks and Queues

    • Implement a stack using arrays/linked lists
    • Implement a queue using arrays/linked lists
    • Evaluate a postfix expression
    • Implement a queue using two stacks
    • Implement a stack that supports push, pop, top, and retrieving the minimum element in constant time (Min Stack )
    • Check for balanced parentheses in an expression
    • Design a circular queue
    • Design a stack that supports getMax() in O(1) time
    • Implement a monotonic queue
    • Implement an LRU Cache

  4. Trees and Graphs

    • Implement tree traversal methods (in-order, pre-order, post-order)
    • Level order traversal of a binary tree
    • Find the height of a binary tree
    • Check if a binary tree is a valid binary search tree (BST)
    • Find the lowest common ancestor (LCA) of two nodes in a BST
    • Serialize and deserialize a binary tree
    • Check if two trees are identical
    • Find the diameter of a binary tree
    • Implement Depth First Search (DFS) and Breadth First Search (BFS) for a graph
    • Find the shortest path in a graph (Dijkstra's Algorithm)
    • Detect a cycle in an undirected/directed graph
    • Topological sorting of a directed acyclic graph (DAG)
    • Implement a binary search tree (insert, delete, search)

  5. Recursion and Backtracking

    • Solve the Tower of Hanoi problem
    • Generate all subsets of a set (Power Set)
    • Solve the N-Queens problem
    • Generate all permutations of a string/array
    • Find all paths in a maze (Rat in a Maze problem)
    • Sudoku solver
    • Word search in a grid (backtracking approach)
    • Partition a set into two subsets such that the difference of subset sums is minimized
    • Count the number of ways to reach the nth stair using 1 or 2 steps
    • Print all possible combinations of r elements in a given array of size n

  6. Sorting and Searching

    • Implement Bubble Sort, Insertion Sort, Selection Sort
    • Implement Merge Sort and Quick Sort
    • Find the Kth largest/smallest element in an array
    • Binary Search implementation
    • Search in a rotated sorted array
    • Find the peak element in an array
    • Sort an array of 0s, 1s, and 2s (Dutch National Flag problem)
    • Find the majority element in an array (Moore's Voting Algorithm)
    • Search in a 2D matrix
    • Find the median of two sorted arrays

  7. Dynamic Programming

    • Find the nth Fibonacci number (with and without memoization)
    • 0/1 Knapsack Problem
    • Longest Common Subsequence (LCS)
    • Longest Increasing Subsequence (LIS)
    • Coin Change Problem
    • Word Break Problem
    • Maximum Subarray Sum (Kadane’s Algorithm)
    • Edit Distance between two strings
    • Palindrome Partitioning
    • Maximum Product Subarray

  8. Greedy Algorithms

    • Activity Selection Problem
    • Huffman Coding
    • Fractional Knapsack Problem
    • Job Sequencing Problem
    • Minimum Spanning Tree (Prim’s and Kruskal’s Algorithms)
    • Dijkstra’s Shortest Path Algorithm
    • Gas Station Problem
    • Coin Change Problem (using Greedy approach)
    • Interval Partitioning Problem
    • Optimal Merge Pattern

  9. Bit Manipulation

    • Check if a number is a power of two
    • Count the number of set bits in an integer
    • Find the single number in an array where every other number appears twice
    • Swap two numbers without using a temporary variable
    • Reverse bits of a given 32-bit unsigned integer
    • Find the two non-repeating elements in an array of repeating elements
    • Find the missing number in an array of size n containing numbers from 1 to n+1 using XOR
    • Check if two numbers have opposite signs
    • Multiply a number by 7 without using multiplication/division operator
    • Determine if a number is even or odd using bitwise operators

  10. Math and Number Theory

    • Check if a number is prime.
    • Find the greatest common divisor (GCD) of two numbers.
    • Count trailing zeroes in factorial of a number.
    • Find all prime numbers up to n (Sieve of Eratosthenes)
    • Calculate the power of a number (x^n) using an optimized approach.
    • Find the square root of a number using binary search.
    • Check if a number is a perfect square.
    • Find the largest prime factor of a number.
    • Check if a number is a palindrome (numeric)
    • Find the nth Fibonacci number using matrix exponentiation.

  11. Design and System-Level Questions

    • Design a data structure that supports insert, delete, search, and getRandom in constant time (O(1)).
    • Implement a LRU (Least Recently Used) cache.
    • Design a snake game with a moving snake and food items (2D grid).
    • Implement an autocomplete system.
    • Design a hit counter that counts the number of hits in the past 5 minutes.
    • Design a parking lot system.
    • Design a social media feed ranking algorithm.
    • Design a library management system.
    • Design a URL shortening service like Bitly.
    • Design a rate limiter.

  12. Miscellaneous

    • Find the median of a stream of integers.
    • Design a stack that supports push, pop, and retrieving the minimum element in constant time (Min Stack).
    • Find the maximum sum of non-adjacent elements in an array.
    • Generate all possible combinations of well-formed parentheses.
    • Implement a trie (prefix tree) and use it for efficient prefix search.
    • Check if a binary tree is a subtree of another binary tree.
    • Determine if two strings are anagrams of each other.
    • Merge k sorted linked lists into one sorted linked list.
    • Check if a binary tree is height-balanced.
    • Implement a sliding window maximum (maximum of all subarrays of size k).