YouTube Icon

Interview Questions.

Top Data Structure Interview Questions and Answers - Sep 08, 2021

fluid

Top Data Structure Interview Questions and Answers

A records structure can be any organization, management, and storage layout of statistics that permits efficient access and modification. It is a group of records values, relationships amongst them, and the numerous features or operations that can be implemented to the data.

Data systems are a foundational concept of programming that is immensely utilized in set of rules layout. Hence, it's far important for any programmer, irrespective of the programming language, to have an excellent know-how of facts structures.

Top Data Structure Interview Questions and Answers

Any programming language interview could have a few or many questions based totally on data systems. Here are the pinnacle records shape interview questions and answers with their respective answers for you:

Question: What do you understand through a records shape?

Answer: A statistics structure gives a handy way of organizing as well as manipulating the records. Simply positioned, it permits the information to be used in an effective manner. There is a galore of facts systems and each of them is appropriate for a awesome set of applications.

For example, compiler implementations use hash tables for looking up identifiers. Similarly, B-timber are suitable for the implementation of databases. Data systems are surely carried out to all areas counting on facts. Some of the maximum critical ones are:

Artificial intelligence

Compiler design

Database control

Graphics

Numerical evaluation

Operating gadget

Statistical evaluation

Question: How does a linear records structure vary from a non-linear statistics shape?

Answer: If the factors of a statistics shape shape a series or a linear list then it's far known as a linear records structure. On the opposite hand, non-linear facts structures are those in which the traversal of nodes is performed in a non-linear manner.

Arrays, related lists, stacks, and queues are examples of linear records systems, while graphs and trees are the ones of non-linear data structures.

Question: What are the various packages of Data Structures?

Answer: In records systems, information is organized in a way that makes it green for use. Some sensible programs of statistics structures are:

Storing records in a tabular form. For example, touch information of a person. This is done thru arrays.

Arrays are widely used in photograph processing and speech processing.

Music gamers and image sliders use Linked Lists to transport to next or previous gadgets.

The maximum not unusual application of the records shape, Stack is the undo operation, wherein the closing object suggests up first.

A Queue is used for task scheduling, the arrangement of information packets for communication.

A Tree is utilized by the Decision Tree algorithm which is widely used for gadget gaining knowledge of and choice making.

Technologies like Blockchain, cryptography are based totally on Hashing algorithms.

Matrices are widely used to represent information and plotting graphs, acting statistical analysis.

Question: Explain the difference between file structure and storage structure?

Answer: 

File Structure: A hard disk or external device (such as USB), stores data that remains intact until manually deleted. Such a representation of records into secondary or auxiliary reminiscence is called a file structure. 

Storage Structure:  In this kind of structure, data (variables, constants, and so forth.) are saved within the major memory, i.E. RAM, and is deleted once the feature that makes use of this records receives finished.

Question: Please enumerate the diverse operations that may be carried out on a facts shape.

Answer: Following are the various operations that can be accomplished on a information shape:

Deletion – Deleting an present detail from the records shape

Insertion – Adding a brand new element to the facts structure

Searching – Find the area of an element, if it exists, in the information shape

Sorting – Arranging elements of the records structure in:

Ascending or descending order for numerical information

Dictionary order for alphanumeric data

Traversal – Accessing every detail of the statistics shape as soon as for processing

Question: Explain the postfix expression.

Answer: In a postfix expression, the operator is fixed after the operands. Some examples are:

B++ (i.E. B+B)

AB+ (i.E. A+B)

ABC*+ (i.E. A+B*C)

AB*CD*+ (i.E. A*B + C*D)

Question: Can you tell which statistics systems are used for BFS and DFS of a graph?

Answer: BFS (Breadth-First Search) of a graph makes use of a queue. Although DFS (Depth First Search) of a graph uses a stack, it may additionally be implemented the usage of recursion that makes use of characteristic call stack.

Question: Explain a multidimensional array.

Answer: If an array has extra than two dimensions, it's miles referred to as a multidimensional array. They also are known as an array of arrays. For example, a 3-D array will appear to be,

   int 3darr[10][20][30] 

– this array can shop 10*20*30 factors.

Assigning values

