Data Structure Interview Questions

What is Data Structure? Explain.

The data structure is a way that specifies how to organize and manipulate the data. It also defines the relationship between them. Some examples of Data Structures are arrays, Linked List, Stack, Queue, etc. Data Structures are the central part of many computer science algorithms as they enable the programmers to handle the data in an efficient way

What is the difference between a File Structure and a Data Structure?

What is a linked list?

A linked list is a data structure that consists of individual entities called nodes. These nodes have the capability to connect to other nodes and create a chain in the process. This continuous chain structure forms a linked list, as the name suggests.

Where are Data Structures primarily used?

Data structures are very much needed in almost all of the fields that you can think of. Algorithms are the primary requirement in every data handling situation. Following are some of the scenarios where data structures are widely used:

• Numerical computation
• Operating system design
• Artificial Intelligence
• Compiler design
• Database handling
• Graphical processing
• Lexical analysis
• Statistics

What are the types of searching used in Data Structures?

The two primary methods of searching are linear search and binary search.
The linear search involves iterating over a data unit in order to perform the required operation.
Binary search is more efficient in a way that it has the ability to split the data unit into chunks and then perform a search operation.

How does binary search work?

Binary search is used when there is primarily a criterion of efficiency. It involves working on the already ordered data, sorted in ascending or descending order. To begin with, the middle element of the array is found, and the search begins from there. The array is searched in two parts based on the search value being higher or lower than the middle element. It is key to know the order of the arrangement to help search the value accordingly.

How are individual elements accessed in an array?

Each of the values in an array is given an index position starting from 0 to n-1, where ‘n’ is the number of elements in the array. Individual elements can be accessed by using the index element for operations. Multi-dimensional arrays will have more than one dimension to work with.

What is a queue in Data Structures?

A queue is a widely used data structure that is used to denote the ordered access and manipulation of an element. The operation of this data structure is exactly the same as a literal queue in the real world. Elements are added one after the other and are processed on the front end.

What is a binary tree?

A binary tree, as the name suggests, is a tree data structure with two nodes, which are the nodes on the left and the right sides of the root note. In usage, binary trees are considered to be an extended linked list.

What is the meaning of stack?

A stack is another widely used data structure that provides users with the ability to work with data at one point only. As the name suggests, this can literally correspond to the working of a stack of cards.

What is the working of LIFO?

LIFO stands for the Last in, First out access order. It is directly corresponding to how the data can be worked on and modified. The data entity that is stored or pushed in last is the first one to be worked on at any point in time. If there is a requirement to access the very first element stored, then first you have to retrieve all of the data that came in after that element.

What are multi-dimensional arrays?

Multi-dimensional arrays are arrays that span across more than one dimension. This means that they will have more than one index variable for every point of storage. This is primarily used in cases where data cannot be represented or stored using only one dimension.

Are linked lists Linear or Non-linear Data Structures?

Linked lists are considered to be the best of both worlds here. Based on usage, if it is a storage policy, then it can be considered nonlinear. Whereas, if a person is considering it based on retrieval strategies, then it can be considered linear.
Next up on these Data Structure questions, you need to understand a little bit about a Binary Search Tree.

What is a Binary Search Tree?

A binary search tree is a data structure that stores data in a very efficient manner. It consists of two primary nodes from the root node. The main thing here is that the values of the nodes in the left sub-tree are less in number than the value of the root node, and the values of the nodes on the right of the root node are correspondingly higher than the root. Also, individually both of these left and right sub-trees are their own binary search trees at all points of time.

What is the meaning of FIFO?

FIFO, also known as First in, First out, is a way of representing a data operation on factors such as how data is accessed and in what order. Here, the data that is first put into the list will be the first entity to exit from the ordered data structure.

What is the difference between void and null in Data Structures?

Void is a data type identifier in data structures, while null is considered to be a value with no physical presence. When the void is used, it indicates that there is no size while initializing the data structure.

What is dynamic memory management?

Dynamic memory management is a technique in which storage units are allocated based on the requirements continuously. Using dynamic memory allocations, individual data structures can be either stored separately or combined to form entities called composites. These composites can be worked on when required

What are push and pop operations in Data Structures?

Both push and pop operations denote how data can be stored and used when required in a stack. The push operation denotes that users are adding data into the structure, and the pop operation denotes that the data is being pulled or removed from the structure. Usually, the top element is considered when performing push and pop operations.

How is a variable stored in memory when using Data Structures?

A variable is stored based on the amount of memory that is needed. First, the required quantity of memory is assigned, and later, it is stored based on the data structure being used. Using concepts such as dynamic allocation ensures high efficiency and that the storage units can be supplied based on the requirements in real-time.
Next up on this compilation of top Data Structures interview questions, we can check out the questions categorized as intermediate.

