Coaches Icon to expand interview coaching navigation menu
All coaches
Get job offers
Interview coaching Popular Resume review Take-home assignment review
Negotiate your salary
Salary negotiation
Get promoted
Leadership coaching
Plan your next career steps
Career coaching
Advice Icon to expand interview coaching navigation menu
Engineering Product Consulting Program View all
Reviews

The Ultimate Data Structure Interview Questions List (Google, Meta, etc)

Software engineering Dec 01, 2022
Data structure interview questions

Data structure interview questions are a core part of software engineer interviews at companies such as Meta, Google, or Amazon.

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 structure 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!

Click here to practice 1-on-1 with FAANG ex-interviewers

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.

Click here to download the data structure interview cheat sheet as a PDF.

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 Meta, 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 tips from ex-interviewers.

10.1 Refresh your knowledge

To refresh your knowledge, and to review relevant data structures and algorithms, check out our specific guides:

Data structures:

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

Algorithms:

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

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 complete breakdown of this framework, and 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 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 our article 71 algorithm interview questions, which has links to high quality answers to each problem. It's organized by type of algorithm and difficulty level. 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 Meta, Google, and Amazon. Learn more and start scheduling sessions today.