100-interview-problems-checklist.md

100 Must attempt Problems for Coding Interview: Checklist

These 100 algorithmic problems will give you all core concepts and insights to solve Interview Problems at top tech companies like Google. This is an economical approach alternative to practicing 500+ problems over 3 to 4 years. If you are in the problem solving mindset, you can ace any interview. Save time and study smarter.

Array problems

1. Move Negative elements to front
   Move Negative elements to front is a simple problem that tests your knowledge of how to move elements across an array. These involve partition algorithms like Lomuto and Hoare Partition Scheme and has direct application in algorithms like QuickSort.
2. 2 Sum Problem
   2 Sum problem is a standard problem where you need to find two elements that add up to a given number. The advanced form is to find 2 numbers whose sum to closest to the target.
3. 3 Sum Problem
   In Interviews, you need to build on problems. 3 Sum problem tests your knowledge from the previous problem.
4. 3 Sum Closest Problem
   You have attempted the 2 Sum Closest problem variant but can you use similar ideas to solve 3 Sum Closest problem as well.
5. 4 Sum Problem
   4 Sum problem brings in new ideas and puts your knowledge from previous problems to test. If you are able to solve it, try the 4 Sum Closest problem on your own.

Linked List problems

1. Linked List with no NULLs
   This is an important topic that you must cover. In interviews at top companies like Google, you must implement Linked List without using NULL as this is the standard coding practice in Industry.
2. XOR Linked List
   XOR Linked List is the memory efficient version of Doubly Linked List. The concept of using XOR in such cases in very important for Interviews.
3. Linked List vs Array
   Understand the differences between Array and Linked List. Often, asked in initial rounds.
4. Binary Search on LL
   Binary Search is frequently used to solve Interview problem. Is Binary Search on Linked List equally efficient?.
5. Middle element in LL
   This problem of "Finding middle element of a Linked List" involves the technique of Slow and Fast pointer which is widely used.
6. Sort LL on absolute values
   Sort Linked List whose values have already been sorted on absolute values is a HOT interview problem.
7. Loop in Linked List
   There are 3 methods to detect a loop in Linked List.
8. Reverse a Linked List
   Reversing a Linked List may seem to be a simple problem but it uses 3 pointers. The challenge is to reverse a Linked List using 2 pointers. This involves the idea of XOR.
9. Cycle detection
   This is a HOT interview question. There are over 3 methods to detect Cycle in a Linked List and a follow-up question will to be remove a cycle.

Stack problems

1. 2 Stacks in one Array
   This problem of implementing 2 Stacks in 1 array is a simple problem. The main challenge is with the next problem.
2. N Stacks in one Array
   This problem is much more challenging problem. Understand the solution carefully as this is a HOT interview question now. Similar problem is N Queues in one Array.
3. Monotonic Stack
   Monotonic Stack is a core technique which exploits the properties of Stack to solve several challenging problems. Go through some example problems to hone your skills.
4. Merge Intervals
   The problem of Merge Intervals is a HOT interview problem. It is, often formulate as Time interval or duration of an event.

Queue problems

1. Delete middle element of Queue
   Delete middle element of Queue is a simple problem that tests how you can use core operations to build other operations. If needed, you should quickly revise the basics of Queue and types of Queue.
2. Monotonic Queue
   Monotonic Queue is a core technique using Queue to solve challenging problems like Daily Temperate problem.
3. Queue using Stack
   Implementing Queue using Stack data structure is another important Interview problem to test your concepts. The corresponding problem is to Implement Stack using Queue.
4. Next Larger / Smaller element in Array
   Next Larger / Smaller element in Array is a difficult interview problem that use the idea of Monotonic Queue.
5. Maximal Rectangle problem
   Maximal Rectangle problem is another difficult interview problem that use the idea of Monotonic Queue.

Binary Tree

1. Diameter and Height
   Finding the Diameter and Height of a Binary Tree is a simple yet core problem that everyone should be fluent in. Every few students know that the average height of a random Binary Tree is O(N^0.5) (see how?).
2. No NULL implementation
   Implementing Binary Tree with no NULLs is an approach that sets you apart from other candidates. Avoiding NULLs is Industry standard.
3. Largest Independent Set
   Finding the Largest Independent Set in Binary Tree is a problem that requires the application of Dynamic Programming. This is an important interview problem.