What is merge sort?

Merge sort is a method of sorting, which is based on the divide and conquer technique. Here, data entities adjacent to each other are first merged and sorted in every iteration to create sorted lists. These smaller sorted lists are combined at the end to form a completely sorted list.

Why should a heap be used over a stack?

The heap data structure is more efficient to work with when compared to the stack in a way that memory allocation in a head is dynamic and can be allocated and removed as per the requirement. The memory structure and access time of a stack are comparatively slow.

What is the meaning of Data Abstraction?

Data abstraction is one of the widely used tools in data structures. The goal is to break down complex entities into smaller problems and solve these by using the concepts of data structures. This provides users with the advantage of being focused on the operations and not worried about how the data is stored or represented in the memory.

What is the meaning of a post-fix expression in Data Structures?

Post-fix expressions are used in a scenario where every operator is preceded by its operands. Using this ensures eliminates the need for parentheses or sub-expressions when it comes to the concept of operator precedence.

What is the working of a selection sort?

A selection sort is a widely used sorting algorithm in the world of Data Structures. The working is simple where the smallest entity is first found out and the index of that is set to zero, thereby permanently sorting this in the first step. The remaining steps involve iterating through other elements and adding the next index correspondingly. This is done until all of the elements are sorted.

What are signed numbers in Data Structures?

Signed numbers are the units that have a data bit at the beginning of the number that denotes if the number is positive or negative. Signed numbers have a range of -128 to +127.

What are the minimum nodes binary trees can have?

Binary trees can have zero nodes or a minimum of 1 or 2 as well. It can be zero in a case where all of the nodes have a NULL value.

What Data Structures make use of pointers?

Pointers are used in a variety of data structures. They are majorly used in the following data structures:

• Binary trees
• Linked lists
• Queues
• Stacks

What is the use of dynamic Data Structures?

Dynamic data structures provide users with a lot of flexibility in terms of the provision of data storage and manipulation techniques, which can change during the operation of the algorithm or the execution of the program.

What is a priority queue?

A priority queue is an abstract data type that resembles a normal queue but has a priority assigned to elements. Elements with higher priority are processed before the elements with a lower priority. A minimum of two queues are required in this case, one for the data and the other to store the priority.

Pointers allocate memory for data storage. True or False?

False, pointer operations such as declaration will not allocate any memory for the storage of data. But, memory is allocated for the variable that the pointer is pointing to. Memory processing begins only when the program begins its execution.

What is the meaning of deque?

A deque is a queue that is double-ended. This means that elements can be added or removed from any one of the two ends. It can be used both as a regular queue and as a stack. It performs better than both linked lists and stacks in general.

State the difference between Linear and Non-linear Data Structures.

What is the meaning of an AVL tree?

An AVL tree is a type of binary search tree where the tree is only slightly balanced. Balance is the unit of comparison between the heights of the subtrees from the main (root) node

How does Huffman’s algorithm work?

Huffman’s algorithm uses a table, containing the frequency of the occurrence of every data entity on the list. This is used for creating extended binary trees, which are known to have minimum weights for the path lengths. This is considering each of the corresponding weights.

What are recursive algorithms?

Recursive algorithms are algorithms that solve a problem by breaking it down into simpler sub-problems and then solving them iteratively. The output of one recursion operation is usually the direct input for the next iteration operation, and this process goes on.

How does bubble sort work?

Bubble sort is one of the most used sorting techniques out there. It is applied to arrays where elements adjacent to each other are compared and values are exchanged based on the order of arrangement. It’s called bubble sort because of the concept of exchanging elements like a bubble floating to the top of the water and larger entities sinking down to the bottom end.

Which is the fastest sorting algorithm available?

Among the many types of algorithms such as bubble sort, quick sort, merge sort, and more, it is not right to put one method on the podium for performance as this greatly varies based on data, the reaction after the algorithm processes the data, and how it’s stored. The concept of time complexity is considered here.

What is the postfix form of: (X + Y) * ( Z – C)

The postfix form of the given expression is XY+ZC-*

Where are Tree Data Structures used?

Tree data structures are used in a variety of applications. Following are some of them:

• Arithmetic expression handling
• Symbol table creation
• Lexical analysis
• Hierarchical data modeling

What are the Data Structures that are used in graphs?

To implement graphs, two data structures play a key role. They are:

• Adjacency matrix: Used for sequential data representation
• Adjacency list: Used to represent linked data

What are the Data Structures that are used in DFS and BFS algorithms?

In the depth-first search (DFS), the stack data structure is made use of.
In the case of the breadth-first search (BFS) technique, queues are used

What are the time complexities of linear search and binary search?

Binary search is more effective as it takes lesser comparisons to search for an element in an array. The time complexity for linear search is O(n), while it is O(log n) for binary search.

