### Data-Structure Technical Interview Questions Answers

**What is data structure?**

**What are various data structures available?**

**What is an algorithm?**

**Why we need to do algorithm analysis?**

**What are the criteria of algorithm analysis?**

**execution**time and how much

**extra space**is required by the algorithm.

**What is an asymptotic analysis of an algorithm?**

**What are asymptotic notations?**

**What is linear data structure?**

**What are common operations that can be performed on a data structure?**

**Insertion**− adding a data item

**Deletion**− removing a data item

**Traversal**− accessing and/or printing all data items

**Searching**− finding a particular data item

**Sorting**− arranging data items in a pre-defined sequence

**Briefly explain the approaches to developing algorithms.**

**Greedy Approach**− finding a solution by choosing the next best option

**Divide and Conquer**− diving the problem to a minimum possible sub-problem and solving them independently

**Dynamic Programming**− diving the problem to a minimum possible sub-problem and solving them combinedly

**Give some examples greedy algorithms.**

**What are some examples of divide and conquer algorithms?**

**What are some examples of dynamic programming algorithms?**

**What is a linked-list?**

**What is stack?**

**Why do we use stacks?**

**What operations can be performed on stacks?**

**push()**− adds an item to stack

**peek()**− gives value of top item without removing it

**isempty()**− checks if stack is empty

**isfull()**− checks if stack is full

**What is a queue in data-structure?**

**Why do we use queues?**

**What operations can be performed on Queues?**

**enqueue()**− adds an item to rear of the queue

**dequeue()**− removes the item from front of the queue

**peek()**− gives value of front item without removing it

**isempty()**− checks if stack is empty

**isfull()**− checks if stack is full

**What is linear searching?**

^{2}). Data in target arrays/lists need not to be sorted.

**What is binary search?**

**What is bubble sort and how bubble sort works?**

^{2}), it is not suitable for large set of data.

**Tell me something about 'insertion sort'?**

**What is selection sort?**

**How insertion sort and selection sorts are different?**

**What is merge sort and how it works?**

**What is shell sort?**

**gap**variable and then each sub-list is sorted using insertion sort. In best cases, it can perform upto Ο(n log n).

**How quick sort works?**

**What is a graph?**

**How depth first traversal works?**

**How breadth first traversal works?**

**What is a tree?**

**What is a binary tree?**

**What is a binary search tree?**

**What is tree traversal?**

**See the below image of a binary search tree, and traverse it using all available methods −**

**What is an AVL Tree?**

**What is a spanning tree?**

**How many spanning trees can a graph has?**

^{n-1}number of spanning trees, where n is number of nodes.

**How Kruskal's algorithm works?**

**How Prim's algorithm finds spanning tree?**

**What is a minimum spanning tree (MST) ?**

**What is a heap in data structure?**

**What is a recursive function?**

**base criteria**where the function stops calling itself and

**a progressive approach**where the functions try to meet the base criteria in each iteration.

**What ithe a tower of Hanoi?**

**What is the Fibonacci series?**

**What is hashing?**

**What is the interpolation search technique?**

**What is the prefix and post fix notation of (a + b) * (c + d) ?**

**The following formula will produce F _{n} = F_{n-1} + F_{n-2}**

**The following formula is of left_subtree (keys) ≤ node (key) ≤ right_subtree (keys)**

**Match the following −**

- (
**1**) Bubble Sort-----------(**A**) Ο(n) - (
**A**) Ο(n)-------------------(**B**) Ο(n^2) - (
**3**) Selection Sort----------------------(**C**) Ο(n log n)

**node. next → node. next.next; will make.**

`node.next → node.next.next;`

we will not have a n ode.next stored anywhere if not explicitly mentioned.**Differentiate between file and structure storage structure.**

The key difference between both the data structure is the memory area that is being accessed. When dealing with the structure that resides in the main memory of the computer system, this is referred to as storage structure. When dealing with an auxiliary structure, we refer to it as file structures.

**What is merge sort?**

Merge sort, is a divide-and-conquer approach for sorting the data. In a sequence of data, adjacent ones are merged and sorted to create bigger sorted lists. These sorted lists are then merged again to form an even bigger sorted list, which continues until you have one single sorted list.

**Differentiate NULL and VOID**

Null is a value, whereas Void is a data type identifier. A variable that is given a Null value indicates an empty value. The void is used to identify pointers as having no initial size.

