Top 50+ Data Structure interview questions

1. What is a Data Structure?

Ans. A data structure is a way of organizing and storing data in a computer’s memory that one can effectively process data to be searched, traversed, or modified. By using data structure complex problems can be solved effectively. One can use linear data structure(Array, Linked List, queue, stack), or non-linear data structure(Tree, Graph) for Logical or mathematical computation.

For Example Student entities have many attributes just like student_id, student_name, roll_no  that will be stored in the database as information of student and fetched, modified, and searched along with specific details.

2. What are the resources of algorithm analysis?

Ans. An algorithm can be analysed using two resources.

1. Time
2. Space

Both are the criteria used to analyse the algorithm.

The time is measured by the no. of processes and space is measured by the CPU memory needed by the algorithm.

3. What is the classification of data structure?

Ans. The data structure can be classified in two ways.

1. Primitive data structure
2. Non-primitive data structure

Non-primitive data structure again can be classified as a linear data structure and non –linear data structure.

4. What do you mean by linear data structure?

A sequence of elements is called a linear data structure. For example Arrays, Linked List, Queue, Stacks.

5. What do you mean by non-linear data structure?

When multiple elements are organized into a hierarchical relationship then that structure of data is called a non-linear data structure. For example Tree, Graph

6. Write an algorithm to swap two variables?

tep1:  Read a=10, b=20, t

Step2: t=a,a=b,b=t

Step 3: print a, b;

Step4: stop

7. What is the difference between the algorithm and flowchart?

An algorithm is a step-by-step representation of a given problem or a program. A flowchart is a graphical representation of the sequence of operations or a program.

8. What do you mean by pseudocode?

Pseudocode is an informal way such as everyday English that helps the programmer to develop algorithms.

9. What do you mean by the complexity of the algorithms?

he analysis and complexity of an algorithm by which the algorithm is best for a problem are determined by the complexity of an algorithm. Problem is determined as searching and algorithm are defined by the linear search or a binary search.

10. What is the complexity of an algorithm?

To analyse an algorithm we can use two criteria.

1. Time Complexity:

Time complexity is the amount of time used by the processor(CPU) to run the process for execution.

2. Space Complexity:

The space complexity of an algorithm is the specific amount of memory for program execution.

For example:

M=f(n)

n: is the no. of input

M: running time and space requirement of an algorithm to process data.

11. On what basis time complexity would be analysed?

Number of array elements accessed, number of comparisons through a critical loop, and no. of operations to be performed.

12. What is an array?

Ans. A list of similar data elements at a finite number(n) is called an array. An array is a collection of a variable of the same type the elements of the array are referenced by an index.

Length of an array=UB-LB+1

UB: Upper Bound(Largest index)

LB: Lower Bound (Smallest Index)

Array is of two types:

1. Single Dimensional array:

Syntax:   int Array[10];

2. Multi Dimensional array:

Syntax: int array[10][10];

 (two dimensional array)

int array [10][10][10];

(multi dimensional array)

 LB                                                              UB

13. What is the computational complexity of linear search?

The computational complexity of the linear search is the maximum number of comparisons you need to search the array. Linear search is also called sequential search.

For Example: if an array of 100 elements then the maximum number of comparison required is n-1, 99 comparison may be required.

14. What is Binary search?

Ans. The binary search algorithm can be used with a sorted array only. After each comparison being searched in the array eliminates one-half of the elements. If the search key is less than the middle element of the array, the first half of the array is searched, If it’s not, in the specified subarray the algorithm is repeated one-quarter of the original array.

SKEY<A[MID] then

Set  END=MID-1

Set  START=MID+1

MID=START+END/2

If SKEY=A[MID]

Set LOC=MID

Else

LOC=-1

return  LOC

EXI

15. How to read array input from user?

Ans.

int   A[10][10];
int i,j;
for(i=0;i<10;i++)
{
for(j=1;j<=10;j++)
{
printf(“enter array elements”);
scanf(“%d” , &A[i][j]);
}

}

16. What do you mean by sorting?

Ans.

Sorting is the process of arranging data items in an ascending or descending order. There are different types of algorithms to sort an element or an array-like: merge sort, bubble sort, selection sort, etc. 

17. What is a Linked list?

Ans.

A linked list is a linear data structure. It is a linear collection of data elements called a node pointing to the next node. Node is divided into two parts the first part contains the information of the elements and the second part contains the address of the next node in the list.

The Head is a special pointer variable that contains the address of the first node of the list if there is no node available in the list then, the Head contains a NULL value that means it’s empty.

The next pointer of the last node is the NULL pointer signal at the end of the list.

Linked lists are dynamic so the length of the list can be increased or decrease if necessary.

18. What is a doubly-linked list?

Ans. In the doubly Linked list, all nodes are linked together by multiple links which help in accessing both the next node and the previous node. A  doubly Linked list helps to traverse the list in the towards the direction and backward direction.