int ndarr[2][3][5] = 1,2,4,five,5,6,7,9, 6,five,4,three, 1,1,three,four, 2,three,4,6, 5,6,7,8;

Accessing elements

To get admission to each detail, we want 3 nested loops, say i,j,ok, in order that we are able to get the cost as ndarr[i][j][k]

Question: Please give an explanation for stack and also point out some of its important packages.

Answer: Stack is a linear records structure that follows either LIFO (Last In First Out) or FILO (First In Last Out) method for gaining access to factors. Push, pop, and peek are the basic operations of a stack.

Some extremely good packages of a stack are:

Check for balanced parentheses in an expression

Evaluation of a postfix expression

Implement two stacks in an array

Infix to postfix conversion

Reverse a string

Question: What is a queue? How is it different from a stack?

Answer: A queue is a shape of linear structure that follows the FIFO (First In First Out) approach for getting access to factors. Dequeue, enqueue, the front, and rear are fundamental operations on a queue. Like a stack, a queue may be implemented using arrays and connected lists.

In a stack, the object that is maximum currently delivered is eliminated first. Contrary to this, the item least lately introduced is removed first in case of a queue.

Question: What do you recognize by way of a binary search? What is the first-rate state of affairs of the usage of it?

Answer: A binary search is an algorithm that starts with looking in the middle element. If the middle element isn't the target detail then it in addition checks whether to maintain looking the decrease 1/2 of the better half of. The method continues till the target detail is discovered.

The binary seek works satisfactory while applied to a listing with sorted or ordered factors.

Question: Could you give an explanation for how to reference all of the elements in a one-dimension array?

Answer: We can reference all of the factors in a one-dimension array the usage of an listed loop. The counter runs from zero to the maximum array size, say n, minus one. All elements of the one-measurement array are referenced in sequence through the usage of the loop counter because the array subscript.

Question: Please give an explanation for what do you apprehend by way of FIFO and LIFO?

Answer: Both FIFO and LIFO are tactics to accessing, storing, and retrieving factors from a information shape. LIFO stands for Last In First Out. In this method, these days stored records is the one to be extracted first.

FIFO is a contraction for First In First Out. Following this technique, the facts this is stored the least recently might be extracted first.

Question: What is a Linked List Data structure

Answer: In a Linked List statistics, factors are saved linearly, but the bodily placements do now not deliver the order in the memory; rather, each element points to the next node. The ultimate one points to a terminator indicating the give up of the list. There are many sorts of Linked List – unmarried, double, round, a couple of. A easy singly LinkedList may be drawn as:

Linked List Data structure

Question: Do you know how does dynamic memory allocation help in dealing with information?

Answer: Dynamic reminiscence allocation allows in storing simple structured records sorts. Moreover, it is able to combine separately allocated structured blocks for forming composite structures that settlement and increase as required.

Question: What is the distinction among NULL and VOID?

Answer: While NULL is a value, VOID is a statistics kind identifier. A variable assigned with a NULL price represents an empty cost. The VOID is used for identifying hints having no preliminary length.

Question: If you are the usage of C language to put in force the heterogeneous related list, what pointer kind need to be used?

Answer: We can use void recommendations. Unsigned char guidelines are some other alternative. This manner, we can save any records type in the list. Example,

  struct a{
   struct a *next;
   s_ize d_size;
  }

Question: How does a POP operation vary from a PUSH operation?

Answer: Both PUSH and POP operations pertain to a stack. Data is brought to the stack the use of the PUSH operation, whilst it's far retrieved using the POP operation.

Question: Could you give an explanation for how does variable assertion have an effect on reminiscence allocation?

Answer: The overall amount of memory to be allocated or reserved in the case of a variable statement relies upon on the facts type used. For instance, putting forward an integer type variable reserves 4 bytes of reminiscence space whilst putting forward a double variable reserve 8 bytes of the to be had reminiscence.

Question: Write the syntax in C to create a node within the singly linked list.

Answer: 

newNode = Node(data);    //creates a new node.

Question: Please provide an explanation for the idea of statistics abstraction.

Answer: Data abstraction allows in dividing complicated facts problems into smaller, smooth-to-control elements. It begins with specifying all of the concerned data gadgets and the diverse operations to be achieved at the same without stressing an excessive amount of on the manner information is stored.

