Top 50 data structure interview questions and answers that tech giants ask!
Data Structures and Algorithms (DSA) is an important part of Computer Science that deals with the organization of data values and code optimization. To understand more about DSA, let’s break down the word DSA into two parts:
A data structure is used for the storage and organization of data values for further use in an application. Talking about an algorithm, it is a stepwise process to solve a problem.
Now, let’s look at some of the most commonly used data structures:
Applications of Data Structures and Algorithms
Data Structures are used in a wide variety of fields. Some of the important applications include:
Importance of DSA for interviews
DSA is paramount as in today’s world, companies deal with a lot of data. As coders, you should know about code optimization to ensure space and time resources are utilized efficiently. Also, for cracking product-based company interviews which offer a high-paying job, DSA is a must.
Let’s look at some important product-based companies that test DSA:
*Median pay for workers with 0-5 years of experience
Source: Payscale
Useful resources to learn DSA
Here is a list of some of the best resources that can help you learn the inside-out of the DSA:
Now, let’s look at some of the important DSA questions.
Top 50 must-know DSA questions and answers
1. What are data structures?
A data structure is a way of storing and organization of data values for further use in an application. Examples include Graph, Trees, Arrays, Linked List, etc.
2. Name different types of data structures?
Data structures are of two types:
3. What is the use of dynamic Data Structures?
Dynamic data structures are flexible and size changes can occur during insertion or deletion operations. Dynamic data structures play a key role in programming because they provide the programmer with the flexibility to adjust the memory consumption of programs.
4. Name various operations that can be performed in DSA.
Insert: Here, we add a new data item in a data structure.
Search: In this, we find an element in the data structure.
Sort: Simple sorting like arranging values in ascending or descending order. For example, arranging values in an array.
Delete: Here, we delete unwanted data points in a data structure.
Traversal: We access each data item exactly once so that it can be processed for further use.
5. What are Infix, prefix, Postfix notations?
Infix: We write expressions in infix notation, e.g. x+y - z, where operators are used in-between operands. For humans, it goes well, but for computing devices, it’s not preferred.
Prefix: Here, the operator is prefixed to operands, i.e. operator is written ahead of operands. For example, +xy instead of x+y.
Postfix: Here, we use the operator after the operands. For example, X*Y is written as XY*.
6. What are the types of searching used in Data Structures?
7. What is an array?
An array is a collection of data points of the same type stored at contiguous memory locations.
For example, an array of integers like 1,2,3,4,5. This array has 5 elements.
The index of an array usually starts with 0.
8. What are dynamic arrays?
A dynamic array is an array with a modification that is automatic resizing. This means that the array expands when we add more elements. This helps to provide flexibility as size is not fixed. So, there’s no need to know the size in advance.
9. Name some characteristics of Array Data Structure.
10. What is a linked list?
This is similar to an array but it consists of a node that has two fields:
Data Field: For storing data values.
Reference Field: For storing address.
A linked list is used in the next feature of a music player.
11. What are the different types of linked lists?
Ans: The different types of linked lists are:
12. What are trees in DSA?
A collection of nodes is a tree. A node is a data point connected with other points with the help of edges. The top of a tree is the root node. Applications of trees include indexing in databases.
13. What are graphs and their uses?
A graph is a collection of nodes connected to one another via edges. It forms a network of nodes like in the case of a journey from one source to a destination.
Uses:
14. What's the difference between the data structure Tree and Graph?
Ans: A tree structure is connected and can never have loops whereas in the graph there are no such constraints. A tree provides information about the relationship between nodes in a hierarchical manner and the graph follows a network model.
15. What is the LIFO and FIFO principle?
LIFO: (Last-In-First-Out) Last inserted element is removed first in the LIFO principle. Example: Stack follows LIFO.
FIFO: (First-In-First-Out) First Element (first to be inserted) is taken out first.
Example: Queue follows FIFO
16. What is a queue?
A queue in English is a line. Similarly, in DSA, it is a line of data values that follows the FIFO ( First in First out) principle. Insertion is done at the rear end and deletion at the front end.
17. What is a priority queue?
A priority queue is like a normal queue of elements but here each element has some priority. The elements in the priority queue occur in this order only.
Say, we have some values like 1, 2, 7, 8, 14, 31 inserted in a priority queue with an ordering based on least values to the greatest value. Therefore, the 1 number will have the highest priority while 31 will have the lowest priority.
18. What is a stack?
A stack is a linear data structure having values that are inserted as per the LIFO principle. To make the point more clear, imagine a pile of chairs. You want to add another chair, for that, you will have to add the chair at the top. That’s a stack. Insertion or deletion takes place at the top of the stack of data values.
19. State the difference between stack and queue?
20. What is a heap in DSA?
A heap data structure is a complete binary tree that follows a specific order. Heaps are of two types:
21. What is a binary heap?
22. What is the meaning of the AVL tree?
An AVL tree is a type of binary search tree. It is named after its inventors Adelson, Velskii, and Landis. An AVL tree is a balanced binary search tree where the height of the two subtrees of a node differs by a maximum of one unit.
23. What do you mean by Hash Table?
A Hash table is a data structure used to store data points in an associative manner. The values are stored in an array format. Hash tables are used to store keys/value pairs
24. What is the complexity of a Hash Table?
Hash tables provide constant-time O(1) lookup on average, irrespective of the number of items(n) in the table.
25. What Data Structures make use of pointers?
26. What is a dequeue?
A dequeue is a double-ended queue. This queue data structure includes elements that can be inserted or removed from either end.
27. What is the meaning of the stack overflow condition?
When a stack is completely full and we try to insert more elements onto the stack then this condition is called stack overflow condition. Here, top=maxsize-1, and no further elements can be inserted.
28. What is the postfix form of (X + Y) * ( Z - C)
The postfix form of the given expression is XY+ZC-*
29. What is a Balanced Tree and why is that important?
A tree is perfectly height-balanced if the left and right subtrees of any node are of the same height. We can also say that a tree is height-balanced if the heights of the left and right subtrees of each node differ by a maximum of one unit.
30. What are the Data Structures that are used to represent graphs?
31. What operations can be performed on stacks?
32. Why use queues?
Queues are important in computer science. They are useful in transport, and operations research. They are also useful in a case where resource sharing takes place among a myriad of consumers. For example, FCFS scheduling.
33. What is linear search?
Linear search is a technique in which we traverse a list in a sequential manner to find an element. When we find the element that is required, we return the index or position of that element.
34. What is binary search?
In this type of search technique, we divide the sorted array or list into two halves. This is done to save time in searching. Here, we consider arrays in sorted form only.
35. What are the time complexities of linear search and binary search?
Linear Search-O(N) Binary Search- O(log 2 N)
36. Tell me about tree traversal.
Tree traversal is a process that goes through the entire tree in a particular manner. Depending upon the order of traversal, we have different types:
37. How does Kruskal's algorithm work?
Kruskal algorithm treats a graph as a forest and every node as an individual tree. A tree connects to another only and only if it has the least cost among all available choices without violating Minimum Spanning Tree (MST) properties.
38. How does Prim's algorithm find a spanning tree?
Prim's algorithm treats each node as a single tree and continues to add new nodes to the spanning tree from the given graph.
39. What is a minimum spanning tree (MST)?
It is a spanning tree that has the minimum weight among all the spanning trees of the same graph.
40. Explain the Tower of Hanoi Problem.
41. What are recursive algorithms?
Recursion in general is a function calling itself. Extending the same logic for Algorithms, we can say that an algorithm that calls itself is a recursive algorithm. One good example of their use would be searching through a file system. Usually, they are used when the iterative approach is not useful for complex problems.
42. Explain why stack is a recursive data structure?
A stack is a recursive data structure because:
43. What is merge sort time complexity?
The time complexity of MergeSort is O(n*log n)
44. What is shell sort?
Shell sort is a sorting algorithm based on the insertion sort algorithm.
This algorithm is highly efficient in sorting. This algorithm tries to avoid large shifts as in the case of insertion sort if the smaller value is to the far right and has to be moved to the far left.
45. What is quicksort time complexity?
Worst-case time complexity is O(n^2)
46. What is a Red-Black Tree?
A red-black tree is a binary tree that has nodes represented by two colors: red and black. The tree follows specific properties.
These include:
47. When does the worst case of QuickSort occur?
It occurs when the picked pivot is an extreme (smallest or largest) element. Usually, when the input array is sorted or reverse sorted, it also leads to the worst case.
48. Which data structures are used for the BFS and DFS of a graph?
49. What do you mean by BFS and DFS?
BFS Algorithm stands for Breadth-First Search. It is a vertex-based technique for finding the shortest path in the graph. For BFS, we use a Queue data structure.
DFS Algorithm stands for Depth First Search. It is an edge-based technique. In DFS, traversal can be started from any node. For DFS, we use a stack data structure.
50. What is the maximum number of nodes in a binary tree of height k?
Ans: The maximum nodes in a binary tree are: 2k+1-1 where k >= 1.
Recommended reading list: