Data Structures and Algorithms
Data Structures and Algorithms tests whether you can choose a structure that fits an operation and can trace basic algorithms by hand: stacks, queues, linked lists, binary trees, linear and binary search, simple sorts, and a first look at time complexity.
Core rules
- Stack: LIFO, with push and pop at the top; used for function calls, undo, expression evaluation and bracket matching.
- Queue: FIFO, enqueue at the rear, dequeue at the front; used for scheduling and buffers.
- A linked list node holds data plus a pointer; insertion and deletion are O(1) at a known position, but access is O(n).
- Binary search needs a sorted array and halves the search space each step, O(log n). Linear search is O(n) and needs no ordering.
- Bubble sort compares adjacent pairs and swaps; after pass k the largest k items are in place; worst case O(n²).
- In a binary tree each node has at most two children; inorder traversal (left, root, right) of a BST gives sorted output.
Worked example
Binary search for 23 in [2, 5, 8, 12, 16, 23, 38, 56, 72, 91], indices 0–9.
- low = 0, high = 9, mid = 4 → value 16 < 23, so low = 5.
- low = 5, high = 9, mid = 7 → value 56 > 23, so high = 6.
- low = 5, high = 6, mid = 5 → value 23, found after 3 comparisons.
Traps
- Applying binary search to an unsorted list.
- Mixing up stack and queue output order in a push/pop trace.
- Not recomputing mid after low or high changes.
- Claiming bubble sort is O(n log n), or that a stack allows random access.