**What is the difference between a PUSH and a POP?**

Pushing and popping apply to the way data is stored and retrieved in a stack. A push denotes data being added to it, meaning data is being “pushed” into the stack. On the other hand, a pop denotes data retrieval, and in particular, refers to the topmost data being accessed.

**Which sorting algorithm is considered the fastest?**

There are many types of sorting algorithms: quick sort, bubble sort, balloon sort, radix sort, merge sort, etc. Not one can be considered the fastest because each algorithm is designed for a particular data structure and data set. It would depend on the data set that you would want to sort.

**Differentiate STACK from ARRAY.**

Stack follows a LIFO pattern. It means that data access follows a sequence wherein the last data is stored when the first one is extracted. Arrays, on the other hand, do not follow a particular order and instead can be accessed by referring to the indexed element within the array.

**Differentiate linear from nonlinear data structure.**

The linear data structure is a structure wherein data elements are adjacent to each other. Examples of linear data structures include arrays, linked lists, stacks, and queues. On the other hand, a non-linear data structure is a structure wherein each data element can connect to more than two adjacent data elements. Examples of nonlinear data structures include trees and graphs.

**What are some of the applications of DS?**

**What are the advantages of a Linked list over an array?**

Consider a scenario, where we need to store a large amount of data in an array. But, the memory to store that data is not available contiguously. In this case, we cannot use an array. Hence, we go for a linked list. Since each node is connected using the link, it is not necessary that memory has to be contiguous.

**What are the applications of Graph DS?**

Graphs are used in circuit networks where points of connection are drawn as vertices and component wires become the edges of the graph, in transport networks where stations are drawn as vertices and routes become the edges of the graph, and in maps that draw cities/states/regions as vertices and adjacency relations as edges, in program flow analysis where procedures or modules are treated as vertices and calls to these procedures are drawn as edges of the graph.

**Explain how dynamic memory allocation will help you in managing data?**

A dynamic memory allocation will help you effectively manage your data by allocating structured blocks to have composite structures which can be flexible, i.e. can expand and can contract based on the need. Also, they are capable of storing simple structured data types.

**How does a linear data structure differ from a non-linear data structure?**

**Can you tell which data structures are used for the BFS and DFS of a graph?**

BFS (Breadth First Search) of a graph uses a queue. Although the DFS (Depth First Search) of a graph makes use of a stack, it can also be implemented using recursion that uses a function called stack.

**Please explain the stack and also mention some of its important applications.**

__Some notable applications 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

**Do you know how memory is affected by signed and unsigned numbers?**

**What do you understand by an AVL tree?**

An AVL tree is a type of BST (Binary Search Tree), which is always in a partially-balanced state. The measure of the balance is given by the difference in the heights of the subtrees from the root node of the AVL tree.

**What do you understand by Infix, Prefix, and Postfix notations?**

**Please explain the Linked List and its various types.**

**Singly Linked List**– Each node stores the address or reference of the next node in the linked list, leave for the last node that stores NULL

**Doubly Linked List**– Each node keeps two references. One points to the next node and the other points to the previous node

**Circular Linked List**– In this type of linked list, all nodes are connected to form a circle. Hence, there is no NULL at the end. A circular linked list can either be a singly circular linked list or a double circular linked list

**Could you give a brief explanation of the various approaches for developing algorithms?**

__There are 3 main approaches to developing algorithms:__

**Divide and Conquer**– Involves dividing the entire problem into several subproblems and then solving each of them independently

**Dynamic Programming**– Identical to the divide and conquer approach with the exception that all sub-problems are solved together

**Greedy Approach**– Finds a solution by choosing the next best option

**How does insertion sort differ from selection sort?**

**Please explain a spanning tree. What is the maximum number of spanning trees a graph can have?**

**How does Kruskal’s Algorithm work?**

Kruskal’s algorithm treats a graph as a forest and each node in it as an individual tree. A tree connects to another tree only if it: Has the least cost among all the available options and Does not violate the MST properties

**Can you explain the Tower of Hanoi problem?**

The Tower of Hanoi is a mathematical puzzle that comprises three towers (or pegs) and more than one ring. Each ring is of varying size and stacked upon one another such that the larger one is beneath the smaller one. The goal of the Tower of Hanoi problem is to move the tower of the disk from one peg to another without breaking the properties.

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