Top 8 Data Structures for Coding Interviews and Practice Interview Questions

Introduction

According to a Swiss computer scientist, Niklaus Wirth, algorithms and data structure are combined together to make a program. Whenever you encounter a technical interview it is expected that the interviewer will give you a problem statement based on data structures and algorithms and expects you to solve it within a given time. The outline of the solution provided by you must be from brute force to the most optimized way you can. This practice is followed on the fresher and experience level candidates too.

Let us now look at the top in-demand 8 data structures for coding interviews:

• Arrays
• Stacks
• Queues
• Linked List
• Trees
• Graphs
• Tries
• Hash Tables

Array

Consider a case when you had to input the names of around a hundred students and print them. The first step would be to declare a hundred variables that might be confusing and shuffling. If it would have been for 10 or 5 students the concept of variables would work great. But now, here we need a data structure whose single variable can hold multiple values.

An array is defined as a data structure that can hold multiple values. Each element in an array is traversed and accessed through the indexes.

The index of the first element starts with 0 and goes till (n-1). Where n is the size of the array. In an array, all the elements are stored at continuous locations.

There are two types of arrays as follows:

1) One-dimensional array - This type of array element can only be accessed by using the position row-wise.

Example - int arr[5] // It is an array of 5 elements

2) Two-dimensional array - This type of array element can only be accessed by row and column together.

Example - int arr[2][2] // It is an array containing two rows and two columns. The first [] is called a row and the second [] is called a column.

In a coding interview, the following are some asked questions -

a) Set Matrix Zeroe
b) Pascal’s Triangle
c) Next Permutation
d) Sort an array of 0’s 1’s 2’s
e) Stock buy and Sell
f) Rotate Matrix
g) Find the duplicate in an array of N+1 integers.
h) Inversion of Array
i) Search in a 2d Matrix
j) Pow(X,n)
k) Majority Element (>N/2 times)
l) Majority Element (>N/3 times)

m) Grid Unique Paths

n) Reverse Pairs

Stack

A stack is a data structure that follows the concept of Last in first out(LIFO). It means that the last element that is put into will be taken out at first.

For example, a pile of 10 plates numbered one to ten, a pile of coins, etc.

Also, the undo option that we commonly see in MS-word or Excel works on the concept of a stack. The basic operations performed on a stack are -

1. Push - Inserts an element into the stack at the top.
2. Pop - Deletes an element from the top of the stack.
3. Top - Prints the topmost element in the stack.
4. Empty - Function to check whether the stack is empty or not.

A stack can be implemented as an array and as a linked list. Common interview questions asked from the stack are as follows -

a) Implement Stack Using Arrays
b) Implement Queue Using Arrays
c) Implement Stack using Queue (using single queue)
d) Implement Queue using Stack (0(1) amortised method)
e) Check for balanced parentheses
f) Next Greater Element
g) Sort a Stack

Queue

A queue is a data structure that works on the concept of FIFO(first in, first out). In short, an element that is inserted first will be operated first and the next ones will be behind that first element. The basic difference between stack and queue is - stacks follow LIFO and queue follows FIFO.

For example, in a line of getting movie tickets, the person standing in the front will receive the movie tickets first.

The basic operations of a queue are as follows -

1. Enqueue()  - The function inserts an element into the queue
2. Dequeue() - The function removes the first element from the queue
3. isEmpty()  -  Checks if the queue is empty or not.
4. Top()  -  Returns the front/first element of the queue

A queue can be implemented using a stack, an array, or a linked list. The commonly asked interview questions on queue data structure are -

a) Next Smaller Element
b) LRU cache (IMPORTANT)

c) LFU Cache

d) Largest rectangle in a histogram
e) Sliding Window maximum

f) Implement Min Stack

g) Rotten Orange (Using BFS)

h) Stock Span Problem

i) Find the maximum of minimums of every window size

j) The Celebrity Problem

Linked lists

A linked list is much similar to arrays but here the only difference is it stores the element at different memory locations, unlike slack. In a linked list, we have a node and the next pointer that holds the address of the next node associated with it.

A head pointer points to the first element in the linked list and the last points to null. There are the following types of linked lists -

• Singly-linked list - In a singly linked list, a node contains the data and the next pointer that points to the next node. In this type of linked list, we can only iterate forward.
• Doubly linked list - In a doubly-linked list, the node contains a previous pointer that points to the previous element. Hence backward and forward moment is supported in a doubly-linked list.

Basic operations of linked lists -

1. Pushfront - Inserts an element in the front of the linked list
2. PushBack - Inserts an element at the end of the linked list
3. Delete - The deletion of a node supports deletion from the front, deletion from the end, deletion at a given node.
4. Search - Searches an element in the linked list
5. Empty - Checks if the linked list is empty or not.

The commonly asked interview questions on the linked list are -

