Core Complexity & Performance

Misconception Reality Interview Trap Strong Answer
Big-O gives exact runtime Big-O shows growth rate, not actual time “Is O(N²) always slower than O(N log N)?” Asymptotically yes, but constants matter more for small N
More memory always means faster Memory can hurt cache & GC “Does memoization always help?” Only if recomputation cost is higher

Trees & Hierarchical Structures

Misconception Reality Interview Trap Strong Answer
BST is always O(log N) Only if balanced “Is BST better than array search?” Only if balanced
Heap is sorted Only parent-child order “Can you binary search a heap?” No
Priority Queue = Heap PQ is ADT; heap is implementation “Can PQ exist without heap?” Yes

Hashing & Lookup

Misconception Reality Interview Trap Strong Answer
Hash table is always O(1) Worst case is O(N) “Why not use hash tables everywhere?” No ordering, collision risk
HashMap > TreeMap always Depends on use case “Why TreeMap?” Sorted keys & range queries

Arrays, Lists & Memory

Misconception Reality Interview Trap Strong Answer
Linked lists are better than arrays Arrays have cache locality “Why arrays are faster?” Contiguous memory
Shifting in array is fine Shifting is O(N) “Why circular queue?” Avoids shifting

Recursion & Control Flow

Misconception Reality Interview Trap Strong Answer
Recursion is inefficient Fine for bounded depth “Always convert to loop?” Only if stack overflow risk
Recursion uses no extra space Uses call stack “Space complexity?” O(depth)

Tries & Graphs

Misconception Reality Interview Trap Strong Answer
Tries are faster than hash tables Key-length dependent “Why not hash?” Prefix queries
DFS = BFS DFS explores depth, BFS explores level-wise. “Shortest path?” BFS (unweighted)
Adjacency matrix is inefficient Good for dense graphs “Matrix vs list?” Density & lookup speed