Data Structures Interview Questions

Contiguous memory, fast index access O(1), insert/delete in middle O(n).

const a = [3,1,2];
a.push(5); // O(1)
a.splice(1, 0, 9); // O(n)

Nodes with pointers; insert/delete O(1) at known position, access by index O(n).

// Singly list node
class Node { constructor(val, next=null){ this.val=val; this.next=next; } }

Stack: LIFO (push/pop). Queue: FIFO (enqueue/dequeue).

const stack = [];
stack.push(1); stack.push(2); stack.pop(); // 2

const queue = [];
queue.push(1); queue.push(2); queue.shift(); // 1

Average O(1) get/set via hashing, worst-case O(n) with collisions.

const m = new Map();
m.set('a', 1);
m.get('a'); // 1

Binary tree: each node up to 2 children. BST: left < node < right; search/insert O(log n) average.

// In-order traversal (DFS)
function inorder(root){
  if(!root) return;
  inorder(root.left);
  console.log(root.val);
  inorder(root.right);
}

Complete binary tree; min-heap keeps smallest at root. Insert/remove O(log n).

Vertices and edges; represented via adjacency list/matrix. Traverse with BFS/DFS.

// BFS
function bfs(start, adj){
  const q=[start], seen=new Set([start]);
  while(q.length){
    const v=q.shift();
    for(const n of adj[v]) if(!seen.has(n)){ seen.add(n); q.push(n); }
  }
}

Big-O describes growth: O(1), O(log n), O(n), O(n log n), O(n^2). Optimize by choosing suitable structures.

Hierarchical structure with parent/children; binary tree has up to two children per node. Traversals: inorder, preorder, postorder.

Maintains ordered keys; average O(log n) search/insert/delete; degenerates to O(n) if unbalanced.

Binary heap supports efficient min/max retrieval (insert/extract O(log n)). Used in Dijkstra, scheduling.

Prefix tree for fast string lookups (autocomplete); edges labeled by characters; space-heavy but efficient.

Adjacency list (sparse) vs adjacency matrix (dense). Choose based on edge density and algorithm needs.

Supports union/find operations with path compression and union by rank; used in connectivity and Kruskal's algorithm.

Space-efficient probabilistic set with false positives but no false negatives; used for cache/membership tests.

Singly vs doubly linked; operations are O(1) for insert/delete when node known; traversal is O(n).

Separate chaining vs open addressing (linear probing, quadratic, double hashing); trade-offs in cache locality and performance.

Combine hash map + doubly-linked list to achieve O(1) get/put and eviction of least recently used items.

Supports range queries and updates in O(log n); built over array indices as a binary tree.

Self-balancing BST guaranteeing O(log n) operations via color properties and rotations; widely used in language libraries.