Data structures and Algorithm Interview Questions

Linus Torvalds: “Bad programmers worry about the code. Good programmers worry about data structures and their relationships."

A data structure is a way of organizing (storing) data so that it can be accessed and modified easily, such as tabular data representation or number sequences. An algorithm is a stepwise sequence that yields the desired output. Combined, data structure and algorithm (DSA) are the foundation of software engineering and are applied in aspects of a software development process and enable developers to learn to write efficient code.

Here’s what we’ll cover in this article:

• Why Mastering DSA is critical
• How to Prepare for DSA Interviews
• Basic Data Structure Interview Questions
• Advanced-Data Structure Interview Questions
• Data structure Interview Questions on Strings
• Data structure Interview Questions on Arrays
• Data structure Interview Questions on Linked Lists
• Data structure Interview Questions on Binary Tree
• Data structure Interview Questions on Search and Sort Algorithms

Why Mastering DSA is Critical

Are you wondering why you need to study complicated stuff such as Array, Linked List, Stack, Queues, Searching, Sorting, Tree, Graphs etc.? And why do companies ask questions related to DSA instead of language/frameworks/tools-specific questions?

Many beginners and experienced programmers avoid learning Data Structures and Algorithms because they think they are complicated and not useful in real life. A strong understanding of data structures and algorithms helps programmers evolve and advance their careers. At the same time, interviewers often use DSA questions to evaluate candidates during the interview to test potential employees’ problem-solving skills, coding skills, and clarity of thought.

Data structures and algorithms play a major role in implementing software and the hiring process. Companies encounter a lot of complex and unstructured data on a larger scale. They are looking to hire software developers who can make the right decisions and efficiently complete the requisite tasks in a short amount of time and using fewer resources.

Knowledge of DSA goes a long way in solving these problems efficiently, and the interviewers are more interested in seeing how candidates use these tools to solve a problem. Just like a car mechanic needs the right tool to fix a car and make it run properly, a programmer needs the right tools (DSAs) to make the software run properly.

In product development, companies of the ilk of Google, Microsoft, Facebook, and Amazon allot 20-30% on the coding, which is the implementation aspect of the total project. Most of the time goes into designing things with the best and optimum algorithms to save on the company’s resources (servers, computation power, etc.). This is why interviews in these companies are mainly focused on algorithms, as they want people who can think out of the box to design algorithms that can save the company thousands of dollars.

How to Prepare for DSA Interviews?

Whether interviewing for startups or established FAANG or MAANG organizations, every company will expect you to have strong knowledge of basic data structures concepts, including String, Array, Linked List, Binary Tree, hash table, Stack, Queue, and advanced data structures such as binary heap, self-balanced Tree, circular buffer, etc.

Stage 1: Refresh your knowledge

First, start with revisiting the basics of DSA and focus on solving several problems. You should be able to write 20-30 codes without errors after practising about 100 problems. important topics to learn in this stage include the following:

Data structures: Array, Linked List, Stack, Queue, Hash Table, BST, Map (Hash vs. Tree), Set, Trie, Graph. Applications and pros & cons of those.

Algorithms: Time complexity, Space complexity, Sorting, Searching, BFS & DFS, Dynamic programming, Recursion, Divide and Conquer, and Bit manipulations.

Maths: Permutations, Combinations, Medians, Probability, Geometry, …

Problem-solving: How to reduce any given problem to a known Math or DS or DS+algo problem given enough hints.

Searching and sorting (Merge Sort, Quick Sort, Bubble Sort, Heap Sort, etc.)

Recursion, Divide and Conquer

Dictionaries and Sets, Arrays, LinkedList

HashTable, Binary Search Tree, BFS, DFS

Algorithms: Depth-first search, Breadth-first search, Binary search, Sorting, Dynamic programming, Greedy algorithms, Backtracking, Divide and conquer, Learn a framework

Logic building

Collections 101

It is highly recommended that you thoroughly practice basic and advanced data structures problems to give yourself the best chance to ace programming or coding rounds.

Overall, you can devote around 100-150 hours of focused learning in this stage to build a strong base of knowledge in fundamentals.

Stage 2: Expand Your Knowledge

Start with commonly asked questions of medium difficulty in Leetcode. After practising 100-150 such problems, you should be able to come up with multiple solutions to a problem, be familiar with common syntax errors, and would have improved your coding and debugging skills. You can devote

about 150-200 hours of focussed practice in this stage, focusing on the following:

• Writing graph traversals with 10 minutes
• Implementation of Stack, Queue, Hash, BST, and Tree
• Application of BST, Tree, Heap, and Graph
• BFS (Breadth for Search)
• DFS (Depth for Search)

Stage 3: Polish Your Skills

