Table of contents
The tech interview stage of a job requires a thorough preparation before you can impress the interviewer. Right from knowing everything about the technical subject to apprising the interviewers about your previous achievements and projects, you are required to do everything that can convince them about your knowledge and skills.
In this article, we have prepared a list of most frequently asked Data Structure interview questions and answers.
1) What is Data Structure?
Data structure is a fundamental concept of any programming language, essential for algorithmic design. It is used for the efficient organization and modification of data. DS is how data and the relationship amongst different data is represented, that aids in how efficiently various functions or operations or algorithms can be applied.
2) What are the applications of Data Structure?
Data structures form the core foundation of software programming as any efficient algorithm to a given problem is dependent on how effectively a data is structured.
Identifiers look ups in compiler implementations are built using hash tables. The B-trees data structures are suitable for the databases implementation.
Some of the most important areas where data structures are used are as follows:
- Artificial intelligence
- Compiler design
- Machine learning
- Database design and management
- Numerical and Statistical analysis
- Operating system development
- Image & Speech Processing
3) Tell us about linked list.
A linked list can be defined as a chain of nodes wherein each node is connected to the next one.
4) Give us one advantage of linked list?
One inherent advantage of linked list is that it is very easy to modify irrespective of the number of elements that are there in the list.
5) What is the difference between PUSH and POP?
PUSH and POP operations specify how data is stored and retrieved in a stack.
PUSH: PUSH specifies that data is being "inserted" into the stack.
POP: POP specifies data retrieval. It means that data is being deleted from the stack.
6) Where is data structure majorly used?
Simplistically speaking, data structures are involved in all areas when data is engaged. Some of the prominent areas where it is applied are artificial intelligence, database management, statistical analysis, etc.
7) Are linked lists considered linear or non-linear data structures?
A linked list is considered both linear and non-linear data structure depending upon the situation.
On the basis of data storage, it is considered as a non-linear data structure. On the basis of the access strategy, it is considered as a linear data-structure.
8) What do you mean by LIFO?
LIFO stands for Last In First Out. It means that the data which was stored last would be the first one to be extracted.
9) What are the various operations that can be performed on different Data Structures?
Insertion ? Add a new data item in the given collection of data items. Deletion ? Delete an existing data item from the given collection of data items. Traversal ? Access each data item exactly once so that it can be processed. Searching ? Find out the location of the data item if it exists in the given collection of data items. Sorting ? Arranging the data items in some order i.e. in ascending or descending order in case of numerical data and in dictionary order in case of alphanumeric data.
10) Which Data Structure Should be used for implementing LRU cache?
We use two data structures to implement an LRU Cache. Queue which is implemented using a doubly linked list. The maximum size of the queue will be equal to the total number of frames available (cache size). The most recently used pages will be near rear end and least recently pages will be near front end. A Hash with page number as key and address of the corresponding queue node as value. See How to implement LRU caching scheme? What data structures should be used?
11) What are the advantages of Linked List over an array?
The size of a linked list can be incremented at runtime which is impossible in the case of the array. The List is not required to be contiguously present in the main memory, if the contiguous space is not available, the nodes can be stored anywhere in the memory connected through the links. The List is dynamically stored in the main memory and grows as per the program demand while the array is statically stored in the main memory, size of which must be declared at compile time. The number of elements in the linked list are limited to the available memory space while the number of elements in the array is limited to the size of an array.
12) Tell us something about binary trees.
A binary tree is a form of data structure. It has two nodes, namely the left node and the right node.
13) How to check if a given Binary Tree is BST or not?
If in order traversal of a binary tree is sorted, then the binary tree is BST. The idea is to simply do in order traversal and while traversing keep track of previous key value. If current key value is greater, then continue, else return false. See A program to check if a binary tree is BST or not for more details.
14) What is a queue?
A queue is a form of data structure that induces a list of data. In this form of structure, the old elements are removed from one end while the new ones keep getting added to the other end.
15) What exactly do you mean by merge sort?
In merge sort, adjacent data elements are merged into one to form a bigger list. These lists are further merged into another big list and the process keeps happening until a single list is obtained.
16) What is the least number of nodes that a binary tree can have?
A binary tree can have zero nodes as the least number. Further, the number can be increased to 1 or 2 nodes. Data structure is a large concept. A range of questions can be extracted from this data storage model. Keeping that in mind, we have another set of questions below that you should prepare for the interview.
17) What are the scenarios in which an element can be inserted into the circular queue?
If (rear + 1)% maxsize = front, the queue is full. In that case, overflow occurs and therefore, insertion can not be performed in the queue. If rear != max - 1, the rear will be incremented to the mod(maxsize) and the new value will be inserted at the rear end of the queue. If front != 0 and rear = max - 1, it means that queue is not full therefore, set the value of rear to 0 and insert the new element there.
18) What do you know about stack?
In stack, the newest data element is accessed first. As the name suggests, all old elements are pushed downwards leaving the last added one on the top.
19) What is a dequeue?
Dequeue (also known as double-ended queue) can be defined as an ordered set of elements in which the insertion and deletion can be performed at both the ends, i.e. front and rear.
20) Define the graph data structure?
A graph G can be defined as an ordered set G(V, E) where V(G) represents the set of vertices and E(G) represents the set of edges which are used to connect these vertices. A graph can be seen as a cyclic tree, where the vertices (Nodes) maintain any complex relationship among them instead of having parent-child relations.
21) Which data structures are used in BFS and DFS algorithm?
In BFS algorithm, Queue data structure is used. In DFS algorithm, Stack data structure is used.
22) What are the applications of Graph data structure?
The graph has the following applications:
Graphs are used in circuit networks where points of connection are drawn as vertices and component wires become the edges of the graph. Graphs are used in transport networks where stations are drawn as vertices and routes become the edges of the graph. Graphs are used in maps that draw cities/states/regions as vertices and adjacency relations as edges. Graphs are used in program flow analysis where procedures or modules are treated as vertices and calls to these procedures are drawn as edges of the graph.
Some Extra questions for your preparation :
- • What do you understand by dynamic data structures?
- • Differentiate between Null and Void
- • Cite the difference between Stack and Array.
- • How would you define dequeue?
- • Tell us about the working of a selection list.
- • What do you know about graph?
- • What exactly is an AVL tree?
- • Do you know anything about Huffman’s algorithm?
- • Tell us about recursive algorithm.
While appearing for your interview, Be confident and approach the day with an optimistic outlook. Present yourself with smile and take your time to think about the solutions, do not hurry yourself.
Thanks for the reading. All the best!