Data Structure Interview Questions

By | May 16, 2020
Data Structure Interview Questions
Table of Contents show

Every year many computer science graduates apply for the job related to programming, coding and software development in big tech companies such as Google, Microsoft, Amazon, Netflix, etc., but many graduates have no idea what kind of programming questions they might have to face in the interview. Most of the coding interviews mainly comprised of Data Structure and algorithms questions because these topics are very basic and every computer science graduate supposed to know these topics. There is another reason for asking questions from Data Structure and Algorithm, for many tech giants having knowledge of a specific programming language could be irrelevant because the programming language could be obsolete with time, but data structure and algorithms remain the same.

Best Data Structure Interview Questions

Here in this article, we have covered the frequently asked Data Structure and Algorithms interview question.

Vamware

Question: What is Data Structure?

Answer: Data Structure refers to a technique or a way which can organize and manipulate data in a specific order, Arrays, LinkedList, Tree, and Graphs are the examples of Data Structure. As there are many examples of the data structure and each one has a specific technique to organize and relate to each data they have stored, we can use these Data structures according to our project need. 

Question: What is the key difference between File Structure and Storage Structure?

Answer:  Memory allocation;

In Storage Structure the RAM memory allocated to the variables and functions of the program, and as soon as the function ends the memory allocated to the variables also get deleted.

In File Structure, the file created by the program stored in the Secondary memory and remain intact until it gets deleted explicitly.

Question: Name all the basic operations we can apply in Data Structures?

Answer: 

  • Deletion – To delete an element from the structure.
  • Insertion- Insert a new element in the Structure
  • Searching- Search an Element in the Data Structure.
  • Sort- Arrange the structure in Ascending or Descending Order.
  • Traversal- Go through each element of the data structure.

Question: When can we use a binary search on Data Structure?

Answer:  Binary Search is a searching algorithm with a time complexity O(logn), and it can be applied on a sorted array or list. This algorithm search divided the array into 2 equal parts and search for the middle element.

Question: What is the key difference between the Breadth-First Search and Depth First Search Algorithm?

Answer:  Breadth-First Search (BFS) uses the queue data structure as an auxiliary data structure whereas the Depth First Search algorithm uses a stack data structure.

Question: What is a Linked List?

Answer:  A linked list is a linear data structure and a collection of nodes. In the linked list, each node is connected to the successor node except the rear one.

Question: What is Stack and tell some of its applications?

Answer:  A stack is a linear data structure that follows the principle of Last In First Out (LIFO), and according to the LIFO, the element which is inserted at the last will be retrieved first.

In stack, we represent the insertion operation with push and deletion operation with pop.

Stack Applications

  • Check the balanced parentheses in an expression.
  • To estimate the postfix expression
  • Reverse a string.

Question: How can we traverse an Array?

Answer:  Using a loop and the index value we can go through every element of the array, but the loop should be started from the 0 and end with the one less than the total size of the array.

Question: What is Queue and how it is different from the Stack?

Answer:  A Queue is a linear data structure which works on the principle of First In First Out (FIFO), according to FIFO, the element inserted first in the queue data structure would be retrieved first. On a queue, we can perform operations like Dequeue, enqueue, etc.

Difference between Queue and Stack.

  • A queue follows FIFO whereas stack follows LIFO principle.
  • If we perform the stack push and pop operation on a string, we get a reverse string but in the queue, we do not get any reverse string. 

Question: What are Arrays?

Answer: 

  • An array is a collection of homogeneous data elements, which mean we can only store similar data type in the array data structure.
  • When we declare an array, we also mention its size so the compiler can allocate a consecutive memory location to its element.
  • As all the elements of the array are stored in the consecutive memory location, we can access its element using index values.
  • The indexes value of array starts with 0 and ends with 1 less than the total size of the array.

Question: Where we apply the data structure?

Answer:  The data structure is applied everywhere and even every operating system needs data structure to design the basic operation. Data structure provides an efficient way to design operating systems, A.I machines, compilers, databases, graphics, and statistical tools.

