Question 1

Why are arrays faster to iterate over than linked lists even when both have O(N) time complexity?

Accepted Answer

Arrays benefit from spatial locality and alignment with CPU cache lines, while linked-list nodes are scattered randomly across the heap.

Question 2

How do hash tables work, and what is the difference between collision resolution by chaining and open addressing?

Accepted Answer

A hash function maps a key to a numeric index in an internal array for O(1) access. If two different keys map to the same index (a collision), resolve it with linked lists (chaining) or by searching for available slots (open addressing).

Question 3

What are binary search trees (BSTs), and why do we need self-balancing trees such as AVL and Red-Black trees?

Accepted Answer

A BST ensures the left child is smaller than a node and the right child is larger. However, inserting sorted values turns it into a skewed line with O(N) operations, so self-balancing trees use rotations to maintain O(log N) depth.

Question 4

Compare a Queue and a Stack, and what are monotonic stacks?

Accepted Answer

A Stack is last-in, first-out (LIFO), and a Queue is first-in, first-out (FIFO). A monotonic stack keeps its elements in strictly ascending or descending order to solve range problems in O(N).

Question 5

How does a binary heap work, and how can a simple array represent it without node pointers, including Heapify?

Accepted Answer

A binary heap is a nearly complete binary tree that satisfies the heap property (in a Min-Heap each parent is smaller than its children; in a Max-Heap it is larger). It is efficiently represented as an array where the children of index i are at 2i+1 and 2i+2.

Question 6

What is the difference between an adjacency matrix and an adjacency list for representing graphs?

Accepted Answer

An adjacency matrix uses a two-dimensional V×V grid, which is excellent for dense graphs and checks for an edge in O(1). An adjacency list stores each vertex's neighbors in a space-efficient O(V + E) structure, ideal for sparse graphs.

Question 7

How does a Trie (Prefix Tree) work, and why is it better than hash tables for prefix search and autocomplete?

Accepted Answer

A Trie stores strings character by character so words with the same prefix share a path, allowing lookup and prefix retrieval in O(L), where L is the word length, independent of the number of stored words.

Question 8

How do you design an LRU (Least Recently Used) cache with strict O(1) Get and Put operations?

Accepted Answer

Combine two data structures: a Hash Map for immediate O(1) lookup and a Doubly Linked List to track usage order and add or remove elements in O(1).

Question 9

When should you use a Segment Tree or Fenwick Tree (BIT) for range queries?

Accepted Answer

Use them when you need arithmetic range queries over an array that changes over time (such as range sum or minimum) along with frequent dynamic item updates, all in O(log N).

Question 10

What is the fundamental difference between Stack Memory and Heap Memory for program resource management?

Accepted Answer

The Stack is a very fast linear memory area managed automatically by the processor for local variables and function frames. The Heap is a large dynamic area for variable-sized objects, managed by the programmer or garbage collector (GC).