Niklaus Wirth, a Swiss computer scientist, wrote a book in 1976 titled:
Algorithms + Data Structures = Programs
40+ years later, that equation still holds true. That's why software engineering candidates have to demonstrate their understanding of data structures along with their application.
Almost all problems require the candidate to demonstrate a deep understanding of data structures. It doesn't matter whether you have just graduated (from a university or coding bootcamp), or you have decades of experience.
Sometimes interview questions explicitly mention a data structure, e.g. "given a binary tree." Other times it's implicit, e.g. "we want to track the number of books associated with each author."
Learning data structures is essential even if you're just trying to get better at your current job. Let's start with understanding the basics.
If you are looking for resources on data structures for coding interviews, look at the interactive & challenge based courses: Mastering Data Structures for Coding Interviews which features data structure interview courses in Python, Java, C++, and JavaScript.
For more advanced questions, look at Grokking the Coding Interview: Patterns for Coding Questions.
What is a Data Structure?
Simply put, a data structure is a container that stores data in a specific layout. This "layout" allows a data structure to be efficient in some operations and inefficient in others. Your goal is to understand data structures so that you can pick the data structure that's most optimal for the problem at hand.
Why do we need Data Structures?
As data structures are used to store data in an organized form, and data being the most crucial entity in computer science, the true worth of data structures is clear.
No matter what problem are you solving, in one way or the other you have to deal with data - whether it's an employee's salary, stock prices, grocery list, or even a simple telephone directory.
Based on different scenarios, data needs to be stored in a specific format, and we have a handful of data structures that cover our need to store data in different formats.
Commonly used Data Structures
Let's first list the most commonly used data structures, and then we'll cover them in more detail:
- Arrays
- Stacks
- Queues
- Linked List
- Trees
- Graphs
- Tries (They are effectively trees but it's still good to call them out separately).
- Hash Tables
Arrays
An array is the simplest and most widely used data structure. Other data structures like stacks and queues are derived from arrays.
Here's an image of a simple array of size 4, containing elements (1,2,3 and 4):
Each data element is assigned a positive numerical value called the Index, which corresponds to the position of that item in the array. The majority of languages define the starting index of the array as 0.
The following are the two types of arrays:
- One-dimensional arrays (as shown above)
- Multi-dimensional arrays (arrays within arrays)
Basic Operations on Arrays
- Insert - Inserts an element at given index
- Get - Returns the element at given index
- Delete - Deletes an element at given index
- Size - Get the total number of elements in an array
Commonly asked Array interview questions
- Find the second minimum element of an array
- First non-repeating integers in an array
- Merge two sorted arrays
- Rearrange positive and negative values in an array
Stacks
We are all familiar with the famous Undo option, which is present in almost every application. Ever wondered how it works? The idea: you store the previous states of your work (which are limited to a specific number), in the memory in such an order that the last one appears first. This can't be done just by using arrays. That is where the Stack comes in handy.
A real-life example of Stack could be a pile of books placed in a vertical order. In order to get the book that's somewhere in the middle, you will need to remove all the books placed on top of it. This is how the LIFO (Last In First Out) method works.
Here's an image of the stack containing three data elements (1,2 and 3), where 3 is at the top and will be removed first:
Basic operations of the stack:
- Push - Inserts an element at the top
- Pop - Returns the top element, after removing from the stack
- isEmpty - Returns true if the stack is empty
- Top - Returns the top element without removing from the stack
Commonly asked Stack interview questions
- Evaluate postfix expression using a stack
- Sort values in a stack
- Check balanced parentheses in an expression
Queues
Similar to Stack, Queue is another linear data structure that stores the element in a sequential manner. The only significant difference between Stack and Queue is that instead of using the LIFO method, Queue implements FIFO method, which is short for First in First Out.
A perfect real-life example of Queue: a line of people waiting at a ticket booth. If a new person comes, he will join the line from the end, not from the start - and the person standing at the front will be the first to get the ticket and hence leave the line.
Here's an image of Queue containing four data elements (1,2,3 and 4), where 1 is at the top and will be removed first:
Basic operations of Queue
- Enqueue() - Inserts element at the end of the queue
- Dequeue() - Removes an element from the start of the queue
- isEmpty() - Returns true if queue is empty
- Top() - Returns the first element of the queue
Commonly asked Queue interview questions
- Implement stack using a queue
- Reverse first k elements of a queue
- Generate binary numbers from 1 to n using a queue
Linked List
A linked list is another important linear data structure which might look similar to arrays at first but differs in memory allocation, internal structure and how basic operations of insertion and deletion are carried out.
A linked list is like a chain of nodes, where each node contains information like data and a pointer to the succeeding node in the chain. There's a head pointer, which points to the first element of the linked list, and if the list is empty then it simply points to null or nothing.
Linked lists are used to implement file systems, hash tables, and adjacency lists.
Here's a visual representation of the internal structure of a linked list:
Following are the types of linked lists:
- Singly Linked List (Unidirectional)
- Doubly Linked List (Bi-directional)
Basic operations of Linked List:
- InsertAtEnd - Inserts given element at the end of the linked list
- InsertAtHead - Inserts given element at the start/head of the linked list
- Delete - Deletes given element from the linked list
- DeleteAtHead - Deletes first element of the linked list
- Search - Returns the given element from a linked list
- isEmpty - Returns true if the linked list is empty
Commonly asked Linked List interview questions
- Reverse a linked list
- Detect loop in a linked list
- Return Nth node from the end in a linked list
- Remove duplicates from a linked list
Graphs
A graph is a set of nodes that are connected to each other in the form of a network. Nodes are also called vertices. A pair(x,y) is called an edge, which indicates that vertex x is connected to vertex y. An edge may contain weight/cost, showing how much cost is required to traverse from vertex x to y.
Types of Graphs:
- Undirected Graph
- Directed Graph
In a programming language, graphs can be represented using two forms:
- Adjacency Matrix
- Adjacency List
Common graph traversing algorithms:
- Breadth First Search
- Depth First Search
Commonly asked Graph interview questions
- Implement Breadth and Depth First Search
- Check if a graph is a tree or not
- Count number of edges in a graph
- Find the shortest path between two vertices
Trees
A tree is a hierarchical data structure consisting of vertices (nodes) and edges that connect them. Trees are similar to graphs, but the key point that differentiates a tree from the graph is that a cycle cannot exist in a tree.
Trees are extensively used in Artificial Intelligence and complex algorithms to provide an efficient storage mechanism for problem-solving.
Here's an image of a simple tree, and basic terminologies used in tree data structure:
The following are the types of trees:
- N-ary Tree
- Balanced Tree
- Binary Tree
- Binary Search Tree
- AVL Tree
- Red Black Tree
- 2–3 Tree
Out of the above, Binary Tree and Binary Search Tree are the most commonly used trees.
Commonly asked Tree interview questions
- Find the height of a binary tree
- Find kth maximum value in a binary search tree
- Find nodes at "k" distance from the root
- Find ancestors of a given node in a binary tree
Trie
Trie which is also known as "Prefix Trees", is a tree-like data structure which proves to be quite efficient for solving problems related to strings. It provides fast retrieval, and mostly used for searching words in a dictionary, providing auto suggestions in a search engine, and even for IP routing.
Here's an illustration of how three words "top", "thus" and "their" are stored in Trie:
The words are stored in the top to the bottom manner where green colored nodes "p", "s" and "r" indicates the end of "top", "thus" and "their" respectively.
Commonly asked Trie interview questions:
- Count total number of words in Trie
- Print all words stored in Trie
- Sort elements of an array using Trie
- Form words from a dictionary using Trie
- Build a T9 dictionary
Hash Table
Hashing is a process used to uniquely identify objects and store each object at some pre-calculated unique index called its "key." So, the object is stored in the form of a "key-value" pair, and the collection of such items is called a "dictionary." Each object can be searched using that key. There are different data structures based on hashing, but the most commonly used data structure is the hash table.
Hash tables are generally implemented using arrays.
The performance of hashing data structure depends upon these three factors:
- Hash Function
- Size of the Hash Table
- Collision Handling Method
Here's an illustration of how the hash is mapped in an array. The index of this array is calculated through a Hash Function.
Commonly asked Hashing interview questions
- Find symmetric pairs in an array
- Trace complete path of a journey
- Find if an array is a subset of another array
- Check if given arrays are disjoint
The above are the top 8 data structures that you should definitely know before walking into a coding interview.
If you are looking for resources on data structures for coding interviews, look at the interactive & challenge based courses: Mastering Data Structures for Coding Interviews featuring courses in Python, Java, C++, and JavaScript.
For more advanced questions, look at Grokking the Coding Interview: Patterns for Coding Questions.
Good luck and happy learning! :)
Top comments (13)
Oh man, I would never want to work in a company that believes my understanding of the internals of arrays, hash tables, trees, graphs, etc. matter. They clearly have the focus on some nonsense that helps not at all in performing the actual job of a programmer, which is implementing good enough things in a timely manner.
I would literally walk out on the interview if they started asking me nonsense like this.
The worst job I ever took I should've passed on immediately when they seriously asked me to write SQL on a piece of paper. I should've walked out at that very moment. I didn't have the sense to do that then, but now I do.
It's like the post from a few days ago about how bubblesort works - literally basically nobody needs to ever know that. What the average programmer needs to know is how to use the
sort()-function of the language in question and that's it, whatever algorithm is behind it matters so incredibly rarely that you can basically say it's never.It really depends where you’re working. Companies like FB, Google, and Amazon need to test programmers on data structures because certain structures work better in certain situations, and when their software engineers know which tools to use to optimize a process to run in 5μs instead of 10μs... well, let’s just say for a company running tens or hundreds of thousands of servers, every microsecond saved means less servers the company needs running. And less servers = more $$$.
But for most startups or mid sized companies it’s way more important that developers know how to get shit up and running, and less important the actual code they write to get there.
The problem is a lot of smaller tech companies look up to companies like Google and try to copy they’re interview process because hey, it’s Google. And these companies never consider that just maybe an app with billions of users has a slightly different set of requirements than their app with 500 users.
No heaps? I'm sure they deserve some love too.
Yes, I should add them to the list as well.
There is list of offers and it's criteria, which looks like this.
Each offer will have list of product ids, if a cart has all these products, then the corresponding discount would be applicable.
Now for a given cart, multiple offers may be applicable. In that case, offer which returns the max discount should be returned.
Example
Lets say the Cart contains these products [1,2,3,5,7,6,9]
List of offers are:
Offer 1- Product I'd [1,3,8] 10%
Offer 2 product ids [1,2,5,9] 15%
Offer 3 product ids [2,5,6] 25%
Offer 4 product ids [1,2,3,4] 30%
Output : 25%
For the cart, offer1 is not applicable as product I'd 8 is not there in the cart.
Offer2 is applicable as product I'd 1,25,9 all are available in the cart.
Offer3 is also applicable
Offer 4 is not applicable as product I'd 4 is not present in the cart.
Thus output would max discount from offer 2 and offer 3.
Which is 25%
Question is how should we store these offers so that we should get the offer amount with minimum time.
Assume this is for a big retail company, where the request comes in large number.
Can anyone please let me know the right data structures for this?
Hi,
You can use two different data structure to maintain the time complexity.
Hash Map
Hash-Map to put all the products for efficient lookup
Go through all the offers and check whether their elements exist in Hash-map.
If yes , put them in heap.
Max-Heap will contain discounts in descending order but before inserting into heap you need to check that the list of order with id's belongs to product like Product I'd [1,3,8] doesn't belong to original list of these : This is step 1
products [1,2,3,5,7,6,9]
After Insertion you can get Max discount in o(1) in max-heap.
Awesome! Thank you.
Thanks a lot! ❤️
thanks) remember that book (studied at the institute ))
next step - methods of sorting?
Nice! Thanks a lot for this.
Awesome list! Well laid out and super useful. Thanks so much for your time in writing this!
What a great great post! Your interview questions have been added (and answered) on fullstack.cafe portal and back-linked!
Very well explained sir.
Very helpful.