Data Structures and Algorithms Interview Questions (2023)

Why do you need knowledge of data structures and algorithms?

Data structures and Algorithms are techniques used to write efficient code for a given problem, much like how you need music theory to master an instrument. To be a good programmer you need to learn to use the right data structure and algorithm for a given problem.

Say, you need to travel to a particular spot in your city. You take a car to travel to the spot but later discover that taking the metro would have been faster and cheaper. Similarly, insufficient knowledge in DSA can lead you to write inefficient code.

In interviews, an interviewer will test you on the basis of how quickly you come up with the solution, how efficient your code is, and they can go on to ask you in-depth questions about the data structure or algorithm you’ve used to solve the problem.

The popular opinion for mastering Data Structures and Algorithms is to solve hundreds of problems. But it is actually more valuable to focus on a handful of problems and get a thorough understanding of each data structure and algorithm and how to apply them.

Once you take this approach to learning, you will find that you can segregate problems into different types and each of these will have the same approach and algorithm that can be used.

This blog will introduce you to frequently asked DSA interview questions in some of the top IT companies in the world.

List of Questions

1. Trapping Rainwater

Steps

Rainwater can be trapped if there are bars of higher elevations to its left and right. The amount of water that can be trapped is the difference between the minimum of the two higher elevations to the left and right and the elevation in the current bar.

Here, two-pointer approach is used which uses two different pointers, one moving from the left to the right, and another from the right to the left of the elevation map.

Start with the left pointer on the leftmost bar, i.e, initialize left pointer to index 0, and the right pointer on the rightmost bar i.e., initialize right pointer to index n-1. Set the amount of water stored to be 0.
Create two variables maxLeft and maxRight to keep track of the highest elevations encountered by the left and right pointer respectively. Initalize maxLeft and maxRight as 0.
Traverse the array with these two pointers until they cross each other i,e., While left pointer <= right pointer

a. Find the highest bars on the left and right sides by performing the following comparisons.

If the elevation at left pointer is greater than maxLeft, update maxLeft.
If the elevation at right pointer is greater than maxRight, update maxRight.

b. There will be two cases at each iteration.

If maxLeft <= maxRight

Increment the water stored by the difference between maxLeft and the elevation at the left pointer bar.

Increment the left pointer by 1.

If maxLeft > maxRight

Increment the water stored by the difference between maxRight and the elevation at the right pointer bar.

Decrement the right pointer by 1.

4. Display the water stored, which is the required result.

2. Rat in a Maze

Steps

Two paths exist for the rat to travel to the destination (3,3)

We will use the principle of backtracking to find all valid paths.

Create a path matrix of N*N dimensions to keep track of the path that the rat will take. This matrix will be used to store the path that the rat takes by marking the cells it has visited with 1s and the unvisited cells with 0s.
Start the traversal of the input matrix that represents the maze starting from the rat’s initial position (0,0). The rat can traverse in 4 possible ways - either down, up, right, or left. Keep track of the visited cells by marking them as visited in the path matrix.
If the position (x,y) is out of the matrix, or if it is blocked (0) backtrack to the previous step taken.

Else,

Mark (x,y) as visited in the path matrix
If (x,y) is the destination cell,
Then
Print the path taken as a solution (using the path matrix) and backtrack to the previous step

Else

Move from (x,y) to (x+1,y) (right), (x-1,y) (left), (x,y+1) (down) (x,y-1) (up), one at a time, and repeat step 4 recursively from each of these positions.
If these don’t lead to the destination cell, unmark (x,y) as visited in the path matrix and backtrack to the previous step.

3. House Robber

Steps

There can be no houses so the robber can't steal any money. There can be just one house, in which case the robber steals money from that house. If there are two or more houses, the robber will try to steal the maximum amount of money without stealing from any two adjacent houses.
Use an array called dp[ ] with the size equal to the number of houses. Each element of this array will indicate the maximum amount of money that can be stolen from the ith house (index of that element) to the last house.

To find out the maximum money that can be stolen you need to consider every possible combination of houses from the ith house to the last house. However, this will result in repeatedly calculating certain sub-problems. By storing the result of these subproblems (the maximum money that can be stolen from ith house to the last house) in the dp array, you can optimise the solution. This is the principle of Dynamic Programming.

3. The robber can steal money in two ways as he moves from the first house to the last

a. He can rob from the current house (i) and skip the next house ( go to the house at i + 2), and from there find the maximum money that can be stolen amongst all the houses that are remaining.

So the robber steals the money from the current house + the maximum money that can be stolen from house i+2 onwards.

b. He can skip the current house and move to the next house (at i + 1) and repeat step 3. So, the robber steals the maximum amount that can be stolen from house i + 1 onwards.

4. Now, find the maximum of the values calculated at steps a and b and update the dp array to this value.

Note: If the maximum money that can be stolen at a house i has already been calculated and stored in dp[i], the value is directly used.

4. Merge K Sorted Linked Lists

Steps

Pair the K linked lists into groups of 2 and combine each pair in a sorted way with linear time complexity.
A pair of linked lists can be combined by using 2 pointers, each pointer traversing one linked list. Both pointers start at the head node of their respective list and traverse through the nodes till the end. At each step, compare the value at the two nodes and pick the smallest of the nodes. Increment that smaller node pointer while the other pointer stays where it is.
After the first repetition, K / 2 lists remain, each with a size of 2 * N. In the second duplication, K / 4 linked lists remain, and so on.
Repeat this process until you have only one linked list left.

5. Valid Parentheses