In this stage, all you need to do is to practise more and increase your coding speed. Try solving a wide variety of problems to avoid getting stuck when you encounter an unfamiliar question during the interview. Additionally, you can focus on improving your knowledge about the following topics:

• DP memoization
• DP tabulations
• Knapsack
• Advanced recursion
• Backtracking
• Greedy method
• Topological sort
• Graph partitioning
• Spanning-tree
• Shortest path

Let’s go ahead and look at some popular data structure interview questions that you may be asked at FAANG, MAANG, or any technical interviews.

Basic Data Structure Interview Questions

1. How will a variable declaration activity consume or affect the memory allocation?
2. What is a Dequeue?
3. What Is the Difference Between File Structure and Storage Structure?
4. What is the difference between Linear and Non-Linear Data Structures?
5. Explain how dynamic memory allocation will help you in managing data?
6. What operations can be performed on a data structure?
7. Which data structures can you use for the BFS and DFS of a graph?
8. What is a binary search? When is it best used?
9. What are FIFO and LIFO?
10. What is the difference between NULL and VOID?
11. How will you implement a stack using a queue and vice-versa?
12. What is data abstraction?
13. What are the three characteristics of data structures?
14. What are the advantages of the heap over a stack?
15. What is the difference between a PUSH and a POP?

Advanced-Data Structure Interview Questions

Can you share some examples of greedy and divide-and-conquer algorithms?

Examples of algorithms that follow the greedy approach are:

• Dijkstra’s Minimum Spanning Tree
• Graph – Map Coloring
• Graph – Vertex Cover
• Job Scheduling Problem
• Knapsack Problem
• Kruskal’s Minimal Spanning Tree
• Prim’s Minimal Spanning Tree
• Travelling Salesman

Examples of the divide and conquer approach are:

• Binary Search
• Closest Pair (or Points)
• Merge Sort
• Quick Sort
• Strassen’s Matrix Multiplication

What is a spanning tree? What is the maximum number of spanning trees a graph can have?

A spanning tree is a subset of a graph that has all the vertices but with the minimum possible number of edges. A spanning tree cannot be disconnected and does not have cycles.

The maximum number of spanning trees in a graph depends on the number of connections. A complete undirected graph with n number of nodes can have a maximum of n-1 number of spanning trees.

What is recursion?

It is the ability to allow a function or module to call itself. Either a function f calls itself directly or calls another function ‘g’ that in turn calls the function ‘f. The function f is known as the recursive function, and it follows recursive properties, which are:

Base criteria: Where the recursive function stops calling itself.

Progressive approach: Where the recursive function tries to meet the base criteria in each iteration.

What is the Tower of Hanoi problem?

It is a mathematical puzzle that comprises three towers (or pegs) and more than one ring. Each ring is of varying size and stacked upon one another such that the larger one is beneath the smaller one. The Tower of Hanoi problem’s goal is to move the disk’s tower from one peg to another without breaking the properties.

What is the maximum number of nodes in a binary tree of height k?

The maximum number of nodes in a binary tree of depth K is 2K-1, k >=1 . Here the depth of the tree is 1. A binary tree is a tree data structure in which each node has at most two children, referred to as the left and right child.

What is an asymptotic analysis of an algorithm?

Asymptotic analysis determines an algorithm’s running time in mathematical units to determine the program’s limits, also known as “run-time performance.” The purpose is to identify the best-case, worst-case, and average-case times for completing a particular activity. Asymptotic analysis is an essential diagnostic tool for programmers to analyze an algorithm’s efficiency rather than its correctness.

What are the differences between the B tree and the B+ Tree?

The B tree is a self-balancing m-way tree, with m defining the Tree’s order. Btree is an extension of the Binary Search tree in which a node can have more than one key and more than two children. The data is provided in the B tree in a sorted manner, with lower values on the left subtree and higher values on the right subtree.

B+ Tree is an advanced self-balanced tree where every path from the Tree’s root to its leaf is of the same length.

What is an AVL tree?

An AVL (Adelson, Velskii, and Landi) tree is a self-balancing binary search tree in which the difference of heights of the left and right subtrees of any node is less than or equal to one. This controls the height of the binary search tree by not letting it get skewed. This is used when working with a large data set, with continual pruning through the insertion and deletion of data.

Where is the LRU cache used in the data structure?

LRU (Least Recently Used) cache is used to organize items in order of usage, enabling you to quickly find out which item hasn’t been used for a long time.

How do you find the height of a node in a tree?

You can use a recursive Depth-First Search (DFS) algorithm to find the height of a node in a tree.

What are Infix, prefix, and Postfix notations in data structure?

The approach of writing arithmetic expressions is known as notation without changing the essence or output of the expression. These notations are:

Infix notation: Here, the X + Y – operators are written between their operands. An example of infix notation is A * ( B + C ) / D

