Data Structures interview questions

1. What is a data structure?

A data structure is a way to store and organize data in a computer. It has a logical relationship, a storage structure, and a set of operations.

Full lesson: Data structures tutorial

2. Why do programmers learn data structures and algorithms?

Data structures and algorithms control the running speed and the resource use of a program. Good choices solve complex problems with less time and memory.

Full lesson: Dsa intro

3. What is an algorithm?

An algorithm is a clear and finite sequence of steps. It solves a specific problem or completes a task.

Full lesson: Dsa basic algorithm

4. What is a tree structure?

A tree is a non-linear data structure. It has a root node and a one-to-many hierarchy of nodes.

Full lesson: Dsa tree

5. What is a graph?

A graph has nodes and edges. Nodes are points and edges are the links between them.

Full lesson: Dsa graph

6. What is a hash table?

A hash table stores data by a computed key index. It gives close to O(1) time for search, insert, and delete in the average case.

Full lesson: Dsa hash table

7. How does insertion sort work?

Insertion sort takes one element at a time. It inserts each element into the correct place in the sorted part.

Full lesson: Insertion sort

8. How does merge sort work?

Merge sort splits the array into smaller parts. It sorts each part and then merges the ordered parts.

Full lesson: Merge sort

9. What is Shell sort?

Shell sort is an improved insertion sort. It sorts distant elements first and then reduces the gap.

Full lesson: Shell sort

10. How does a max heap add a new element?

The new element goes to the last array position. Then shift up swaps it with its parent until the heap property holds.

Full lesson: Heap shift up

11. How does a max heap remove the top element?

The last element moves to the root. Then shift down swaps it with the larger child until the heap property holds.

Full lesson: Heap shift down

12. What is the heapify step in heap sort?

Heapify builds a heap from an unordered array. It runs in O(n) time and is faster than repeated insert.

Full lesson: Heap sort

13. What is a union-find structure?

Union-find handles disjoint sets with merge and query operations. An array holds the parent of each element, and the root identifies the set.

Full lesson: Union find basic

14. Why does an index heap help with large elements?

An index heap stores indices instead of the elements. It avoids costly swaps of large elements and keeps each position easy to find.

Full lesson: Heap index

15. What common mistake causes a wrong result in union-find?

A common mistake is to skip path compression or rank. Without them, the trees can become tall and slow.

Full lesson: Union find rank

16. What is the main difference between a linear data structure and a non-linear data structure?

A linear data structure arranges elements one after another. A non-linear data structure arranges elements in a hierarchy or network. Trees and graphs are non-linear structures.

Full lesson: Dsa tree

17. What are the two common ways to represent a graph in memory?

An adjacency matrix uses a two-dimensional array. An adjacency list uses an array of lists. The matrix is fast for edge checks. The list saves space for sparse graphs.

Full lesson: Graph theory

18. How does insertion sort build a sorted sequence step by step?

Insertion sort takes one element at a time. It inserts the element into its correct position in the already sorted part. The sorted part grows by one element each step.

Full lesson: Insertion sort

19. What is the time complexity of building a heap with the heapify method?

The heapify method builds a heap in O(n) time. This is faster than inserting elements one by one, which takes O(n log n) time. Heapify works from the bottom of the tree upward.

Full lesson: Heap sort

20. How does a heap store its elements in an array?

A heap stores elements in an array that represents a complete binary tree. For a node at index i, the parent is at index i/2, the left child at 2*i, and the right child at 2*i+1. This mapping allows efficient navigation without pointers.

parent(i) = i/2
left(i) = 2*i
right(i) = 2*i + 1

Full lesson: Heap storage

21. What is the purpose of the shift up operation in a heap?

The shift up operation moves a new element up the heap to restore the heap property. It compares the element with its parent and swaps them if needed. This process continues until the element is in the correct position.

Full lesson: Heap shift up

22. What is the purpose of the shift down operation in a heap?

The shift down operation moves an element down the heap to restore the heap property. It compares the element with its children and swaps with the larger child (for a max heap). This process continues until the element is in the correct position.

Full lesson: Heap shift down

23. How does the quick-find implementation of union-find work?