For a set of parentheses to be valid, they have to be closed in the reverse order in which they have been opened. In other words, the most recently opened bracket has to be closed first. The Last In First Out property of a stack is well suited to handle this.

Steps

Use a stack to store characters.
Traverse the given string expression.
If the current character is an opening bracket, then push it into the stack.
If the current character is a closing bracket, compare it to the character at the top of the stack by popping from the stack. If they are a pair of opening and closing brackets of the same kind, the brackets are valid and we continue. If not, they are invalid, we can stop at this point and return false.
After the traversal, if there is an opening bracket left in the stack, then the parentheses are not valid.

6. Search a 2D Matrix

Steps

Binary Search is the optimal solution for this problem as we have a sorted matrix. You can perform Binary Search at the middle column of the sorted matrix. If the search element is less than the middle element of the middle column, then you can eliminate all the rows following that element. The vice versa can be done if the search element is greater than the middle element, which makes searching easier.

Perform binary search on the middle column of the matrix. If at any iteration, the search element is equal to the middle column element being compared, the search is successful. Else, continue binary search until only two rows are remaining.
Compare the search element with the middle elements of the two remaining rows. Now, there are four cases that may arise

If the search element is equal to either of the middle elements, the search is successful.
If the search element is lesser than both the middle elements, perform binary search on the first half of the first row.
If the search element is between the middle elements, perform binary search first on the second half of the first row, and if the search element is not found, perform binary search on the first half of the second row.
If the search element is greater than both the middle elements, perform binary search on the second half of the second row.

3. If the search element is still not found, label the search as unsuccessful.

4. Use a nested loop. An outer loop for the row and an inner loop for the column.

7. Number of Islands

Steps

There are 3 islands in this matrix

Since two pieces of land are connected only if they are vertically or horizontally adjacent to each other, the matrix can be treated as an undirected graph, with an edge between two horizontally or vertically adjacent nodes of value 1.

Because all the nodes in an island are connected, a graph search algorithm can be used to visit all the nodes of an island by starting at any island node. Any graph search algorithm such as Depth First Search or Breadth First Search can be used to solve this problem.

Here Depth First Search is used as the graph search algorithm.

Treat the 2D matrix as an undirected graph with an edge between two horizontally or vertically adjacent nodes of value 1.
Linear scan the 2D matrix.
Depth-first search is initiated upon finding an unvisited node 1. This node is taken as the root node.
During DFS, set every visited node as 0, to account for visited nodes.
The number of root nodes that trigger DFS would be the number of islands.

8. Merge Intervals

Steps

If you have a sorted list of intervals (sorted by their start time), with the first i intervals non overlapping, then the (i + 1)th interval can only overlap with the ith interval. Hence, if you push the first i intervals into a stack, then only the interval at the top of the stack is required for further comparison.

Sort the given intervals in increasing order of their starting time.
Create an empty stack and start traversing the list of intervals.
For each interval,

Push the current interval into the stack only if the stack is empty or the top interval in the stack does not overlap with it.
If the current interval overlaps with the top interval of the stack, that is, the starting time of the current interval is less than the ending time of the stack top interval, update the ending time of the stack top interval as the ending time of the current interval.

4. The stack now contains the list of merged intervals none of which overlap.

9. Minimize Cash Flow

Steps

Calculate the total amount of each person as -

Net amount at person i = Sum of all money i receives - Sum of all money i pays

Find two persons with the maximum and minimum net amount. Let the person with the maximum net amount be maxReceiver and the person with the minimum net amount be maxPayer.
Find the absolute minimum of maxReceiver and maxPayer. Let this amount be payment ‘x’.
maxPayer will pay ‘x’ to maxReceiver. X will be added to maxPayer’s net amount and subtracted from maxReceiver’s net amount.
Repeat steps 2 to 4 until all the net amounts become zero.

10. LRU Cache

Steps

Least Recently Used (LRU) is a common caching strategy. It implements a policy to evict elements from the cache. When the cache is full and new elements need to be added, it evicts the least recently used items first.

Also read,

Take an example of a cache that has a capacity of 4 . The elements 1, 2, 3, 4 are cached with 1 being the first element to be cached and 4 the last element.

The cache state after first access of all four elements

1 2 3 4

Say you need to cache a new element 5.

In LRU cache, the least recently used element should be evicted in case a new element needs to be added.

So, 1 is removed and 5 is added to the cache. Now the cache has the elements

2, 3, 4, 5

A cache has to be able to access and retrieve the data in constant time. This can be achieved using the following data structures

Queue (representing the cache) - The maximum size of the queue will be equal to the cache size . The most recently used elements will be near the front end and the least recent elements will be near the rear end. A doubly linked list is used to implement this queue over a singly linked list because a doubly linked list can delete a node given its address, in constant time whereas a singly linked list achieves this in linear time.

Hashmap - Use a hashmap to access the node address of the doubly linked list which corresponds to a particular element in constant time.The hashmap will contain the element as key and address of the corresponding node as value.

When an element is referenced, try to lookup the cache by using the corresponding node address from the hash. The required element may be in the cache. If it is in the cache, detach the particular node from the list and attach it to the front of the queue.
If the required element is not in cache, attach a new node to the front of the queue and write the corresponding node address in the hash.
If the queue is full, delete a node from the rear of the queue, and add the new node to the front of the queue. Update the hash.

Conclusion

Hope this blog helped you learn to apply different data structures and algorithms using the problem statements asked in interviews. Only some of the frequently asked questions were picked for this blog. But there are many more such problems you can find and practice. Crio’s DSA packs are a great place to start and master all the data structures and algorithms.