Data Structures and Algorithms Last-Minute Revision

30 quick revision notes for Data Structures and Algorithms

1. Big-O gives an upper bound on growth; drop constants and lower terms, so 3n squared plus 5n is O(n squared).
2. About 10 to the power 8 simple operations run per second, so for n up to 10 to the power 5 aim for O(n log n).
3. Amortised O(1) append in dynamic arrays comes from doubling capacity, so total copying over n appends stays under 2n.
4. Every recursive function needs a correct base case; deep recursion can overflow the stack in Java and Python.
5. Master Theorem: merge sort T(n) = 2T(n/2) + n is O(n log n), and binary search T(n) = T(n/2) + 1 is O(log n).
6. Two pointers and sliding window turn many O(n squared) array and string problems into O(n) solutions.
7. Prefix sums answer range sum queries in O(1) after O(n) preprocessing; a hash map of prefix sums counts subarrays with sum k.
8. Hash maps give average O(1) operations, but poor hash functions or many collisions can degrade them toward O(n).
9. Kadane's algorithm finds the maximum subarray sum in O(n) by choosing to extend or restart at each element.
10. Floyd's slow and fast pointers detect a linked list cycle in O(n) time and O(1) space.
11. A dummy node before the head removes special cases when the head of a linked list may change.
12. Monotonic stacks solve next greater element and histogram problems in O(n) because each element is pushed and popped once.
13. A queue built from two stacks gives amortised O(1) dequeue because each element moves between stacks only once.
14. Inorder traversal of a binary search tree returns keys in sorted order.
15. BST operations cost O(h); balanced trees keep h near log n, while sorted inserts into a plain BST make it skewed.
16. Validate a BST by passing lower and upper bounds down the recursion, not by comparing only with children.
17. Tries search a word of length L in O(L), independent of the number of stored words.
18. Building a heap from n elements takes O(n), while each insert or extract costs O(log n).
19. Use a min-heap of size k to find the k largest elements in O(n log k) time.
20. Greedy works only with the greedy choice property; test small counterexamples before trusting a greedy rule.
21. BFS finds shortest paths in unweighted graphs; Dijkstra handles non-negative weights; Bellman-Ford handles negative weights.
22. Topological sort exists only for DAGs; if Kahn's algorithm outputs fewer vertices than the graph has, there is a cycle.
23. Union-Find with path compression and union by size gives nearly constant time per operation.
24. Kruskal's MST sorts edges and uses Union-Find, while Prim's grows the tree with a min-heap.
25. Dynamic programming needs overlapping subproblems and optimal substructure; define state, transition, base case and order.
26. 0/1 knapsack in one array iterates capacity downwards; unbounded knapsack iterates capacity upwards.
27. LCS and edit distance use an m by n table and can be reduced to O(n) space using two rows.
28. Comparison sorts need at least n log n comparisons; counting and radix sort beat this for small integer ranges.
29. Use low plus (high minus low) divided by 2 for mid in Java to avoid integer overflow in binary search.
30. Binary search on the answer works whenever feasibility is monotonic, such as minimum capacity to finish within D days.

Night-before checklist

• Revise your saved questions on this page once, aloud.
• Read the quick notes and mark any you cannot explain in one line.
• Rehearse a two-minute self-introduction and two project stories.
• Keep CV, ID, laptop charger and interview link ready; sleep on time.