Question: What do you understand by LIFO and FIFO?

Answer: 

  • LIFO: LIFO stands for Last In First Out, and it is a technique to implement a stack data structure where the element added last in the structure would be accessed first.
  • FIFO: FIFO stands for First In First Out and it is a contradiction of LIFO, in FIFO the element inserted first in the structure would be accessed first.

Question: What are binary trees?

Answer:  A binary tree is a tree data structure where each node has at most two child nodes, which also refer as right and left node.

Question: What is Dynamic Memory allocation and how it helps in managing data?

Answer:  In Dynamic Memory allocation, memory allocated to the program variables and functions at the run time.

Here, it combines separately allocated structure block to form a composite structure which can expand and contract according to the need. In simple words, in dynamic memory allocation data structures are allowed to store and remove data of arbitrary size in arbitrary order.

Question: Which data structure Recursion use to perform its task?

Answer:  Recursion is a technique in which a function calls itself again and again until a base condition becomes true, and at the backend Recursion technique use stack Data Structure to perform its task.

Question: What is a Binary Search Tree?

Answer:  A Binary search tree is an ordered Binary tree in which the left node key value is less than the parent node key value and the right node key value is greater than or equal to the parent node key value.

Question: What is the key difference between NULL and Void?

  • NULL: NULL is a value that represents empty or nothing.
  • Void: Void is a data type identifier and we cannot use it as a value.

Question: What are Multidimensional Arrays?

Answer:  The multidimensional array uses multiple indexes to store data, a multidimensional array can be represented as an Array inside an Array. Many real-world problems cannot be solved with the 1-D array so we use the Multidimensional array to tackle those problems.

Question: What is the difference between PUSH and POP?

Answer:  PUSH and POP operations applied to the stack data structure. PUSH is used to add an element at the top of the stack whereas POP is used to retrieve the last PUSHED element of the stack.

Question: What is an ordered list?

Answer:  In ordered List, each node of the list contains a key value and using this key value we can traverse through each node of the list, and this key-value forms an increasing order as the list is traversed.

Question: How does the variable declaration affect memory allocation?

Answer:  When we declare a variable with its data type then the compiler allocates memory to the variable according to its data type for example if we declare an integer data type variable then the compiler will allocate 4 bytes of memory to that variable.

Question: What are linear and Non-Linear Data Structures?

Answer: Linear Data Structure: A linear Data structure arrange all of its element in a sequential manner it is not necessary that they stored element in the consecutive memory location but the element stored sequentially. Array, Linked List, Stack, Queues, etc. are examples of Linear Data structure. The time complexity of traversal operation in a linear data structure always remains O(n).

Non-Linear Data Structure: Non-Linear data structure does not arrange their elements in sequential order, they use different levels to store their elements. The time complexity of traversal operation in the Non-Linear data structure is always greater than O(n).

Question: What is Merge sort?

Answer:  Merge Sort is a sorting algorithm that can arrange the data structure elements in ascending or descending order, and it works on the principle of Divide-and-Conquer.

Working:

In merge sort first, we divide the array or list into two halves and further continue to divide those equal halves into more equal halves until we get an atomic value.

Once we have the atomic values, now we combine those values in exactly the same manner as we broke them, but before it we compare them.

Question: Explain Data Abstraction and how it is different from Data Encapsulation?

Answer:  Data Abstraction is a property of Object-Oriented-Programming in which we try to hide the essential information from the user, by wrapping the complete program information in a single unit. Using the Class and object we can implement the Data Abstraction.

Data Abstraction is an integration of Data Encapsulation, Data Encapsulation deal with the concept of wrapping various data members and function members in a single unit and data abstraction deal with hiding data. It’s the Data Encapsulation which leads to the Data Abstraction.

Question: What are the key advantages of Linked List over an array?

Answer: 

  • A linked list can be used to hold different data types at once.
  • A linked list is more flexible, we can insert and delete elements very easily.
  • It is scalable and memory efficient.

Question: How can you insert a new element in the binary search tree?