a) Reverse a LinkedList
b) Find the middle of LinkedList
c) Merge two sorted Linked List (use method used in mergeSort)
d) Remove N-th node from back of LinkedList
e) Add two numbers as LinkedList
f) Delete a given Node when a node is given.(0(1) solution)
g) Find intersection point of Y LinkedList

h) Detect a cycle in Linked List

i) Reverse a LinkedList in groups of size k.

j) Check if a LinkedList is palindrome or not.

k) Find the starting point of the Loop of LinkedList

l) Flattening of a LinkedList

Trees

A tree is the most hot-pick topic in the coding interview. It is mostly asked in the big product-based companies like Microsoft, Google, Salesforce, etc.

A tree is a non-linear data structure in which all the nodes are in the form of a tree branch. The hierarchical structure of a tree consists of nodes and edges.

In the real world, it is used in artificial intelligence, databases, and game development.

The most commonly asked trees in an interview are -

1) Binary trees - A tree in which a node has the utmost two nodes is known as a binary tree.
2) Binary search trees - A tree in which the nodes are arranged in some ascending or descending order from root node to the leaf node is called a binary search tree. It is also known as an ordered or sorted tree.

In addition to these, there are also other types of trees such as balanced trees, N-ary trees, AVL trees, red-black trees, etc. The interview questions asked on trees are as follows -

a) Level order Traversal / Level order traversal in spiral form
b) Height of a Binary Tree
c) Diameter of Binary Tree
d) Check if the Binary tree is height-balanced or not
e) Binary Tree to Doubly Linked List
f) Find median in a stream of running integers.
g) K-th largest element in a stream.
h) Distinct numbers in Windows.
i) K-th largest element in an unsorted array.
j) Flood-fill Algorithm
k) Search given Key in BST
l) Construct BST from given keys
m) Construct BST from preorder traversal

Graphs

A graph is similar to a tree with the difference that a cycle exists between the nodes in a graph data structure. An edge in a graph may contain some cost/weight that connects you with the other node.

Some of the graph terminologies are described below:

1) Directed graph - A directed graph is the one in which there is a direction specified while going from node A to node B.
2) Undirected graph - In an undirected graph, there is no direction between the nodes. You can go and return back to the same node via the same edge as it specifies no direction.
3) Adjacency matrix -* A square matrix used to represent a finite graph is called an adjacency matrix.
4) Adjacency list - A set of unordered lists that are used to represent a finite graph is called an adjacency list.

The common interview questions asked in the graph data structure are as follows -

a) Clone a graph
b) DFS(Depth first search)
c) BFS(Breadth first Search)
d) Detect A cycle in Undirected Graph using BFS
e) Detect A cycle in Undirected Graph using DFS
f) Detect A cycle in a Directed Graph using DFS
g) Detect A cycle in a Directed Graph using BFS
h) Topological Sort BFS
i) Topological Sort DFS
j) Number of islands
k) Bipartite Check using BFS
l) Bipartite Check using DFS

Tries

A trie is also known as prefix tree is a tree-like data structure that proves to be solving problems efficiently associated with strings.

For example, searching a word in a dictionary, providing auto suggestions, IP routing, etc.

There are three types of tries mentioned below -

1. Standard trie - In a standard trie, each node is labeled with a character expected from the root node.
2. Compressed trie - A compact representation of standard trie is called compressed trie.
3. Suffix tree - A suffix tree stores a list of strings. It is also referred to as the compressed version of a trie, as, unlike a trie, each unique suffix in the list is compressed together and represented by a single node or branch in a suffix tree.

The following are the relevant interview questions related to tries -

a) Count the total number of words in Trie
b) Print all words stored in Trie
c) Sort elements of an array using Trie
d) Form words from a dictionary using Trie
e) Build a T9 dictionary

Hash Tables

The hash table data structure stores elements in an associated manner and each element in the hash table has its own unique index value. The concept of index value makes the access of any piece of information fastly if it is known.

All the search and insertion operations are very fast and efficient in hash tables. Hashing is a technique to convert a range of key values into a range of indexes of an array.

The performance of hashing depends on - the size of the Hash Table, hash Function, collision Handling Method.

The basic operations in a hash table are as follows:

1. Search - Searches an element in the hash table
2. Insert - Inserts an element into the hash table
3. Delete - Deletes an element from the hash table

The most asked interview questions in trie are as follows -

a) Find symmetric pairs in an array
b) Trace the complete path of a journey
c) Find if an array is a subset of another array
d) Check if given arrays are disjoint

Conclusion

Every data structure holds its individual weightage and importance in interviews. The most commonly asked questions are given in the article but the journey doesn't end here. There are many more types of sections like sorting, searching, greedy algorithms, dynamic programming methodology, etc. also asked in interviews. Some of them you can learn by reading Data Structures resources by Scaler Topics.