19. What is the difference between a singly linked list and an array?

Ans.

20. What do you mean by a circular doubly linked list?

Ans.

A circular doubly linked list has both the successor pointer(next node) and predecessor pointer(previous node) in a circular manner.

21. Write a traversing algorithm for the linked list?

Ans.

Step1: PTR=HEAD

Step2: repeat Step 3 and step 4 until PTR!=NULL

Step3: PTR->INFO

Step4: PTR=PTR->NEXT

END of Step2

Step 5: stop

22. What do you mean by memory allocation?

Ans.

Memory allocation is of two types:

1. Static memory allocation: it is also called compile-time allocation using arrays
2. Dynamic memory allocation: it is also called run time allocation using pointers.

23. What do you mean by new and delete operator?

Ans: New operator:

Dynamic memory is allocated using the new operator.

Syntax: 

ptr=new int;

ptr=new int [10];

Delete operator:

Once the memory is no longer needed it can be release for other requests of dynamic memory this is done by the delete operator.

Syntax:

delete ptr;

delete [] ptr;

24. What is Stack in Data Structure ?

Ans. A stack is a list of elements in which an element could be added or deleted only at one end, called the top of the stack. Stack operations are performed on the concept of LIFO(Last in First out).

Two operations associated with the stack:

1. Push(): is the term used to insert an element into the stack.
2. Pop(): is the term used to delete an element from the stack.

Two ways to represent stack into the memory is:

1. Array(static)
2. Linked List (Dynamic)

If  top=-1 or NULL represents that stack is empty

25. Write an algorithm for push operation of stack data structure?

Ans.

PUSH(STACK,TOP,STACKSIZE,ITEM)

Step1: if TOP=STACKSIZE-1 then

Step2: TOP=TOP+1

Step3: STACK[TOP]=ITEM

Step4: return

26. Write an algorithm for pop operation?

Ans.

POP(STACK,TOP,ITEM)

Step1: if top=-1 then

Print: UNDERFLOW/stack is empty and  return

Step2: set ITEM=STACK[TOP]

Step3: TOP=TOP-1

Step4:return

27. What is a Queue in Data Structure ?

Ans.

The queue is a linear data structure. queue permits insertion of an element at one end and deletion of an element at another end. The end at which insertion can take place is called the rear and the end at which the deletion of an element takes place is called the front.

A queue is worked on the principle FIFO(First in First out).

Enqueue(insertion) and Dequeue(deletion) are two primary operations performed on the queue data structure.

Array(static) and Linked List(dynamic) are two ways to represents a queue in the memory.

“Front” and “Rear” are two pointer variables. Front=NULL indicates the queue is empty.

NOTE: whenever an element is deleted from the queue, the value of Front increased by 1.

Fro nt=Front+1

Whenever an element is added to the queue, the value of Rear is increased by 1

Rear =Rear+1

28. Write an algorithm for insertion in a queue?

Ans.

Step1: if REAR=(MAXSIZE-1) then

Print: queue is overflow and return

Step2: READ NUM (Inserted into the queue)

Step3: REAR=REAR+1

Step4: set QUEUE[REAR]=NUM

Step5: If FRONT=-1 then

Set FRONT=0

Step6: stop

29. Write an algorithm for deletion in a queue?

Ans.

Step1: if FRONT=-1 then

Print:” queue is underflow “and return

Step2: set num:=QUEUE[FRONT]

STEP3: print: “deleted item is: num”

Step4: set FRONT=FRONT+1

Step5: if Front>REAR then

Set FRONT:=REAR=-1

Step6:stop

30. What do you mean by Dequeue?

Ans. A double-ended queue is a linear list in which elements can be added or removed at either one end but not in the middle.

31. Write an algorithm for bubble sort?

Ans.

Let a[5] is an array

Step1: read 5 elements of an array

Step2: print an array A

Step3: Repeat step3 to 4 i=0 to 3

Step4:repeat step4 for j=0to 4-i

If A[j]>A[j+1]

Set TEMP=A[j+1]

Set A[j+1]=A[j]

Set A[j]=TEMP

END of if

END of step4 

END of step 3

Step5:print sorted array A

Step6: exit

32. Write down the complexity of various sorting algorithms?

Ans.

33. What do you mean by hashing?

Ans. Hashing is a searching technique also called hash addressing that is used to compute the location of the desired record to retrieve the desired record in  single access.

34. What do you mean by the hash table?

Ans. The Hash table is divided into several buckets and each bucket is then capable of storing several records in a data structure where we store a key-value after applying the hash function.

35. What do you mean by hash function?

Ans. A hash function is defined as a function that takes “key “ as input and transforms it into the hash index.

H: K->M

H is a hash function

K is a set of keys

M is a set of memory addresses.