Answer:  Steps:

  • First, we need to find the correct location where the new element will be linked.
  • We will traverse from the root node.
  • If the data is less than the key value, search for the empty location in the left subtree and insert data.
  • If the data is greater than the key value, search for the empty location in the right subtree and insert data.

Question: What is a linear search?

Answer:  A linear search is a searching algorithm with the worst time complexity of O(log n), where n is the total number of elements present in the list or array. In this algorithm, we check for each element and compare it with the target element.

Question: How does Selection sort work on an Array?

Answer:  Steps:

  • Here we start with the first element of the array, search for the smallest element in the array and replace it with the first position element.
  • Now we will move to the second position, and again search for the smallest element from the second position to the last position of the array and once we find the smallest element, we will swap it with the second element, now two elements in the array have been sorted.
  • Now we will move to the third element and continue to repeat the above steps until the array gets sorted.

Question: What is the advantage of Heap over a stack?

Answer: 

  • It is more flexible.
  • Memory space for the heap can be dynamically allocated and de-allocated as needed
  • Heap does not have a limit on the memory size 

Question: Explain recursion and what are the measures we should take care of when we create a recursive function.

Answer: When a function calls itself again and again then that scenario is known as recursion, and it is the most common and best technique used to traverse through the non-linear data structure. To design a recursive function, we should take care of two measures Base Condition and Progressive approach.

  • Base Condition: Each recursive function must have a base condition where it returns a single value or we can say that a condition from where it stops calling itself.
  • Progressive approach: A progressive approach is a statement that brings the recursive call near to the base condition.

Question: How signed and unsigned numbers affect memory?

Answer:  The signed number represents positive and negative Integers whereas the Unsigned number represents a positive number including 0.

Both signed and unsigned numbers take 8 bits of memory.

But in Signed number 1 out of 8 bits is used to represent the positive and negative sign that’s mean only 7 bits of the signed number are capable of holding numeric values that’s why the signed number has a range of -128 to 127.

On the other hand, Unsigned number use, the complete 8 bits to store the numeric value so it’s range varies from 0 to 255.

Question: What is a postfix expression?

Answer:  In postfix expression, the operator comes after its corresponding operands. For instance, in infix and mathematic expression if we want to apply an additional operation between two operands then we put the operator between the operands but in postfix, we put the operator after the operands.

In infix —–>A + B

Postfix expression —–> AB+

Question: What are the minimum numbers of nodes a binary tree can have?

Answer:  A binary tree can have a minimum of 0 nodes, which means it does not even have a root node.

Question: Does declaration mean fixed memory allocation for all the variables at compile time?

Answer: Except for the pointer variable, when we declare a variable the compiler allocates a temporary memory to the variables, but the actual memory allocation for the data occurs at the runtime.

Question: Name the different data structures where we can apply pointers.

Answer:  Pointers are normally used with nodes and the Data structure which consists of nodes use pointers.

  • Stack
  • Linked List
  • Trees
  • Graphs

use pointers.

Question: What is the AVL tree?

Answer: Adelson, Velski & Landis (AVL) tree is a self-balancing binary tree, which means if we insert a new element in the AVL tree the tree will re-balance it and keep its height as small as possible.

Question: What is the minimum number of queues we required to implement a priority queue?

Answer:  To create a priority queue, we at least require two queues, one for the sorting priorities and second for the actual storage of data.

Question: Name some of the sorting algorithms with their corresponding time complexities.

Answer: 

Algorithm Time Complexity
  Best Average Worst
Selection Sort Ω(n^2) θ(n^2) O(n^2)
Bubble Sort Ω(n) θ(n^2) O(n^2)
Insertion Sort Ω(n) θ(n^2) O(n^2)
Heap Sort Ω(n log(n)) θ(n log(n)) O(n log(n))
Quick Sort Ω(n log(n)) θ(n log(n)) O(n^2)
Merge Sort Ω(n log(n)) θ(n log(n)) O(n log(n))
Bucket Sort Ω(n+k) θ(n+k) O(n^2)
Radix Sort Ω(nk) θ(nk) O(nk)