Where are Multi-linked Data Structures used?

Multi-linked data structures are used in many domains. Following are the two most important use cases of multi-linked data structures:

• Generation of sparse matrices
• Index creation for data entities

What is the method used for inorder traversal in trees?

Inorder traversal works in the following way:

• The tree is traversed through the left subtree.
• The root node is visited after the left visit.
• Then, the right subtree is traversed.

What is the working of post-order traversal in trees?

Postorder traversal works in the following way :

• First, the left subtree is traversed through.
• The right subtree is traversed next.
• The root node is visited after the right subtree visit.

What are the disadvantages of implementing queues using arrays?

There are two main downsides when implementing queues using arrays. They are as follows:

• Array sizing: The queue has to be constantly extended to make way for more elements that get implemented. Always extending the size of the array will not be feasible as there will be a discrepancy in the creation of the correct array size.
• Memory dumps: The memory that is used to store the queue elements cannot be reused to actually store the queue. This is because of the working of queues where insertion happens at the head node only.

How can elements be inserted into the circular queue?

There are two cases in which items can be placed in a circular queue. They are as follows

• When front != 0 and rear = max -1. This makes it possible as the queue will not be full, and new elements can be inserted here.
• When rear != max -1. This ensures that the rear is incremented to the maximum allocation size, and values can be inserted easily into the rear end of the queue.

What is the use of void pointers?

Void pointers are used because of their capability to store any pointer, which is pointing to a wide variety of data. It is used to implement heterogeneous linked lists in many programming languages.

What is the meaning of the stack overflow condition?

Stack overflow is the term given when the stack is full and an element cannot be inserted into the stack anymore.
Stack overflow happens when top = Maxsize – 1

Write the steps involved in the insertion and deletion of an element in the stack.

Push:

• Increment the variable top so that it can refer to the next memory allocation
• Copy the item to the at the array index value equal to the top
• Repeat steps 1 and 2 until the stack overflows

Pop:

• Store the topmost element into the an another variable
• Decrement the value of the top
• Return the topmost element

What is a postfix expression?

An expression in which operators follow the operands is known as a postfix expression. The main benefit of this form is that there is no need to group sub-expressions in parentheses or to consider operator precedence.
The expression “a + b” will be represented as “ab+” in postfix notation.

List the area of applications of Data Structure.

Data structures are applied extensively in the following areas of computer science

• Compiler Design,
• Operating System,
• Database Management System,
• Statistical analysis package,
• Numerical Analysis
• Graphics
• Artificial Intelligence,
• Simulation

List the data structures which are used in RDBMS, Network Data Modal, and Hierarchical Data Model.

• RDBMS uses an Array data structure
• The network data model uses Graph
• The hierarchal data model uses Trees

How to reference all the elements in a one-dimension array?

It can be done by using an indexed loop such that the counter runs from 0 to the array size minus one. In this manner, you can reference all the elements in sequence by using the loop counter as the array subscript.

What is a multidimensional array?

The multidimensional array can be defined as the array of arrays in which, the data is stored in a tabular form consisting of rows and columns. 2D arrays are created to implement a relational database lookalike data structure. It provides ease of holding the bulk of data at once which can be passed to any number of functions wherever required

How are the elements of a 2D array are stored in the memory?

There are two techniques using which, the elements of a 2D array can be stored in the memory.

• Row-Major Order: In row-major ordering, all the rows of the 2D array are stored in the memory contiguously. First, the 1st row of the array is stored in the memory completely, then the 2nd row of the array is stored in the memory completely, and so on till the last row.
• Column-Major Order: In column-major ordering, all the columns of the 2D array are stored in the memory contiguously. first, the 1st column of the array is stored in the memory completely, then the 2nd row of the array is stored in the memory completely, and so on till the last column of the array

Calculate the address of a random element present in a 2D array, given the base address as BA

Row-Major Order: If the array is declared as a[m][n] where m is the number of rows while n is the number of columns, then the address of an element a[i][j] of the array stored in row-major order is calculated as,
Address(a[i][j]) = B. A. + (i * n + j) * size

Column-Major Order: If the array is declared as a[m][n] where m is the number of rows while n is the number of columns, then the address of an element a[i][j] of the array stored in column major order is calculated as
Address(a[i][j]) = ((jm)+i)Size + BA

Define Linked List Data structure.

A linked list is the collection of randomly stored data objects called nodes. In Linked List, each node is linked to its adjacent node through a pointer. A node contains two fields, i.e. Data Field and Link Field.

Are linked lists considered linear or non-linear data structures?

A linked list is considered both linear and non-linear data structure depending on the situation.

• On the basis of data storage, it is considered a non-linear data structure.
• On the basis of the access strategy, it is considered a linear data structure.

What are the advantages of a 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 continuously 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, the 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