DSA Interview Questions with Answers

Array: Access O(1), Search O(n), Insert at end O(1) amortized, Insert at position O(n), Delete O(n). Linked List: Access O(n), Search O(n), Insert at head O(1), Insert at position O(n), Delete O(1) if node known. Arrays have better cache locality.

BFS (Breadth-First): uses queue, explores level by level. Best for shortest path in unweighted graphs. DFS (Depth-First): uses stack/recursion, explores as deep as possible. Best for cycle detection, topological sort, connected components. BFS uses O(V) space, DFS uses O(height) space.

DP solves problems by breaking them into overlapping subproblems, storing results to avoid recomputation. Identify DP: (1) Optimal substructure — optimal solution uses optimal sub-solutions, (2) Overlapping subproblems — same subproblems solved multiple times. Approach: define state → recurrence relation → base cases → tabulation/memoization.

Two main methods: (1) Chaining — each bucket stores a linked list of entries. Simple but uses extra memory. (2) Open Addressing — find next empty slot using linear probing, quadratic probing, or double hashing. Better cache performance but degrades at high load factors. Good hash table: O(1) average for insert/search/delete.

Stack: LIFO (Last In, First Out). push/pop from top. Use cases: function calls, undo, expression evaluation, DFS. Queue: FIFO (First In, First Out). enqueue at back, dequeue from front. Use cases: BFS, task scheduling, buffering. Both have O(1) push/pop operations.

A balanced BST (AVL, Red-Black tree) ensures height is O(log n), guaranteeing O(log n) search/insert/delete. Unbalanced BST can degrade to O(n) — essentially a linked list. Java's TreeMap uses Red-Black tree. AVL is more strictly balanced (heights differ by ≤1) but has costlier rotations.

Floyd's Tortoise and Hare algorithm: use two pointers — slow moves 1 step, fast moves 2 steps. If they meet, there's a cycle. To find cycle start: reset one pointer to head, move both at 1 step — they meet at the cycle start. Time: O(n), Space: O(1).

Merge Sort: divide array, sort halves, merge. Always O(n log n). Stable. Extra O(n) space. Quick Sort: pick pivot, partition, sort partitions. Average O(n log n), worst O(n²). In-place (O(log n) stack). Not stable. Quick Sort is faster in practice due to cache locality.