Here n is the number of elements present in the array and k represents the maximum number length of the largest digit.

Question: What is dequeue?

Answer:  Dequeue stand for double-ended-queue, it is a queue data structure in which we can add and remove elements from either side of the queue.

Question: What is Bubble sort and how does it work?

Answer:  Bubble sort is a sorting algorithm with the worst time complexity O(n2).

In bubble sort, we compare each element with its adjacent element and swap them if there are not in order. This is known as bubble sort because each time the comparison takes place between two elements which act like bubbles. 

Question: What is notation is Data structure and how many types of notation are there?

Answer:  In Data structure how we write an expression and how the operator is written along with the operands is decide by the notation, and in Data structure we have three types of notations.

  • Infix notation- In this notation operator is written between the operands e.g. A + B
  • postfix notation/reverse polish Notation- In this notation operator is written after the operands e.g. AB+
  • Prefix notation/polish Notation- In this notation operator is written before the operands e.g. +AB

Question: Name the parts of the linked list.

Answer:  A linked is a collection of nodes where each node except the end one point to another node. The first node of the linked list is known as Head and the last node is known as Tail.

Question: Explain the various types of Linked List present in Data Structure.

Answer: 

  • Singly Linked List- In Singly linked list each node point to its success node except the last one, here the last node point to the NULL value.
  • Doubly Linked List- In this linked list each node contains two pointers, one point to the next node and other points to the previous node.
  • Circular linked list- Circular linked list is similar to the singly linked list but here the last node point to the head node rather than pointing to the NULL value.

Question: What is a Graph?

Answer:  A Graph is a non-linear data structure which comprises of nodes and arcs, here node represents the vertices and arcs represent the edges. And, the arc act as a bridge between the two nodes or vertices.

Question: What is the Huffman algorithm?

Answer:  Huffman’s algorithm is used for creating extended binary trees that have minimum weighted path lengths from the given weights. It makes use of a table that contains the frequency of occurrence for each data element.

Question: How to form a queue data structure using stack and vice versa?

Answer:  Queue Using Stack:

We require two stacks to form a queue like data structure, the first stack takes the element by push operation and once the stack is full we perform the pop operation on the first stack and simultaneously we use the push operation on the second stack and push all the popped element of the first stack into the second stack. So, when we pop from the second stack it will act as a queue, First Element which was pushed in the first stack will be popped first from the second stack.

Stack using Queue:

With the help of two queues data structures, we can form a stack-like data structure. The first queue is used to insert the element in the queue and the second queue will store the popped elements of the first queue, that how the second queue will pop the last entered element first and the complete structure act as a stack data structure.

Question: Define the different types of algorithms approach.

Answer: 

  • Divide and Conquer: In this, we try to divide the problem into small sub-problems and try to solve those small subproblems independently and then join them back.
  • Dynamic Programming: Dynamic programming is similar to the divide and conquer approach but there we solve all the subproblems together.
  • Greedy Approach: In the Greedy approach, we try to solve the problem by choosing the best option.

Question: What is interpolation Search techniques?

Answer:  The interpolation search technique is a searching algorithm which is similar to the Binary search algorithm that divides the array into two parts, but here the interpolation does not divide the array into two equal half rather than it tries to divide the array from that position from where it can get near to the solution.

The interpolation search technique uses both Divide and Conquer and Greedy Approaches.

Question: How can you check a given Binary tree is a BST or not?

Answer:  We perform the in-order traversal on the binary tree and store each visited element in an array and if we get a sorted array then it would be a Binary Search tree else not.

Question: What is Fibonacci search?

Answer:  Fibonacci search is a search algorithm that applies to a sorted array. It makes use of a divide-and-conquer approach that can significantly reduce the time needed in order to reach the target element.

Conclusion

Here we have provided the top 50 most frequent Data Structure interview questions; we recommend you al least go through these questions before you go for a technical interview.

If you like this article or have any suggestions related to it you can let us know by filling the comment box.

You might be also interested in:

Leave a Reply

Your email address will not be published. Required fields are marked *