Question: Can you write a C application to insert a node in a circular singly listing at the beginning?

Answer: In a round LinkedList, the closing pointer points to the head (first node). For this, we use an outside pointer that factors to the remaining node, and the final->subsequent points to the first node. We take the remaining node pointer as it saves us from traversing the entire list even as inserting a node inside the beginning or cease. 

Program steps

Create a node N

N->next = last->subsequent

remaining->subsequent = N

Code 

 struct Node *addBeginning(struct Node *last, int data) 
{ 
 /*check if list empty, if so create a node, else proceed  as below*/
  // dynamically create a node
  struct Node *N 
        = (struct Node *)malloc(sizeof(struct Node)); 
  // Assign the data. 
  N -> data = data; 
  // last pointer becomes the first node 
  N -> next = last -> next; 
  last -> next = N; 
  return last; 
}

Question: How will you insert a new item in a binary seek tree?

Answer: As a binary search tree doesn’t allow for duplicates, the brand new item to be inserted need to be particular. Assuming it's miles, we can continue with checking whether the tree is empty or now not. If it's far empty, then the new object could be inserted inside the root node.

However, if the tree is non-empty then we can refer to the important thing of the brand new item. When it's miles smaller than the foundation item’s key, the new item might be brought to the left subtree. If the brand new item’s key's larger than the root item’s key, then the brand new item is inserted into the proper subtree.

Question: Could you provide an explanation for how does the choice sort work on an array?

Answer: The selection type starts offevolved with locating the smallest element. It is switched with the detail present at subscript 0. Next, the smallest detail in the remaining subarray is placed and switched with the detail residing in the subscript 1.

The aforementioned method is repeated until the biggest element is located on the subscript n-1, wherein n represents the scale of the given array.

Question: Write the pseudocode to perform in-order traversal on a binary tree.

Answer: In-order traversal is a intensity-first traversal. The approach is known as recursively to carry out traversal on a binary tree. The code is as follows:

struct btnode
{
    struct btnode *left;
    struct btnode *right;
}
*root = NULL, *temp = NULL;
void inorder(struct btnode *temp)
{
    if (root == NULL)
    {
        printf("Root is empty");
        return;
    }
    if (temp->left != NULL)    
        inorder(temp->left);
    if (temp->right != NULL)    
        inorder(t->right);
}

Question: Write the recursive C feature to matter the number of nodes present in a binary tree.

Answer: 

static int counter = 0;
int countnodes(struct node *root)
{
    if(root != NULL)
    {
        countnodes(root->left);
        counter++;
        countnodes(root->right);
    }
    return counter;
}

Question: Write a recursive C feature to calculate the height of a binary tree.

Answer: To locate the height the use of recursion, we discover the most of the height of subtrees on the left and right facets after which upload it with the basis. 

struct node
{
int data;
struct node *left;
struct node *right;
};
int height(struct node *node)
{
if(node == NULL)
return 0;
else
{
int l_side;
int r_side;
l_side = height(node -> left);
r_side = height(node -> right);
if(l_side > r_side)
{
 return l_side + 1;
}
else
 return r_side + 1;
}

}

Question: Do you understand how the reminiscence is laid low with signed and unsigned numbers?

Answer: For signed numbers, the first bit is reserved for indicating whether the number is fantastic or terrible. Hence, it has one bit less for storing the value. Unlike signed numbers, unsigned numbers have all of the bits to be had for storing the variety.

The impact of the aforementioned may be seen inside the price range available to signed and unsigned numbers. While an unsigned 8-bit wide variety could have a number zero to 255, an eight-bit signed wide variety has a variety various from -128 to 127.

Question: Do all statement statements bring about a set reminiscence reservation?

Answer: Except for tips, all announcement statements result in a set memory reservation. Instead of allocating reminiscence for storing statistics, a pointer declaration results in allocating reminiscence for storing the address of the pointer variable.

For guidelines, real reminiscence allocation for the facts happens all through the runtime.

Question: How does an array differ from a stack?

Answer: A stack follows the LIFO method. This way that records manipulation follows a specific collection where the today's information element is the one to be retrieved first.

