Advanced Data Structures and Algorithms Interview Prep

Posted on Sep 29, 2026 in Computer Engineering

What is a Red-Black Tree?

Answer:

A Red-Black Tree is a self-balancing Binary Search Tree (BST) in which every node contains an additional color bit: Red or Black.

It maintains balance using recoloring and rotations, ensuring that the height remains O(log n).

Properties of a Red-Black Tree

Answer:

A Red-Black Tree satisfies the following properties:

1. Every node is either Red or Black.
2. The root is always Black.
3. Every NIL/NULL leaf is Black.
4. A Red node cannot have a Red child (no two consecutive Red nodes).
5. Every path from a node to its descendant NIL leaves has the same black height.

What is Black Height?

Answer:

The black height of a node is the number of black nodes on any path from that node to a descendant NIL leaf, generally excluding the node itself depending on convention.

All paths from a node to its NIL descendants must have the same black height in a Red-Black Tree.

What is a Binomial Heap?

Answer:

A Binomial Heap is a collection of binomial trees satisfying the min-heap or max-heap property.

Important properties:

• At most one binomial tree of each degree exists.
• A binomial tree B_k contains 2^k nodes.

What is a Binomial Tree?

Answer:

A Binomial Tree B_k is defined recursively:

• B₀ contains one node.
• B_k is formed by linking two B_k-1 trees, making the root of one tree a child of the root of the other.

Therefore, |B_k| = 2^k and its root has degree k.

What is a Fibonacci Heap?

Answer:

A Fibonacci Heap is a collection of heap-ordered trees that maintains a set of minimum-rooted trees.

It uses lazy consolidation, making operations such as insertion and decrease-key highly efficient.

Amortized complexities:

• Insert: O(1)
• Decrease-Key: O(1)
• Extract-Min: O(log n)

What is a Skip List?

Answer:

A Skip List is a probabilistic data structure consisting of multiple sorted linked-list levels.

Higher levels contain a subset of nodes from lower levels, allowing searching to skip many elements. The expected search complexity is O(log n).

What is a B-Tree?

Answer:

A B-Tree is a height-balanced multiway search tree in which each node can contain multiple keys and children. All leaf nodes occur at the same level. It is widely used in database and file-system indexing.

What is a Trie?

Answer:

A Trie is a tree-based data structure used for storing strings. Each edge generally represents a character, and a path from the root represents a string or prefix. Searching a string of length L takes O(L).

What is Dijkstra’s Algorithm?

Answer:

Dijkstra’s algorithm finds the single-source shortest path from a source vertex to all other vertices in a weighted graph with non-negative edge weights. Using a binary heap priority queue, the complexity is O((V + E) log V).

What is Kruskal’s Algorithm?

Answer:

Kruskal’s algorithm is a Greedy algorithm used to find the Minimum Spanning Tree (MST) of a weighted undirected graph. It:

1. Sorts edges by increasing weight.
2. Selects the smallest edge that does not form a cycle.
3. Uses Disjoint Set/Union-Find to detect cycles.

What is Fractional Knapsack?

Answer:

In the Fractional Knapsack problem, items can be divided into fractions. Items are selected according to the Profit/Weight ratio in decreasing order. The greedy method provides an optimal solution.

What is Merge Sort?

Answer:

Merge Sort is a Divide and Conquer sorting algorithm. It:

1. Divides the array into two halves.
2. Recursively sorts both halves.
3. Merges the sorted halves.

Time complexity is O(n log n) in best, average, and worst cases.

Worst-Case Complexity of Quick Sort

Answer:

The worst-case complexity of Quick Sort is O(n²). It occurs when the pivot repeatedly produces highly unbalanced partitions, such as choosing the smallest or largest element as the pivot every time.

Red-Black Tree Insertion

Answer

A Red-Black Tree is a self-balancing BST. During insertion, the new node is initially inserted as Red. If Red-Black properties are violated, we use recoloring and rotations.

Insertion Cases

Case 1: Parent is Black

If the parent of the inserted node is Black, no violation occurs. Action: No correction required.

Case 2: Parent and Uncle are Red

If both parent and uncle are Red:

• Change parent to Black
• Change uncle to Black
• Change grandparent to Red

Then continue checking upward. This is called recoloring.

Case 3: Uncle is Black

Rotations are required. There are four structural possibilities:

LL Case

      G
     /
    P
   /
  X

Perform Right Rotation(G).

RR Case

G
 \
  P
   \
    X