Quick-find uses an array where each element stores the ID of its set. The find operation returns the ID in O(1) time. The union operation changes all elements of one set to the other set's ID, which takes O(n) time.

int find(int p) { return id[p]; }

Full lesson: Union find quick

24. How does size optimization improve the union-find structure?

Size optimization makes the root of the smaller set point to the root of the larger set. This keeps the tree height low. The find operation becomes faster on average.

Full lesson: Union find size

25. How does rank optimization differ from size optimization in union-find?

Rank optimization uses the height of the tree instead of the number of elements. It points the root of the shorter tree to the root of the taller tree. This gives a more balanced structure in some cases.

Full lesson: Union find rank

26. What is the key difference between two-way quicksort and three-way quicksort?

Two-way quicksort partitions the array into two parts: less than the pivot and greater than the pivot. Three-way quicksort partitions into three parts: less than, equal to, and greater than the pivot. Three-way quicksort is more efficient for arrays with many duplicate elements.

Full lesson: 3way qiuck sort

27. Why does two-way quicksort perform poorly on arrays with many duplicate elements?

Two-way quicksort puts all elements equal to the pivot on one side. This creates very unbalanced partitions. The algorithm can degrade to O(n^2) time.

Full lesson: 2way quick sort

28. What common mistake causes an infinite loop in union-find?

A common mistake is to forget to update the parent pointer of the root. If the root points to itself and the union operation does not change it, the find operation can loop forever. Always ensure that the root of one set points to the root of the other set.

Full lesson: Union find basic

29. What common mistake causes a heap to violate the heap property after an insertion?

A common mistake is to stop the shift up operation too early. The shift up must continue until the new element is smaller than its parent (for a max heap) or reaches the root. Otherwise, the heap property is broken.

Full lesson: Heap shift up

30. What common mistake causes a wrong result in graph traversal?

A common mistake is to forget to mark visited nodes. Without marking, the traversal can visit the same node many times and loop forever. Always mark a node as visited when you first see it.

Full lesson: Dsa graph

31. What is the main purpose of the heap data structure?

A heap keeps the largest or smallest element at the top. It supports fast insertion and removal of that top element.

Full lesson: Heap storage

32. How does the quick-find union-find operation merge two sets?

Quick-find changes all elements of one set to the ID of the other set. This merge takes O(n) time.

public void unionElements(int p, int q) {
  int pID = find(p);
  int qID = find(q);
  if (pID == qID) return;
  for (int i = 0; i < count; i++)
    if (id[i] == pID) id[i] = qID;
}

Full lesson: Union find quick

33. What is the time complexity of the find operation in quick-find union-find?

The find operation returns the ID array value directly. It takes O(1) time.

private int find(int p) {
  assert p >= 0 && p < count;
  return id[p];
}

Full lesson: Union find quick

34. How does size optimization reduce the height of a union-find tree?

Size optimization points the root of the smaller set to the root of the larger set. This rule keeps the tree height low.

Full lesson: Union find size

35. What is the difference between rank optimization and size optimization in union-find?

Rank optimization uses the tree height to decide the merge direction. Size optimization uses the number of elements.

Full lesson: Union find rank

36. How does the shift-up operation restore the heap property after an insertion?

Shift-up compares the new element with its parent. It swaps them when the heap order is wrong and repeats up the tree.

while (k > 0 && data[parent(k)] < data[k]) {
  swap(parent(k), k);
  k = parent(k);
}

Full lesson: Heap shift up

37. How does the shift-down operation restore the heap property after removing the top element?

Shift-down compares the element with its children. It swaps with the larger child and repeats down the tree.

while (leftChild(k) < count) {
  int j = leftChild(k);
  if (j + 1 < count && data[j + 1] > data[j]) j++;
  if (data[k] >= data[j]) break;
  swap(k, j);
  k = j;
}

Full lesson: Heap shift down

38. What is the time complexity of the heapify method for building a heap?

The heapify method builds a heap in O(n) time. It starts from the last parent node and shifts down each node.

Full lesson: Heap sort

39. How does the two-way quicksort partition an array?

Two-way quicksort uses two pointers that move toward each other. It swaps elements to keep smaller values on the left and larger values on the right.

Full lesson: 2way quick sort