4. Copy Binary Tree
   Copying a Binary Tree with random pointers is a challenging problem. The trick is to handle the random pointers efficiently as the destination node may not have been processed. A related concept is Threaded Binary Tree.
5. Traversal of Binary Tree
   Zig Zag traversal and Level Order traversal of a Binary Tree is a problem that tests your Binary Tree handling skills. Different types of view of a Binary Tree is equally important problem.
6. Self-balancing Trees
   Self-balancing Trees are important concepts. Interviewers usually ask to list a few self-balancing binary trees. Some advanced levels may ask to explain the idea behind Red Black Tree.
7. Spreadsheet
   A HOT interview question is to design a spreadsheet / Excel sheet. This ivolve the idea of using Binary Tree.

Trie problems

1. Maximum XOR of two numbers
   This problem of finding the Maximum XOR of two numbers involve the use of Trie data structure which is not obvious from the problem statement.
2. Longest Common Suffix
   This is a HOT interview problem. Finding the Longest Common Suffix cannot be done efficiently using Trie. Similarly, you can solve the Longest Common Prefix problem.
3. All Valid Word Breaks of a Sentence
   Word Break Problem is a standard problem that involve the use of DP and Greedy algorithms. This variant: All Valid Word Breaks of a Sentence use Trie to solve it optimally.
4. Autocomplete feature
   Autocomplete feature is the most common feature of True data structure and Interviews revolve around this specific application.

Hash Map / Set

1. Collision Resolution
   There are different Collision Resolution techniques in a Hash Set and is frequently asked in Interviews.
2. LFU (Least Frequently Used) Cache
   Designing LFU (Least Frequently Used) Cache is a HOT interview question that involve the use of Hash Map. Another related problem is to design Least Recently Used (LRU) Cache.
3. Quadratic Probing
   The concept of Quadratic Probing and Linear Probing are frequently asked in Interviews.
4. Hash Functions
   Knowing multiple examples of Hash Functions is important for Interview as it is the fundamental component of Hash Set. You may need to hash an array or set.
