73 data structure interview questions (with solutions and cheat sheet)

Practice 1-on-1 with FAANG ex-interviewers. Learn more.

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 data structure problems.

That's why we've compiled a comprehensive list of 73 typical questions grouped by type (arrays, strings, linked list, 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 data strucure at a glance.

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

    1. Data structure cheat sheet
    2. Array questions
    3. String questions
    4. Linked list questions
    5. Stacks and queues questions
    6. Tree questions
    7. Graph questions
    8. Map questions
    9. Heap questions
    10. How to prepare for a coding interview

      Let's get into it!

      1. The ultimate data structure 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 data structures.

      Just put your email in the form below, and we'll send it straight to you (don't worry, we won't bombard you with endless emails).

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

      2. Arrays

      Arrays are one of the most fundamental data structures in programming and computer science, and many more complex data structures are built using arrays. Learn more.

      2.1 Easy array questions

      2.1.1 Merge two sorted arrays 
      2.1.2  Remove duplicates from an array
      2.1.3 Count the frequency of an element in an array

      2.2 Medium array questions

      2.2.1 Move all zeros to the beginning/end of an array 
      2.2.2 Find if a given element is in a sorted array (binary search)
      2.2.3 Rotate an array 
      2.2.4 Product Array Puzzle 

      2.3 Hard array questions

      2.3.1 Rotate a 2D array 
      2.3.2 Create change with coins (dynamic programming)
      2.3.3 Sliding window maximum

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

      3. Strings

      A string is an ordered sequence, or string, of characters. It is usually considered a data type and is often included as part of language primitives. In most languages, strings are implemented using an array of bytes. The bytes are encoded using some character encoding. Earlier systems used ASCII encoding, with Unicode encoding used in later systems. Learn more.

      3.1 Easy string questions

      3.1.1 Remove vowels from a string 
      3.1.2 Defanging an IP address
      3.1.3 Jewels and stones

      3.2 Medium string questions

      3.2.1 Longest substring without repeating characters
      3.2.2 Longest palindromic substring
      3.2.3 String to integer (atoi)

      3.3 Hard string questions

      3.3.1 Regular expression matching
      3.3.2 Wildcard matching
      3.3.3 Minimum window substring

      Keen to work through some more? See our article, 50+ string questions and solutions. That should keep you busy for a while!

      4. Linked lists

      A linked list is a data structure used to store a collection of data elements. In this way, it is similar to an array. However, unlike an array, the data elements in a linked list do not need to be stored contiguously in memory. Rather, each node in a linked list has a pointer or reference to the memory location of the next node in the list. This means that linked lists do not have a fixed size like arrays, and can easily grow and shrink as elements are added or removed. Learn more.

      4.1 Easy linked list questions

      4.1.1 Merge two sorted lists
      4.1.2 Linked list cycle
      4.1.3  Intersection of two linked lists

      4.2 Medium linked list questions

      4.2.1 Add two numbers
      4.2.2 Remove Nth node from end of list
      4.2.3 Copy list with random pointer

      4.3 Hard linked list questions

      4.3.1 Design linked list
      4.3.2 Merge k sorted lists
      4.3.3 Reverse nodes in k-group

      For more questions like these, check out our list of 40+ linked list questions and solutions.

      5. Stacks and queues

      Stacks and queues are similar and complementary in many ways. Both are a sequenced collection of elements that are generally accessed one element at time, and they are implemented using similar data structures. Learn more.

      5.1 Easy stacks and queues questions

      5.1.1 Valid parenthesis
      5.1.2 Min stack
      5.1.3 Implement stack using queues

      5.2 Medium stacks and queues questions

      5.2.1 Simplify path
      5.2.2 Evaluate reverse polish notation
      5.2.3 Basic calculator II

      5.3 Hard stacks and queues questions

      5.3.1 Longest valid parentheses
      5.3.2 Trapping rain water
      5.3.3 Largest rectangle in histogram

      Need some more stacks and queues questions to practice with? No problem, we've got plenty more here: 50+ stacks and queues questions and solutions.

      6. Trees

      A tree is an abstract hierarchical data structure. It is represented by a group of linked nodes, with a single root node. Each node can have zero or multiple children. A leaf is a node with no children. Learn more.

      6.1 Easy tree questions

      6.1.1 Binary tree in-order traversal
      6.1.2 Symmetric tree
      6.1.3 Maximum depth of binary tree

      6.2 Medium tree questions

      6.2.1 Validate binary search tree
      6.2.2 Binary tree level-order traversal
      6.2.3 Binary tree zigzag level-order traversal

      6.3 Hard tree questions

      6.3.1 Binary tree maximum path sum
      6.3.2 Serialize and deserialize binary tree
      6.3.3 Binary tree cameras

      Check out plenty more tree questions here: 50+ tree questions and solutions.

      7. Graphs

      A graph is an abstract data structure represented by vertices connected by edges. Vertices are also known as nodes. Vertices sharing an edge are known as adjacent. Learn more.

      7.1 Easy graph questions

      7.1.1 Find the town judge
      7.1.2 Find if path exists in graph
      7.1.3 Find center of star graph

      7.2 Medium graph questions

      7.2.1 Course schedule II
      7.2.2 Find the celebrity
      7.2.3 Clone graph

      7.3 Hard graph questions

      7.3.1 Longest increasing path in a matrix
      7.3.2 Alien dictionary
      7.3.3 Redundant connection II

      For plenty more graph questions, see 50+ graph interview questions.

      8. Maps

      A map is a data structure that allows us to access a value by key. This is in contrast to an array that allows us to access a value by index. A common kind of map is a hash map (also called a hash table), which stores keys along with associated values (for example, a telephone directory which associates phone numbers with names). Learn more.

      8.1 Easy map questions

      8.1.1 Two sum
      8.1.2 Roman to integer
      8.1.3 Majority element

       8.2 Medium map questions

      8.2.1 Longest substring without repeating characters
      8.2.2 Valid sudoku
      8.2.3 Group anagrams

      8.3 Hard map questions

      8.3.1 Minimum window substring
      8.3.2 Word ladder
      8.3.3 Word break II

      You can find lots more map questions to practice with right here: 50+ map interview questions.

      9. Heaps

      A heap is a tree-based data structure that implements a priority queue. A priority queue functions much like a regular stack or queue, except that each element has a priority. It is this priority that determines which element is returned when dequeuing from the priority queue, rather than the order in which the element was added. This is useful for applications like a hospital queue where we want to serve the patient with the highest priority first. Learn more.

      9.1 Easy heap questions

      9.1.1 Kth largest element in a stream
      9.1.2 Last stone weight
      9.1.3 The K weakest rows in a matrix

      9.2 Medium heap questions

      9.2.1 Kth largest element in an array
      9.2.2 Meeting rooms II
      9.2.3 Top K frequent elements

      9.3 Hard heap questions

      9.3.1 Kth largest element in an array
      9.3.2 Meeting rooms II
      9.3.3 Top K frequent elements

      For lots more heap questions, see our article 50+ heap 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.

      10.1 Refresh your knowledge

      You'll need to be confident on all the data structures we've gone through here. To refresh your knowledge, and to find many more questions on each data structure, check out our specific guides:

      1. Arrays
      2. Strings
      3. Linked lists
      4. Stacks and queues
      5. Trees
      6. Graphs
      7. Maps
      8. Heaps

      If you need refreshing on algorithms, we have a series of articles coming soon. In the meantime, we recommend reading Cracking the Coding interview by Gayle Laakmann McDowell.

      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
      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 data structure 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 we've provided.

        For algorithm questions, we recommend using Leetcode, where you can get a lot done with the free tier. Don'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

        cta_illustration arrow_left Browse FAANG ex-interviewers

        Any questions about coding interviews?

        If you have any questions about coding interviews, do not hesitate to ask them in the comments below. All questions are good questions, so go ahead!