Perform Left Rotation(G).

LR Case

    G
   /
  P
   \
    X

Perform: 1. Left Rotation(P), 2. Right Rotation(G).

RL Case

G
 \
  P
 /
X

Perform: 1. Right Rotation(P), 2. Left Rotation(G).

Complexity

Search, insertion, and deletion take O(log n) because the Red-Black Tree remains approximately balanced.

Properties of a Binomial Heap

Answer

A Binomial Heap is a collection of binomial trees satisfying the heap-order property.

Key Properties

1. Every tree follows the min-heap or max-heap property.
2. There is at most one binomial tree of each degree.
3. A binomial tree B_k contains 2^k nodes.
4. The height of B_k is k.
5. The root of B_k has degree k.
6. A Binomial Heap containing n nodes has at most ⌊log₂ n⌋ + 1 trees.

Example

For 13 nodes: 13 = 8 + 4 + 1. Therefore, the heap contains: B₃ + B₂ + B₀.

Union of Two Binomial Heaps

Answer

Union combines two Binomial Heaps into one valid Binomial Heap.

Steps

1. Merge the root lists of both heaps according to increasing degree.
2. Scan the merged root list.
3. If two trees have the same degree, link them. For a min-Binomial Heap, the root with the smaller key becomes the parent.

Algorithm

BINOMIAL-HEAP-UNION(H1, H2)
1. H ← merge root lists of H1 and H2
2. Set previous ← NIL
3. Set current ← first root
4. While current ≠ NIL:
      if degree(current) ≠ degree(next):
          move forward
      else:
          if key(current) ≤ key(next):
              link next under current
          else:
              link current under next
5. Return H

Complexity

Root lists contain O(log n) trees; therefore, the complexity is O(log n).

Fibonacci Heap Explained

Answer

A Fibonacci Heap is a collection of heap-ordered trees. Unlike a Binomial Heap, it does not immediately consolidate trees after every insertion. This lazy strategy improves amortized performance.

Important Properties

• Collection of heap-ordered trees.
• Maintains a pointer to the minimum node.
• Trees are not necessarily binomial immediately.
• Supports cascading cuts and uses lazy consolidation.

Amortized Complexities

Application

Fibonacci Heaps are useful in algorithms such as Dijkstra’s and Prim’s because of the efficient Decrease-Key operation.

Binomial Heap vs. Fibonacci Heap

Answer

Skip List Searching

Answer

A Skip List is a probabilistic data structure consisting of multiple levels of sorted linked lists.

Algorithm

SEARCH(x)
current = head
while current != NIL:
    while next(current) != NIL and key(next(current)) <= x:
        current = next(current)
    if key(current) == x:
        return FOUND
    move down
return NOT FOUND

Complexity

Expected: O(log n). Worst case: O(n).

Skip List Numerical Example

Question

Promotion probability: p = 1/2. Base level contains 100 nodes. Find the expected number of nodes at the next level.

Answer

Expected nodes: n × p = 100 × 1/2 = 50. Therefore, the expected number of nodes at the next level is 50.

B-Tree Properties and Applications

Answer

A B-Tree is a balanced multiway search tree used for efficient searching and indexing.

Properties

For minimum degree t:

1. Every node contains at most 2t – 1 keys.
2. Every internal node has at most 2t children.
3. Except the root, every node has at least t – 1 keys.
4. All leaves are at the same level.
5. Keys within a node are sorted.
6. Searching takes O(log n).

Applications

• Database indexing
• File systems
• Disk-based storage

Trie Insertion and Searching

Answer

A Trie stores strings character by character. For a word of length L, complexity is O(L).

Insertion

1. Start at the root.
2. Check whether the character edge exists.
3. If not, create a new node.
4. Move to the next node.
5. Mark the final node as the end of the word.

Searching

Start from the root and follow the characters. If any character is missing, the word does not exist. If all are found and the final node is marked as an end, the word exists.

Binary Search via Divide and Conquer

Answer

Binary Search is a Divide and Conquer technique used on a sorted array. It repeatedly divides the search space into two halves.

Algorithm

1. Set low = 0 and high = n – 1.
2. Find middle element: mid = (low + high) / 2.
3. If key = A[mid], return the position.
4. If key is smaller, search the left half. Otherwise, search the right half.

Time Complexity

• Best Case: O(1)
• Average Case: O(log n)
• Worst Case: O(log n)

Max and Min via Divide and Conquer

Answer

