Programming and Data Structures
Core concepts
Candidates need control structures, functions and parameter passing (by value versus by reference), recursion, pointers, scope and lifetime of variables, and static versus dynamic binding. Know the phases of program translation: preprocessing, compilation, assembly, linking, and loading.
Data structures form the analytical core. Understand arrays, linked lists (singly, doubly, circular), stacks (LIFO), queues (FIFO, circular queue, priority queue), trees (binary search tree, AVL balance, heap), graphs (adjacency matrix versus list), and hashing with collision resolution (chaining, open addressing). Know traversal orders: inorder, preorder, postorder for trees; BFS and DFS for graphs. Sorting and searching complexity matters: bubble, insertion, selection O(n^2); merge and heap O(n log n); quicksort average O(n log n) worst O(n^2); binary search O(log n) on sorted data.
Traps to watch
- Confusing stack (function calls, expression evaluation) with queue (scheduling, BFS).
- Forgetting that a BST inorder traversal yields sorted order.
- Assuming a hash table guarantees O(1) worst case; it is average case.
- Mixing up preorder (root first) with postorder (root last).
Worked example
Evaluate postfix 5 3 + 8 2 - : push 5, push 3, '+' pops 3 and 5 giving 8; push 8, push 2, '-' gives 6; '' multiplies 8 and 6 giving 48. Rule of thumb: postfix evaluation uses one stack and never needs parentheses.