DSA Interview Questions
This website contains Data Structure interview questions with answers. We have given Data Structure interview questions faced by freshers and experienced in real interviews in IT industries.Dear readers, these Data Structure Programming Interview questions have been specially designed so that you can get acquainted with the nature of the questions you may be ask during your interview.
1. What is a Data Structure?
Answer:- Data structure is a way that specifies how to organize and manipulate the data so that the data can be used efficiently. It also specify the relationship between them. Some example of data structure are - array, linked list, stack etc.
2. What are linear and non linear data Structures?
Answer:-
Linear Data Structure: If all the elements are arranged in sequential order then it is called linear data strucutre for example Array, Linked List.
Non Linear Data Structure If the elements are not arranged in sequential order then it is called non linear data structure for example Tree, Graph.
3. How Linked list is different from array?
Answer:- Differences between array and linked list are -
1) Arrays are index based data structure where each element is associated with an index. On the other hand, Linked list relies on references where each node consists of the data and the references to the previous and next element.
2) The size of the arrays is fixed, Linked Lists are Dynamic in size.
3) In array elements are accessed randomly using index while in linked list elements are accessed in sequence.
4) Insertion and Deletion operations are expensive in array whereas it can be easily done in linked list.
5) Extra memory space is required in linked list for storing address of next node.
6) Element location is allocated during compile time in array while in linked list it is done during run time.
4. What are the criteria of algorithm analysis?
Answer:- Algorithms are analyzed on the basis of 2 factors - time and space. Time specify how much execution time and space specify how much extra space is required by the algorithm.
5. What are the operations that can be performed on a data-structures?
Answer:- Following operations can be performed -
Insertion :Adding a new data item.
Deletion :Deleting the existing data item.
Traversal :Accessing each data item.
Searching :Finding a particular data item.
Sorting :Arranging the data item in a particular sequence.
6. Explain the difference between Divide & Conquer and Dynamic programming?
Answer:- In divide and Conquer approach we divide the problem into minimum possible sub-problem and solve them independently. Divide-and-Conquer is a Top-Down Technique. In Dynamic Programming we diving the problem to a minimum possible sub-problem and solve them combinedly. Dynamic Programming is a Bottom-Up Technique.
7. Which data structure is used to perform recursion?
Answer:- Stack is used to perform recursion due its Last in First Property. Recursion makes use of system stack for storing the return addresses of the function calls.
8. What are the operations that can be performed on a stack?
Answer:- Various operations that can be performed on a stack are -
Push Operation : Inserting the data item into the stack.
Pop Operation : Deleting the data item from the stack.
Peek Operation: Get the data item which is on the top of the stack, without removing it.
9. Explain Infix, prefix, Postfix notations?
Answer:-
In Infix Notation operators are written in-between their operands. For example -> A + B * C + D.
In Prefix Notation operators are written before their operands. For example -> + + A * B C D.
In Postfix Notation operators are written after their operands. For example -> A B C * + D +.
10. What is a queue in data-structure?
Answer:- Queue is a linear data structure where the elements are inserted from one end called REAR and deleted from the other end called as FRONT. It follow First In First Out (FIFO) i.e the first element that is added to the queue is the first one to be removed.
11. How to implement a stack using queue?
Answer:- Stack can be implemented using 2 queues. To push an item in the stack, we first move all elements from the first queue to the second queue, then push new item into the first queue, and finally move all elements back to the first queue. This ensures that the new item lies at front of the queue and hence would be the first one to be removed. To pop an item from the stack, we simply return the front item from the first queue.
12. What is Brute Force algorithm?
Answer:- Brute force means that you will go through all possible solutions extensively. For example, in a chess game, if you know you can win in two moves, the brute force will go through all possible combination of moves, without taking anything in consideration. So the little pawn in the back that cannot influence the outcome will still be considered.
13. What is the wrost case complexity of merge sort and quick sort?
Answer:-
Merge sort : n*log(n)
Quick sort : n^2
14. What is shell sort?
Answer:- Shell sort is a is a generalized version of insertion sort. It is a highly efficient sorting algorithm. In shell sort we break the original list into a number of smaller sublists, each of which is sorted using an insertion sort.
15. Which data structures are used for BFS and DFS of a graph?
Answer:- Queue is used for BFS while Stack is used for DFS.
16. What is a binary search tree?
Answer:- Binary search tree is a binary tree in which all nodes of left subtree are less than root node and all nodes of right subtree are more than root node.
17. What is an AVL Tree?
Answer:- AVL tree is a self-balancing Binary Search Tree where the difference between heights of left and right subtrees cannot be more than one for all nodes.
18. What is a spanning tree?
Answer:- A spanning tree is a subset of a graph, which has all the vertices covered with minimum possible number of edges. It cannot be disconnected and does not have cycles.
19. What is hashing technique?
Answer:- Hashing is a technique where search time is independent of the number of items or elements. In this technique a hash function is used to generate an address from a key. The hash function takes a key as input and returns the hash value of that key which is used as an address index in the array.
20. what is heap data structure?
Answer:- Heap is a tree based data structure which satisfy the heap property. Heap can be of 2 type -
Min Heap : In this the value of the root node is less than or equal to either of its children. The same property must be recursively true for all sub-trees in that Binary Tree.
Max Heap : In this the value of the root node is greater than or equal to either of its children. The same property must be recursively true for all sub-trees in that Binary Tree.
21. What is interpolation search technique?
Answer:- The Interpolation Search is an improvement over Binary Search for instances, where the values in a sorted array are uniformly distributed.Interpolation search may go to different locations according to the value of the key being searched.
For example :- If the value of the key is closer to the last element, interpolation search is likely to start search toward the end side.
22. What is tower of hanoi?
Answer:- The Tower of Hanoi is one of the most popular puzzle of the nineteenth century. It consists of three pegs mounted on a board together and consists of disks of different sizes. At first, all the disks are kept on one peg(say peg 1) with the largest peg at the bottom and the size of pegs gradually decreases to the top.
The goal of this puzzle is to transfer all the disks from one peg to another in order of size, placing the largest one at the bottom.
The rule of the puzzle is that we can move a disk from one peg to another as long as the disk is never placed on the top of the smaller one.
23. What is the primary advantage of a linked list?
Answer:- Linked List can grow and shrink during run time. Insertion and Deletion Operations are Easier.
24. What is a dequeue?
Answer:- dequeue stands for Double-ended queue.In dequeue elements can be inserted or removed from either end.
25. What is Huffman’s algorithm?
Answer:- Huffman coding is a lossless data compression algorithm. In this algorithm, a variable-length code is assigned to input different characters.Most frequent characters have the smallest codes and longer codes for least frequent characters.
Also check :
Discussion