This algorithm finds the maximum and minimum elements by dividing the array into smaller subarrays and combining results.

Steps

1. Divide the array into two halves.
2. Recursively find max and min of the left half.
3. Recursively find max and min of the right half.
4. Compare the two maximums and two minimums to return the final values.

Dijkstra’s Algorithm Details

Answer

Dijkstra’s algorithm finds the shortest path from a single source vertex to every other vertex in a weighted graph with non-negative weights.

Algorithm

DIJKSTRA(G, source)
1. Set distance[source] = 0
2. Set distance of every other vertex = ∞
3. Put all vertices into priority queue
4. Select vertex u with minimum distance
5. For every adjacent vertex v:
       if dist[u] + weight(u, v) < dist[v]:
           dist[v] = dist[u] + weight(u, v)
6. Repeat until all vertices are processed

The relaxation operation is: d[v] = min(d[v], d[u] + w(u, v)).

Dijkstra Numerical Walkthrough

Suppose source = A. Initial distances: A=0, B=∞, C=∞, D=∞.

1. From A: B=4, C=2. Choose C (minimum).
2. From C: B = min(4, 2+8) = 4.
3. Process B: D = min(∞, 4+5) = 9.

Final distances: A=0, B=4, C=2, D=9.

Kruskal’s Algorithm and Example

Answer

Kruskal’s algorithm finds an MST using a greedy approach by sorting edges.

Steps

1. Sort all edges in increasing order of weight.
2. Initially consider every vertex as a separate set.
3. Select the smallest edge. If it does not form a cycle, include it.
4. Perform Union of the two sets.
5. Continue until V – 1 edges are selected.

Complexity: O(E log E).

Fractional Knapsack Numerical

Answer

Greedy criterion: Ratio = Profit / Weight. Arrange items in decreasing order of ratio.

Example: Capacity W=50. Items: (P:60, W:10), (P:100, W:20), (P:120, W:30). Ratios: 6, 5, 4.

1. Take Item 1: Profit 60, Remaining W=40.
2. Take Item 2: Profit 60+100=160, Remaining W=20.
3. Take 2/3 of Item 3: Profit 160 + (120 * 2/3) = 240.

Max Profit: 240.

Merge Sort Steps and Complexity

Answer

1. Divide: Split array into two halves.
2. Conquer: Recursively sort both halves.
3. Combine: Merge the sorted halves.

Recurrence: T(n) = 2T(n/2) + O(n). Complexity: O(n log n).

Quick Sort and Partitioning

Answer

1. Select a pivot.
2. Partition the array: smaller elements to the left, larger to the right.
3. Recursively sort both partitions.

Complexity: Best/Average O(n log n), Worst O(n²).

Activity Selection Problem

Answer

Select the maximum number of mutually compatible activities. Greedy strategy: Always select the activity that finishes earliest.

Complexity: O(n log n) if unsorted, O(n) if sorted.

Convex Hull via Divide and Conquer

Answer

The Convex Hull is the smallest convex polygon containing all points.

Steps

1. Sort points by x-coordinate.
2. Divide points into two equal sets.
3. Recursively find the convex hull of each half.
4. Find upper and lower tangents to merge them.

Complexity: O(n log n).

Red-Black Tree Deletion Cases

Answer

Perform normal BST deletion. If a Black node is deleted, fix the double-black condition.

• Case 1: Sibling is Red. Action: Recolor and rotate.
• Case 2: Sibling is Black and both children are Black. Action: Recolor sibling to Red and move double-black up.
• Case 3: Sibling is Black, near child is Red, far child is Black. Action: Recolor and rotate sibling.
• Case 4: Sibling is Black and far child is Red. Action: Recolor and rotate parent.

Prim’s Algorithm for MST

Answer

Prim’s is a greedy algorithm that grows a single tree from a starting vertex.

Steps

1. Select any starting vertex and add it to the MST set.
2. Find the minimum-weight edge connecting the MST set to an outside vertex.
3. Add that edge and vertex to the MST.
4. Repeat until all vertices are included.

Complexity: O(V²) or O(E log V) with a priority queue.

Extract-Min in a Binomial Heap

Answer

1. Find and remove the minimum root.
2. Separate the children of the removed root.
3. Reverse the order of children to form a new Binomial Heap.
4. Perform Union of the new heap with the original heap.

Complexity: O(log n).

Prim’s vs. Kruskal’s Algorithm

Answer

Dijkstra vs. Bellman-Ford

Answer