Postfix (Polish notation): The X Y + Operators are written after their operands. The infix expression given above is equivalent to

A B C + * D/

Prefix (Polish)notation: + X Y Operators are written before their operands. The expressions given above are equivalent to

/ * A + B C D

Can doubly-linked be implemented using a single pointer variable in every node?

Describe the Different Kinds of Tree Traversals for a Binary Search Tree.

There are three ways to traverse a tree. They are:

Inorder Traversal

Traverse the Tree starting at the left subtree, then to the root of the Tree, and finishing off at the right subtree.

Preorder Traversal

Preorder traversal starts at the root, then moves to the left and, finally, to the right.

Postorder Traversal

This involves covering the Tree starting from the left subtree and moving to the right subtree. It is then moved from the right subtree to the root to complete the traversal.

What Is the Difference Between the Breadth-First Search (BFS) and Depth-First Search (DFS)?

The breadth-first search uses the queue data structure to find the shortest path in a graph. Depth-first search does the same thing but uses the stack data structure.

Can Dynamic Memory Allocation Help in Managing Data?

What Is the Left View of a Binary Tree?

The left view of a binary tree is all the nodes you visit when you traverse the Tree from its left side.

Explain Graph Data Structures

What Are the Applications of Graph Data Structures?

Can You Use an Object as a Key in HashMap?

What are asymptotic notations?

How does insertion sort differ from selection sort?

How does Kruskal’s Algorithm work?

How do you check if the given Binary Tree is BST or not?

Which data structures are used for the BFS and DFS of a graph?

Which data structure is used for the dictionary and spell checker?

What process is used to store variables in memory?

Which Sorting Algorithm Is Considered the Fastest?

**What Is the Maximum Number of Nodes in a Binary Tree of H**eight K?

String Interview Questions

The String is probably the most used data structure. You can solve string-based questions easily if you know the array because strings are nothing but a character array. From the C++ perspective, String is nothing but a null-terminated character array, but from the Java perspective, String is a full-fledged object backed by a character array.

Here is the list of frequently asked string coding questions in job interviews:

1. How do you print duplicate characters from a string?
2. How do you check if two strings are anagrams of each other?
3. How do you print the first non-repeated character from a string?
4. How can a given string be reversed using recursion?
5. How do you check if a string contains only digits?
6. How are duplicate characters found in a string?
7. How do you count the number of vowels and consonants in a given string?
8. How do you count the occurrence of a given character in a string?
9. How do you find all permutations of a string?
10. How do you reverse words in a given sentence without using any library method?
11. How do you check if two strings are a rotation of each other?
12. How do you check if a given string is a palindrome?
13. For a given string, write a code to reverse the string without disturbing the individual words.
14. Write a program to remove duplicate elements from the String.
15. Write a program to find the longest substring’s length with distinct values.
16. Write a code to remove successive duplicate characters recursively
17. For two strings, A and B, write a program to determine if B can be obtained by rotating A in at least two places.
18. How will you determine whether a string only consists of digits?
19. How do you reverse words in a given sentence without using any library method?
20. Explain the implementation process of a bubble sort algorithm.
21. How is an iterative quicksort algorithm implemented?
22. How to check if two Strings are anagrams of each other?
23. Print the first non-repeated character from String.

Data Structure Interview Questions on Arrays

An array is a data structure that stores elements at a contiguous memory location. It is a crucial part of coding or programming interviews, e.g., reversing an array, sorting the array, or searching elements on the array.

Here are some of the popular array-based coding interview questions for your practice:

1. How Do You Reference all Elements in a One-Dimension Array?
2. What Is a Jagged Array?
3. Find a missing number in a given integer array of 1 to 100?
4. Find a duplicate number on a given integer array?
5. Find all pairs of an integer array whose sum equals a given number?
6. How do you find duplicate numbers in an array containing multiple duplicates?
7. How is an integer array sorted in place using the quicksort algorithm?
8. How do you remove duplicates from an array in place?
9. How do you reverse an array in place in Java?
10. How are duplicates removed from an array without using any library?
11. For a given array of size N-1, containing integers in the range from 1 to N, write a program to find the missing element in the array.
12. For a given unsorted array of size N, write a code to rotate it anticlockwise by D elements.
13. For a given array of size N, write a code to print the reverse of the array.
14. For a given array A, write a code to delete the duplicate elements in the array.
15. Write a code to sort the array in the wave fashion for a given array of size N containing distinct integer numbers.
16. Write a code to find the maximum subarray of non-negative numbers from a given array containing integer values.
17. Find all pairs of integer arrays whose sum is equal to a given number?
18. Find multiple missing numbers in a given integer array with duplicates?
19. How do you find the largest and smallest number in an unsorted integer array?
20. How do you identify duplicate numbers in an array if it consists of multiple duplicates?

Linked List Interview Questions