5. **All Oone Data Structure**<br> This problem is about designing a custom Data Structure. These type of problems are HOT in interview. Try: [All Oone Data Structure](https://iq.opengenus.org/all-oone-data-structure/).

Sorting Algorithms

1. Search in Sorted 2D matrix
   The problem to Search an element in Sorted 2D matrix is a HOT interview problem.
2. Quick Sort
   Quick Sort is the most important topic in Sorting. Revise Time Complexity of Quick Sort, Median of Medians algorithm. Practice these MCQs for Interviews.
3. Hybrid Sorting Algorithm
   The concept of Hybrid Sorting presents to the Interviewer that you understand how real-world algorithms are designed. There is no single algorithm that works best for all cases.
4. Radix Sort
   Knowing a few Non-comparison based sorting algorithms is important and Radix Sort is a strong example. Analyze Time Complexity for Non-Comparison based Sorting algorithm.
5. Sort on Linked List
   Sorting on array and linked list are two different things. One may work well on array but not on Linked List and vice versa. Insertion sort on Linked List is a must.

Mathematical Algorithms

1. Analyze Algorithms
   Having an overview of Mathematics for Analyzing Algorithms is a fundamental skill that you should have.
2. Permutation
   Permutation is a HOT interview questions. Problems like K-th permutation, Lexicographical Next Permutation, Heap's algorithm for generating permutations and Counting derangements are must practice problems.
3. N-th root of a number
   There are 3 mainstream algorithms to find the N-th root of a number which everyone should have an idea of. You can also use Binary Search to find Square Root and Cube Root of a number.
4. Regula Falsi Method
   Regula Falsi Method and Newton Raphson Method are used to find root of a Polynomial.
5. Find GCD
   Binary GCD algorithm or Stein's algorithm is the most basic algorithm to find GCD of numbers efficiently. Euclidean Algorithm is an efficient alternative.
6. Integer Factorization
   There are multiple Integer Factorization Algorithms and Pollard's rho algorithm for factorization is a must.
7. Generate 0 and 1
   This is a HOT interview problem. Generate 0 and 1 with 25% and 75% probability using standard random functions.
8. Swap two numbers
   This is a HOT MCQ interview problem. There are over 6 different techniques to swap two numbers.

String Algorithms

1. Sub-strings of a string
   This is more like a brute force approach but candidates fail to implement or design an algorithm to generate all sub-strings of a string. This will help you solve most standard problems.
2. Number of palindromic substrings
   There are over 4 algorithms to find the Number of palindromic substrings in a string which involves use of Dynamic Programming and Modifed Manacher’s algorithm.
3. Pattern Search
   This is often asked in last Interview rounds at FAANG. KMP algorithm is the standard technique while Aho Corasick Algorithm helps you generalize the problem (asked frequently). Rabin-Karp Pattern Searching Algorithm is another efficient algorithm.
4. String Matching
   The concept of String Hashing and Rolling Hash is important in String Matching as it takes O(N) time to match a string but only O(1) time to match an integer. Shift OR algorithm for String Matching and String Matching using Bitset is a MUST for Interviews.
5. Sorted order of characters
   The problem Alien Dictionary problem: Sorted order of characters is a HOT interview problem involving the concept of Topological Sort.

Dynamic Programming

1. Basic problems on DP
   Standard DP problems that are common in Interviews are: Longest Geometric Progression, Calculate Binomial Coefficient and Coin Change Problem.
2. Shortest Path with k edges
   This is a HOT interview problem where DP is applied on Graph problem. Finding the Shortest Path with k edges and Number of paths with k edges with Dynamic Programming is a must practice.
3. Assembly Line Scheduling
   Scheduling problems are HOT interview problems. Assembly Line Scheduling using DP is a must. Similarly, Weighted Job scheduling problem is a variant that is popular in Interviews.
4. Knapsack Problem
   Knapsack Problem is one of the most common Interview problems. 0-1 Knapsack Problem is a variant that uses Dynamic Programming.
5. Box Stacking Problem
   Box Stacking Problem is a common problem for FAANG interviews. A variant of this is asked in every 3 out of 4 interviews.
6. Travelling Salesman Problem
   Travelling Salesman Problem and its variants are frequently asked in Interviews. It involves DP and bitmasking concepts. This is NP-Complete problem.

Greedy Algorithms

1. Activity Selection Problem
   Activity Selection Problem is one of the important problems where Greedy Algorithm is the direct solution. A variant of this: Scheduling tasks to Minimize Lateness is a critical Interview problem.
2. Egyptian Fraction Problem
   Egyptian Fraction Problem is an important Interview problem that lies at the intersection of Mathematical and Greedy Algorithms.
3. Fractional Knapsack Problem
   Fractional Knapsack Problem is a variant of Knapsack Problems that can be solved using Greedy Algorithms.
4. Largest Cube Formed
   The problem of Largest Cube Formed by deleting digits is interesting because of Time Complexity Analysis which many may get wrong in Interviews. It is O(N1/3 logN logN).
5. Maximal Clique
   Greedy Algorithms are also applied on Graph based problems. Finding Single Maximal Clique is a challenging Interview problem that is asked.
6. Fitting Shelves Problem
   This problem of Fitting Shelves is HOT interview problem requiring Greedy Algorithm.

Backtracking problems

1. Backtracking Algorithm for Sudoku
   Solving Sudoku using Backtracking is a standard technique though the implementation strategy is challenging in an Interview setting.
2. 8 Queens Problem
   Solving 8 Queens Problem using Backtracking is yet another important Interview problem. In similar chess setting, MCQs on number of possibilities of a given condition are asked frequently.
3. Subset Sum Problem
   Subset Sum Problem is a very common problem and many try to solve it using DP. Very few practice a variant where Backtracking is applied on Subset Sum Problem.
4. Knight's Tour Problem
   In case of problems dealing with Chess, Backtracking is a potential technique. Solving Knight's Tour Problem is important for Interviews and involve Backtracking and Warnsdorff's algorithm.
5. Word Break Problem
   Word Break Problem is an important Interview problem that involve concepts like Backtracking and Dynamic Programming.

Divide and Conquer

1. Closest Pair of Points
   Closest Pair of Points is the most important Interview Problem based on Geometry and uses the concept of Divide and Conquer to solve it.
2. Karatsuba Algorithm
   Very few realize that there are algorithms that optimized fundamental operations like Multiplication. Karatsuba Algorithm uses the concept of Divide and Conquer to multiply two number efficiently.
3. Floor in sorted array
   Finding floor in sorted array is an easy problem that is asked in Interviews. Having a good hold on Binary Search is a must.
4. Elements with difference K
   Finding 2 elements with difference K in a sorted array is a fundamental problem that many get wrong.
5. Peak Element in an Array
   The problem of finding Peak Element in an Array tests your understanding of Divide and Conquer technique.

Decrease and Conquer

1. Fake Coin Problem
   Fake Coin Problem is the most frequently asked Interview Problem that involve the concept of Decrease and Conquer. Very few use this technique.
2. Basics of Decrease & Conquer
   Revise the basics of Decrease and Conquer along with overview of fundamental problems.

Graph Algorithms

1. Islands Problem
   Number of Islands in MxN matrix (of 0 and 1) and Making A Large Island by changing one 0 to 1 are HOT interview problems. This involve the concept of BFS and DFS.
2. Transitive Closure Of A Graph
   Transitive Closure Of A Graph using Graph Powering is a core concept that helps to solve several challenging interview problems.
3. Dijkstra's algorithm
   Dijkstra's algorithm will help you solve shortest path problems. Time Complexity of Dijkstra's algorithm is a HOT interview problem.
4. Topological Sort
   Topological Sort is used to order nodes in a Graph linearly. There are multiple ways to implement Topological Sort like using BFS, using DFS and Kahn's Algorithm. Understand the applications to understand the potential.
5. Bridges in Graph
   The problem of finding all bridges in a Graph is a hot Interview topic.
6. Hamiltonian Path & Cycle (+ Eulerian)
   The concept of Hamiltonian Cycle and Hamiltonian Path is critical for Interviews. Remember this is a NP-Hard problem but it is important to identify when an interview problem requires Hamiltonian Path (a path that goes through all nodes in the graph once).The alternative concept is Eulerian path which is a path that covers all edges in the graph. It can be found efficiently (not NP-Hard) using algorithms like Fleury's Algorithm.
7. Count all paths
   Finding all paths is a way to count the paths but there exists other optimal ways where we can find the the total count without finding the actual paths.
8. Minimum Spanning Tree
   The concept of Minimum Spanning Tree is important. Kruskal Minimum Spanning Tree Algorithm and Prim Minimum Spanning Tree Algorithm are two core algorithms to find MST. Several graph based problems can be solved easily using MST like the Water Distribution problem in a village.

Computational Geometry

1. Number of integral points
   This problem of finding the Number of integral points between two points is a basic Interview problem. This involves Pick's theorem. A variant is Number of Integral points inside a triangle.
2. Oriented area of a triangle
   Oriented area of a triangle is an important Interview problem for Computational Geometry.
3. Furthest Pair of Points
   Closest Pair of Points is a standard problem yet Furthest Pair of Points is becoming a common questions in Interviews. It involves Rotating Calipers method.

Game Theory

1. Game of Kayle
   Game Theory problems are rare in Interviews but there are 2 concepts that are tested. Sprague-Grundy Theorem and Game of Kayle is one core concept.

Time Complexity Analysis

1. Dynamic Array
   Time Complexity Analysis of Dynamic Array is a HOT interview questions. Candidates are asked how it works better than standard Array.
2. Multiplication
   This is a tricky interview question. Many candidate think multiplication is a simple operation but it is not. Understanding the Time Complexity Analysis of Multiplication is important.
3. Interpolation Search
   Binary Search is a common theme among interviews and Time Complexity of Interpolation Search is a HOT follow-up question in such cases.

Advanced problems

1. Range Minimum query
   The problem of Range Minimum query is common in advanced Interview rounds in FAANG. This can be solved using Segment Tree and Square Root Decomposition.
2. Distinct Elements
   The problem of finding Number of Distinct elements in a range is a HOT interview problem. A follow-up interview question is to support single element updates.
3. Count inversions in array
   This is another HOT interview problem in advanced rounds: Count inversions in an array. This is solved using the idea of Fenwick Tree.
4. Longest Increasing Subsequence
   The problem of Longest Increasing Subsequence is a standard problem that is solved using Binary Search and Dynamic Programming. The challenge is to use Fenwick Tree to solve LIS problem. 2 follow-up questions are to find Longest Common Increasing Subsequence and Longest Increasing Consecutive Subsequence.

---

Generated by OpenGenus. Updated on 2023-11-27