Unlike a stack, an array doesn’t comply with any unique series for adding or retrieving facts. Adding or retrieving an detail in an array is achieved by regarding the array index.

Question: What do you apprehend by using an AVL tree?

Answer: An AVL tree is a sort of BST (Binary Search Tree), which is continually in a partially-balanced kingdom. The measure of the stability is given by using the distinction of the heights of the subtrees from the foundation node of the AVL tree.

Question: Please explain how does an Array differs from a Linked List?

Answer: Following are the diverse differences between an array and a connected list:

Additional Memory – For each element belonging to a connected listing, extra reminiscence area is needed for storing the pointer. Arrays don't have any such requirement

Cache – In comparison to linked lists, arrays have higher cache locality, that could significantly beautify the performance in diverse eventualities

Insertion and Deletion – It is straightforward to add or delete elements in a related listing. Inserting and deleting factors for an array is relatively pricey

Random Access – Linked lists do no longer permit random get admission to, even as arrays do

Size – While the dimensions of an array is constant, the scale of a connected listing is dynamic

Question: What do you apprehend via Infix, Prefix, and Postfix notations?

Answer:

Infix Notation – Operators are written among the operands. This is the same old manner of writing expressions. For example, A * (B + C) / D

Postfix Notation/Reverse Polish Notation – Operators are written after the operands, hence the name. For example, A B C + * D /

Prefix Notation/Polish Notation – Operators are written before the operands. / * A + B C D is the prefix notation equal of the aforementioned postfix notation instance

Question: Please give an explanation for the Linked List and its diverse kinds.

Answer: In a related listing, each detail is a wonderful item. Like arrays, connected lists are a linear sort of data structure. In addition to facts, every detail of a related list incorporates a connection with the subsequent element. Various kinds of connected lists are:

Singly Linked List – Each node stores the cope with or reference of the subsequent node within the linked listing, leave for the ultimate node that shops NULL

Doubly Linked List – Each node maintains  references. One point to the following node and the alternative points to the previous node

Circular Linked List – In this sort of linked list, all nodes are linked to shape a circle. Hence, there's no NULL on the end. A round connected list can either be a unmarried round related list or a double circular linked listing

Question: How will you put into effect a stack the usage of queue and vice-versa?

Answer: It is viable to put in force a stack the usage of two queues. Further, there are  alternatives; either to make the frenzy operation costly or the pop operation high priced.

A queue can also be implemented with two stacks. Moreover, there are two options; both to make the enQueue operation luxurious or the deQueue operation highly-priced.

Question: Which statistics systems are used for imposing LRU cache?

Answer: By organizing objects in order of use, a Least Recently Used or LRU cache allows brief identity of an object that hasn’t been placed to use for the longest time. Two information structures are used for enforcing an LRU cache:

Queue – Implemented using a doubly-related list. The maximum size of the queue is determined via the overall wide variety of frames available i.E. The cache size. While the most these days used pages can be close to the rear end of the queue, the least recently pages might be near the queue’s the front end

Hashmap – Having page number as the important thing along with the deal with of the corresponding queue node because the cost

Question: Could you supply a short clarification of the diverse strategies for growing algorithms?

Answer: There are three essential methods to developing algorithms:

Divide and Conquer – Involves dividing the whole hassle into some of subproblems after which solving each of them independently

Dynamic Programming – Identical to the divide and overcome method with the exception that every one sub-problems are solved collectively

Greedy Approach – Finds a solution by means of choosing the subsequent pleasant alternative

Question: Please enumerate some examples of greedy and divide and conquer algorithms.

Answer: Some examples of algorithms that comply with greedy approach are:

Dijkstra’s Minimal 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

Following are a few first rate instances of the divide and conquer method:

Binary Search

Closest Pair (or Points)

Merge Sort

Quick Sort

Strassen’s Matrix Multiplication

Question: How does insertion sort range from choice kind?

Answer: Both insertion and selection techniques keep  sub-lists, taken care of and unsorted. Each takes one element from the unsorted sub-list and place it into the looked after sub-list. The difference among the 2 sorting approaches lies inside the treatment of the modern-day element.

Insertion sort takes the present day detail and locations it in the looked after sublist at the suitable vicinity. Selection type, however, searches for the minimal value within the unsorted sub-list and replaces the equal with the prevailing element.