A linked list is a linear data structure or a sequence of data objects where elements are not stored in contiguous memory locations. It is a dynamic data structure where the number of nodes is not fixed, and the list has the ability to grow and shrink on demand. Each list element is connected to the next using a pointer to form a chain. Each element is a separate object called a node. Each node has a data field and a reference to the next node.

Here are some of the most common and popular linked list interview questions and their solutions:

What are the operations supported by a Linked List

Basic operations supported by a linked list:

Insertion - Inserts an element at the list beginning.

Deletion - Deletes an element at the list beginning.

Display - Displays the complete list.

Search - Searches an element using the given key.

Delete - Deletes an element using the given key.

Some implementations include stacks and queues, graphs, a directory of names, dynamic memory allocation, and arithmetic operations on long integers.

Explain Doubly-Linked Lists (DLL).

A doubly linked list is a modification of a linked list in which every element points to both the element before it and the element after it. It is easy to navigate doubly linked lists forwards and backward for this reason.

Every entry in a doubly linked list has the following:

• A data field to carry a particular data value
• A link to the previous entry in the list
• A link to the next entry in the list

What Are the Applications of Doubly Linked Lists?

Any application that requires quick forward and backward navigation can employ doubly linked lists. Some examples include:

The actions you’ve taken in an image editing app can be stored in a doubly linked list to allow for each undo/redo operation.

More complex data structures like binary trees and hash tables can be constructed using doubly linked lists.

Search engine results pages can be linked to each other using doubly linked lists.

Examples include:

A music playlist with next and previous navigation buttons

The browser cache with BACK-FORWARD visited pages

The undo and redo functionality on a browser, where you can reverse the node to get to the previous page, here are some of the frequently asked related list questions from programming interviews:

1. What are the advantages of a linked list over an array? In which scenarios do we use Linked List, and when array?
2. Do you know how to reverse a linked list?
3. How do you find the third node from the end in a singly linked list?
4. How do you find the sum of two linked lists using Stack?
5. How do you find a single linked list’s middle element in one pass?
6. Write a code to add two numbers represented by Linked Lists
7. Write a function to remove the nth node from a Linked List
8. Write a program to swap adjacent nodes in a Linked List
9. Write a code to reverse a Linked List from position X to position Y
10. Write a program to flatten a given multi-level linked list
11. Write a code to find the next greater node for a given Linked List
12. Find the middle element of a singly linked list in one pass?
13. Find the 3rd node from the end in a singly linked list?
14. Find the length of a singly linked list?
15. Remove duplicate nodes in an unsorted linked list?
16. Remove duplicate elements from a sorted linked list?
17. How do you check if a given linked list contains a cycle? How do you find the starting node of the cycle?
18. How do you find the third node from the end in a singly linked list?

Binary Tree Interview Questions

1. How is a binary search tree implemented?
2. How do you perform preorder traversal in a given binary tree?
3. How do you traverse a given binary tree in preorder without recursion?
4. How do you implement a postorder traversal algorithm?
5. How do you traverse a binary tree in postorder traversal without recursion?
6. How are all leaves of a binary search tree printed?
7. How do you count the number of leaf nodes in a given binary tree?
8. How do the leaves of a binary search tree get printed?
9. How will you perform a binary search in a given array?
10. How are the leaf nodes in a given binary tree counted?
11. Print all nodes of a given binary Tree using inorder traversal without recursion
12. Check if a given binary tree is a binary search tree?
13. Check if a binary tree is balanced or not?
14. Convert a binary search tree to a sorted doubly-linked list.
15. Given a binary search tree and a value k, How do you find a node in the binary search tree whose value is closest to k.

When solving binary tree questions, having a good grasp of the theoretical concepts is vital.

Search and Sort Algorithmic Interview Questions

Search and Sort based questions are commonly asked in any programming round. You may be asked to implement various sorting algorithms, like the Bubble sort, Quicksort, merge sort, and asking to perform a binary search, etc.

1. Write a code for Bubble Sort algorithm?
2. Implement Iterative QuickSort Algorithm?
3. Implement the Insertion Sort Algorithm?
4. Implement the Radix Sort Algorithm?
5. Implement Sieve of Eratosthenes Algorithm to find Prime numbers?
6. Find GCD of two numbers using Euclid’s Algorithm?

Conclusion

Now that you understand the importance of data structures and algorithms, you can begin to improve your skill set. Practise more and more with set goals. Try experimenting with different patterns of problem-solving, establish familiarity with problems and see if you can crack a similar kind of problem which you have solved already, and you will be all set to face your job interview. It is also important to practice writing code on a paper or whiteboard and talk through your approach as you code.

Related Posts

• Leetcode 222 - Count Complete Tree Nodes
• Trees !!!
• Common Apple interview questions (with preparation tips)