36. What do you mean by trees?

 Ans. tree is a non-linear data structure. A tree is used to represent the hierarchical (parent-child) relationship existing between data items. Items are arranged in a sorted sequence. For the example File system and DOM Structure.

37. What do you mean by a binary tree?

 Ans. binary tree is a special type of tree in which every node can have at least a maximum of 2 children.

A binary tree data structure can be represented using two methods:

1. Array representation
2. Linked List representation
3. The maximum number of nodes in a binary tree of height h is  2h-1.

There are three types of binary tree traversals:

1. In order(left-root-right): The left node visited first, then the root node is visited and later we go for visiting the right child node.
2. Pre order(root-left-right): The root node is visited first then the left child and later its right child.
3. Post order (left-right-root): The left child is visited first, then its right child, and then its root node.

38. What do you mean by binary search tree?

Ans. BST is a type of binary tree in which for each node, the value of all the nodes in the left subtree is lesser or equal and the value of all the nodes in the right subtree is greater. Time complexity to find an element in BST is o(log₂n).

39. Explain traversing of a binary tree with example expression is :(p+q)*(4-3)

Ans. Inorder:      p+q*4-3

Preorder:   *+pq-43

Postorder:  pq+43-*

40. What do you mean by AVL Tree?

Ans. An AVL tree is a self-balancing binary search tree if the difference between the height of left and right child of every node in the tree is either 0, -1,+1 a binary tree is called balanced.

41. What do you mean by the graph?

Ans. A graph is a non-linear data structure. A graph is a collection of nodes(also called vertices) connected by edges(E) each edge connects two nodes.

G=(V, E) G is a graph that is an ordered pair of Vand E.

Graphs  are of two types:

1. Directed graph(unidirectional):Edges have direction.
2. Undirected graph(Bidirectional): Edges have no-direction. 

42. What do you mean by a complete graph?

Ans. A complete graph that has a maximum number of edges. For a directed graph with n vertices the maximum number of edges =n(n-1). For an Undirected graph with n vertices the maximum number of edges=n(n-1)/2.

43. What do you mean by graph traversal techniques?

Ans. Graph traversal is used for searching a vertex in a graph and also used to measure the order of vertices to visit in search.

There are two graph traversal algorithms:

1. Breadth-first search: BFS is a graph search algorithm that begins with the root node and explores all the child nodes until it finds the specified nodes.

The time complexity of BFS is=o(|E|+|V|)

2. Depth-first search: DFS expanding the sorting node and then going deeper until the element or node is not found.

The time complexity of DFS is=o(|E|+|V|

44. Define recursion?

Ans. Recursion is a function that is partially defined by itself. recursion makes code smaller. 

45. Write down the vertices & edges in this graph?

Ans. V={A,B,C,D,E}

E={AB,BC,CE,ED,AD,BD}

46. What do you mean by linear search

Ans. Linear search is mostly used to search an unordered list of elements (where data elements are not sorted).

47. What do you mean by AVL rotation?

Ans. To make itself balanced an AVL tree may perform four kinds of rotations.

1. Left rotation
2. Right rotation
3. Left-right rotation
4. Right-left rotation

48. Which data structure is used to perform recursion?

Ans. STACK because of the concept of LIFO (Last in First out)

49. What do you mean by heap?

Ans. A balanced binary tree has a special case called heap where the root-node key is compared with its children and arranged accordingly.

If p has child node r then

Key(p)>=key(r)

Heap can be of two types:

1. Min-heap: where the value of the root node is less than or equal to either of its child node.
2. Max-heap: where the value of the root node is greater than or equal to either of its child node.

50. What do you mean by insertion sorting?

Ans. Insertion sorting is implemented by inserting a particular element at the appropriate position.

51. What do you mean by quick sort?

Ans. The basic strategy of quicksort is divide and conquer. It is faster and easier to sort two small arrays than one large array. Quicksort can sort a List of data elements faster than any of the common sorting algorithms.

52. What do you mean by external sorting?

Ans. External sorting is applied to the huge amount of data that can not be in the memory all at a time.

53. What do you mean by internal sorting?

Ans. When all the data that is to be sorted can be accommodated at a time in memory then internal sort methods such as bubble sort, merge sort, heap sort, etc are used.

54. What is the primitive data structure?

Ans. Integer, Boolean, Character, Float are the primitive data structure.

55. What is the linear data structure?

Ans. Arrays, Linked List, Queues, Stacks

56. What is the non-linear data structure?

Ans. Tree, Graph.

57. What do you mean by traversing?

Ans. Traversing means accessing each node exactly once so that certain items in the record may be processed.

58. What are the data structure operations?

Ans.

1. Traversing
2. Searching
3. Inserting
4. Deleting

59. What do you mean by merging?

Ans. Combining the two sorted records of two different files into a single file is called merging.