Question: What do you understand through shell sort?

Answer: The shell sort can be understood as a version of the insertion kind. The technique divides the complete list into smaller sub-lists primarily based on some gap variable. Each sub-listing is then looked after the use of insertion kind.

Question: Can you explain tree traversal?

Answer: The manner for visiting all of the nodes of a tree is called tree traversal. It always begins from the basis node and there are three methods of doing it:

In-order Traversal

Pre-order Traversal

Post-order Traversal

Question: Please give an explanation for a spanning tree. What is the maximum range of spanning timber a graph can have?

Answer: A spanning tree is a subset of a graph that has all the vertices but with the minimum possible quantity of edges. Neither a spanning tree may be disconnected and nor does it have cycles.

The maximum number of spanning trees that a graph may have depended on how related the graph is. A whole undirected graph with n range of nodes may have a maximum of nn-1 wide variety of spanning trees.

Question: How does the Kruskal’s Algorithm work?

Answer: Kruskal’s set of rules treats a graph as a forest and every node in it as an individual tree. A tree connects to any other tree simplest if it:

Has the least fee among all the to be had options

Does now not violate the MST homes

Question: What do you understand by using Heap in facts structure?

Answer: A Heap statistics shape is a special balanced binary tree wherein the foundation node secret is in comparison with its youngsters and for that reason arranged. A Heap records structure may be of  types:

Min-Heap – The parent node has a key-cost much less than its youngsters

Max-Heap – The determine node has a key-fee more than its youngsters

Question: Please explain recursion.

Answer: The capacity to permit a feature or module to call itself is known as recursion. Either a characteristic f calls itself without delay or calls another characteristic ‘g’ that during flip calls the function ‘f. The feature f is called the recursive characteristic and it follows the recursive homes:

Base criteria – Where the recursive characteristic stops calling itself

Progressive technique – Where the recursive function attempts to fulfill the base standards in each new release

Question: Can you give an explanation for the Tower of Hanoi problem?

Answer: The Tower of Hanoi is a mathematical puzzle that accommodates of 3 tower (or pegs) and a couple of ring. Each ring is of various length and stacked upon each other such that the larger one is underneath the smaller one.

The purpose of the Tower of Hanoi problem is to transport the tower of the disk from one peg to every other with out breaking the houses.

Question: How do the BFS (Breadth-First Search) and DFS (Depth First Search) algorithms work?

Answer: The BFS set of rules traverses a graph in the breadthwards motion. It makes use of a queue to bear in mind the subsequent vertex for starting a search while a lifeless end occurs in any generation.

A DFS set of rules traverses a graph inside the depthward movement. It uses a stack for remembering the following vertex to begin a seek while coming across a lifeless lead to an new release.

Question: What do you understand by using hashing?

Answer: The technique of converting various key values into more than a few indexes of an array is known as hashing. It is possible to create associative facts garage the use of hash tables wherein information indices may be found by means of imparting the corresponding key values.

Question: Please explain an MST (Minimum Spanning Tree). Also, give an explanation for how does Prim’s set of rules discover a minimal spanning tree.

Answer: An MST or Minimum Spanning Tree is a spanning tree in a weighted graph that has the minimum weight of all the possible spanning trees. Each node is treated as a unmarried tree by Prim’s algorithm while including new nodes to the spanning tree from the available graph.

Question: Can you provide an explanation for the interpolation seek approach?

Answer: The interpolation search method is an enhanced variant of binary search. It works at the probing function of the specified cost.

Question: How will you take a look at whether or not the given Binary Tree is BST or not?

Answer: Simply do inorder traversal of the given binary tree while preserving song of the preceding key price. If the modern key fee is extra, then keep, in any other case return false. The binary tree is BST if the inorder traversal of the binary tree is sorted.

Summary

That sums up the list of the 50 top records shape interview questions. Looking to further your statistics structure knowledge? These DS interview Questions are also beneficial in other programming interviews too. Try those best facts shape tutorials and follow this Udemy path for cracking pinnacle-notch programming companies' interviews. The Coding Interview Bootcamp: Algorithms + Data Structures.




CFG