71 algorithm interview questions (with solutions and cheat sheet)

Algorithms questions and solutions with cheat sheet

If you're a software engineer preparing for a coding interview at a top tech company like Facebook, Google, or Amazon, you'll need to practice solving plenty of algorithm problems.

That's why we've compiled a comprehensive list of 71 typical questions grouped by type (DFS, BFS, sorting, etc.) and included links to high quality solutions.

We've also included the ultimate cheat sheet, giving you key information on space-time complexity for each algorithm at a glance.

Here's a summary of what you'll find below:

    1. Algorithms cheat sheet
    2. Depth-first search questions
    3. Breadth-first search questions
    4. Binary search questions
    5. Sorting questions
    6. Dynamic programming questions
    7. Greedy algorithm questions
    8. Backtracking questions
    9. Divide and conquer questions
    10. How to prepare for a coding interview

      Let's get into it!

      Click here to practice coding interviews with ex-FAANG interviewers

      1. The ultimate algorithms cheat sheet

      When you're preparing for coding interviews, it helps to have at least some of the key information in one place. We've created an 8-page cheat sheet, which you can use as a handy reference point for the 8 main algorithms.

      Click here

      Right, let's take a look at some typical algorithm questions.

      2. Depth-first search

      Depth-first search (or DFS) is a traversal option for trees or graphs in which child nodes are visited before their siblings on the same layer.

      2.1 Easy depth-first search questions

      Question 1: Binary tree inorder traversal 
      Question 2:  Same tree
      Question 3: Symmetric tree

      2.2 Medium depth-first search questions

      Question 4: Surrounded regions 
      Question 5: Clone graph
      Question 6: Number of islands
      Question 7: Course schedule

      2.3 Hard depth-first search questions

      Question 8: Binary tree maximum path sum
      Question 9: Alien dictionary
      Question 10: Serialize and deserialize binary tree

      How did you get on? To practice with more depth-first search questions like this, check out our list of 50+ depth-first search questions with solutions.

      3. Breadth-first search

      Breadth-first search (or BFS) is one traversal method for trees and graphs in which all vertices on one layer are visited before visiting their children on the next layer – i.e. every node on layer i is visited before the nodes on layer i+1.

      3.1 Easy breadth-first search questions

      Question 11: Maximum depth of binary tree
      Question 12: Minimum depth of binary tree
      Question 13: Maximum depth of N-ary tree

      3.2 Medium breadth-first search questions

      Question 14: Binary tree level order traversal
      Question 15: Binary tree zigzag level order traversal
      Question 16: Binary tree level order traversal II

      3.3 Hard breadth-first search questions

      Question 17: Word ladder
      Question 18: Word ladder II
      Question 19: Cut off trees for golf event

      Keen to work through some more? See our article, 44 breadth-first search questions and solutions. That should keep you busy for a while!

      4. Binary search

      Binary search is one of the fastest search algorithms because it halves the search space with each iteration. It requires an ordered set that also has constant access times, meaning that only sorted arrays are suitable for binary search.

      4.1 Easy binary search questions

      Question 20: Search insert position
      Question 21: Sqrt(x)
      Question 22: First bad version

      4.2 Medium binary search questions

      Question 23: Search in a rotated sorted array
      Question 24: Find first and last position of element in sorted array
      Question 25: Search a 2D matrix

      4.3 Hard binary search questions

      Question 26: Median of two sorted arrays
      Question 27: Count of smaller numbers after self
      Question 28: Find minimum in rotated sorted array II

      For more questions like these, check out our list of 50 binary search questions and solutions.

      5. Sorting

      A sorting algorithm can be performed on arrays or linked lists, in order to rearrange elements according to a series of instructions. Many algorithms require, or perform better on, a sorted dataset.

      5.1 Easy sorting questions

      Question 29: Contains duplicate 
      Question 30: Valid anagram
      Question 31: Meeting rooms

      5.2 Medium sorting questions

      Question 32: Sort an array 
      Question 33: 3Sum
      Question 34: H-index

      5.3 Hard sorting questions

      Question 35: Maximum gap
      Question 36: Merge k sorted lists
      Question 37: Count of smaller numbers after self

      Need some more sorting questions to practice with? No problem, we've got plenty more here: 54 sorting questions and solutions.

      6. Dynamic programming

      Dynamic programming is an algorithmic paradigm used to create optimal solutions for complex problems by breaking them down into simpler sub-problems that can be solved recursively.

      6.1 Easy dynamic programming questions

      Question 38: Maximum subarray
      Question 39: Climbing stairs
      Question 40: Pascal's triangle

      6.2 Medium dynamic programming questions

      Question 41: Longest palindromic substring
        Question 42: Unique paths
        Question 43: Unique paths II

        6.3 Hard dynamic programming questions

        Question 44: Regular expression matching
        Question 45: Maximal rectangle
        Question 46: Edit distance

        Check out plenty more dynamic programming questions here: 53 dynamic programming questions and solutions.

        7. Greedy algorithms

        A greedy algorithm is an algorithmic paradigm that finds the optimal solution to a problem by breaking the problem down into smaller (local) parts and finding the best solution for each of these parts.

        7.1 Easy greedy algorithm questions

        Question 47: Assign cookies
        Question 48: Can place flowers
        Question 49: Lemonade change

        7.2 Medium greedy algorithm questions

        Question 50: Jump game
        Question 51: Gas station
        Question 52: Jump game II

        7.3 Hard greedy algorithm questions

        Question 53: Candy
        Question 54: Create maximum number
        Question 55: Patching array

        For plenty more greedy algorithm questions, see 50 greedy algorithm interview questions.

        8. Backtracking

        Backtracking is a form of brute-force problem solving, but with the ability to discard potential solutions early, before they are fully explored. It is an algorithmic paradigm for incrementally finding solutions to problems.

        8.1 Easy backtracking questions

        Backtracking questions don't tend to be very easy, so we've only included one example in this first section.

        Question 56: Binary watch

        8.2 Medium backtracking questions

        Question 57: Letter combinations of a phone number
        Question 58: Generate parentheses
        Question 59: Permutations

        8.3 Hard backtracking questions

        Question 60: Word break II
        Question 61: Sudoku solver
        Question 62: Stickers to spell word

        You can find lots more backtracking questions to practice with right here: 47 backtracking interview questions.

        9. Divide and conquer

        Divide and conquer is an algorithmic paradigm used to solve problems by continually dividing the problem into smaller parts until a part is easy enough to solve (conquer) on its own. The solutions to the solved parts are then combined to give the solution for the original problem.

        9.1 Easy divide and conquer questions

        Question 63: Maximum subarray
        Question 64: Majority element
        Question 65: First bad version

        9.2 Medium divide and conquer questions

        Question 66: Kth largest element in an array
        Question 67: Search a 2D matrix II
        Question 68: Longest substring with at least K repeating characters

        9.3 Hard divide and conquer questions

        Question 69: Median of two sorted arrays
        Question 70: Reverse pairs
        Question 71: Count of smaller numbers after self

        For lots more divide and conquer questions, see our article 50 divide and conquer interview questions and cheat sheet.

        10. How to prepare for a coding interview

        If you're reading this article, it probably means that you're already up and running on the most important step towards preparing to ace a coding interview at Facebook, Google, Amazon, Microsoft, LinkedIn, Airbnb or another tech company: practicing a lot of questions.

        However, that's not all you need to be confident of killing it in an interview situation. To make sure you're really, truly prepared, we recommend following the three steps below. For extra tips, take a look at our list of 21 coding interview tips from ex-interviewers.

        10.1 Refresh your knowledge

        You'll need to be confident on all the algorithms we've gone through here. To refresh your knowledge, and to review data structures, check out our specific guides:

        Algorithms explained:

        1. Depth-first search
        2. Breadth-first search
        3. Binary search
        4. Sorting
        5. Dynamic programming
        6. Greedy algorithm
        7. Backtracking
        8. Divide and conquer

        Data structure guides:

        To review big-O notation in order to assess the time and space requirements of your algorithms, study our complete guide on big-O notation and complexity analysis.

        10.2 Learn a framework

        We recommend getting used to the step-by-step approach explained in the video below. The video was made by Amazon, but it's relevant for coding interviews at any tech company.

        Here is a summary of the approach:

        • Step 1: Clarify
          • Ask clarification questions to remove ambiguity about the problem
          • Explore the edges of the problem
        • Step 2: Plan
          • Discuss potential approaches you could take
          • Pick an approach and lay out the high level steps
        • Step 3: Implement
          • Write clean code, not pseudocode
          • Comment on your code as you go
        • Step 4: Test
          • Start by testing with a simple example
          • Try breaking your code with edge and corner cases
        • Step 5: Optimize
          • Calculate time complexity
          • Discuss how you can optimize your solution

        For a more complete breakdown of this framework, plus a full example answer, take a look at our guide on how to answer coding interview questions.

        Once you're comfortable with a framework, you'll want to start putting it into practice. This brings us to the next step:

          10.3 Practice on your own

          To practice algorithm questions, we recommend going through the questions we've listed above and trying to solve each one. If you find you need more questions on any of the topics, simply click on the links below:

          For data structure questions, we recommend practicing with our list of 73 data structure interview questionsDon't forget to practice questions on a whiteboard or simple text editor instead of an IDE.

          10.4 Practice with others

          Practicing solving coding problems on your own is a great way to prepare, but it's not enough. If you make it to the onsite interview stage, you'll be expected to code on a whiteboard (or virtual equivalent) and talk through your approach as you code. This can be really tricky if you're not used to it.

          That's why we recommend practicing with experts who can give you insightful feedback. If you know a software engineer or similar who has experience running interviews at the company you're interviewing at, then that's fantastic. But for most of us, it's tough to find the right connections to make this happen. And it might also be difficult to practice multiple hours with that person unless you know them really well. 

          Here's the good news. We've already made the connections for you. We’ve created a coaching service where you can practice 1-on-1 with ex-interviewers from leading tech companies like Facebook, Google, and Amazon. Learn more and start scheduling sessions today