Linear structures
Array vs linked list?
Arrays give O(1) random access but costly inserts/deletes in the middle (shifting). Linked lists give O(1) insert/delete at a known node but O(n) access since you must walk the list. Choose by whether you index randomly or mutate often.
Stack vs queue, with real uses?
A stack is LIFO - used for undo, the call stack and DFS. A queue is FIFO - used for scheduling and BFS. Both are simple but appear constantly in interview problems.
How do you detect a cycle in a linked list?
Floyd's tortoise-and-hare: move one pointer one step and another two steps. If they ever meet, there's a cycle; if the fast pointer hits null, there isn't. It runs in O(n) time and O(1) space.
Trees & graphs
Binary tree vs binary search tree?
A BST orders nodes so left < root < right, giving O(log n) search, insert and delete when balanced - but O(n) if it degenerates into a chain. A plain binary tree has no such ordering.
Name the tree traversals and their uses.
Inorder (gives sorted order for a BST), preorder (used to copy a tree), postorder (used to delete a tree), and level-order/BFS (visits nodes depth by depth).
How do you represent a graph, and BFS vs DFS?
An adjacency list suits sparse graphs; an adjacency matrix suits dense ones. BFS explores level by level and finds shortest paths in unweighted graphs; DFS goes deep and is used for cycle detection and topological sorting.
When do you reach for a heap or a hash map?
Use a heap (priority queue) when you repeatedly need the min or max, such as top-K or Dijkstra. Use a hash map for O(1) lookups, counting frequencies, or checking membership.
Sorting & complexity
How do you find the Big-O of a snippet?
Count how the work grows with input size: a single loop is O(n), nested loops O(n^2), and repeatedly halving the input O(log n). This is the most common screening question, so make it instant.
Quick sort vs merge sort?
Quick sort averages O(n log n) and sorts in place, but degrades to O(n^2) on bad pivots and isn't stable. Merge sort is stable and guaranteed O(n log n) but needs O(n) extra space.
When can you beat O(n log n) sorting?
Comparison-based sorts can't do better than O(n log n). But when keys are bounded integers, counting or radix sort reach O(n), and hashing gives O(1) average lookups instead of sorting at all.
Practice this now