DSA Refresher
Arrays, strings, linked lists, trees, complexity — the "small code" viva slice.
Start here
Not a full coding-interview grind — making sure that if the panel hands you a pen and asks for ten lines of code, you don't freeze. Two ideas do most of the work.
- "Efficient" = — shorthand for "how much slower does this get as input grows." O(n) doubles when input doubles; O(n²) quadruples. Recognize the shape: one loop ≈ O(n), nested loop ≈ O(n²), halving each step () ≈ O(log n).
- The toolbox — arrays/strings (, sliding-window), linked lists (nodes chained to the next), stacks/queues, trees (branching hierarchy), hash maps (instant lookup by key).
Almost every "small code" question is one of these building blocks in disguise — recognizing which one applies is 80% of the battle.
Why this is here
The HR call flagged "small code possible" — not a full LeetCode grind, but enough DSA fluency to write 10-15 lines cleanly on a whiteboard or paper without an IDE.
Core threads
- Complexity: know for common ops (array access O(1), search O(n), sorted-array O(log n), hash lookup O(1) avg). Always state time *and* space complexity after solving.
- Arrays/strings: and sliding-window patterns solve most "small code" prompts fast (reverse a string in place, check palindrome, find a pair summing to target).
- Linked lists: reversing in place (three-pointer walk: prev/curr/next), detecting a cycle (Floyd's fast-slow pointer).
- Trees: recursive traversal (pre/in/post-order), via queue for level-order — know when to "return up" a value vs "pass down" a value through recursion.
- Hashing: the go-to for O(1) lookups/dedup/frequency counting — most interview "small code" problems reduce to a trick.
Viva angle
Practice writing these on paper, no IDE, no autocomplete — that's the actual test condition. Speed and clean syntax matter less than correct logic explained while writing.
Visual reference
Big-O growth rates
Two-pointer technique
Cheatsheet
Big-O growth (best to worst)
| Notation | Name | Example |
|---|---|---|
| O(1) | Constant | Array index access, hash lookup |
| O(log n) | Logarithmic | Binary search |
| O(n) | Linear | Single loop / scan |
| O(n log n) | Linearithmic | Good sorting (merge/quick sort) |
| O(n²) | Quadratic | Nested loop / naive pair check |
Which structure for which job
| Need | Use |
|---|---|
| Instant lookup / dedup / counting | Hash map |
| Sorted-input search | Binary search |
| Best contiguous subarray/substring | Sliding window |
| Pair/triplet in sorted array | Two pointer |
| Shortest path, unweighted | BFS |
| Explore all paths / backtracking | DFS |
- ▸Always state time AND space complexity after solving.
- ▸Reverse a linked list: three pointers — prev, curr, next.
- ▸Cycle detection: Floyd's fast-slow pointer.
- ▸Merge two sorted arrays: two pointers, always copy the smaller — the heart of merge sort.
Further study
Question bank
17 questionsWhat is and what does it measure?
Write (or describe step by step) how you'd check if a string is a palindrome without extra space.
Describe how to reverse a singly linked list in place.
How do you detect a cycle in a linked list without extra memory?
How would you check if a string of brackets ( { [ is validly matched and nested?
What is the difference between and traversal of a tree, and when would you use each?
How does a achieve O(1) average lookup, and when does it degrade?
Given an array, describe an O(n) approach to find two numbers that sum to a target (Two Sum).
Why does require a sorted array, and what is its time complexity?
After solving a coding problem, why is it important to always state both time and space complexity?
Compare merge sort and quicksort — how each works at a high level, and when would you prefer one over the other?
What is dynamic programming, and how does it apply to a problem like climbing stairs or computing Fibonacci numbers?
Compare adjacency list and adjacency matrix as ways to represent a graph — what are the space and lookup tradeoffs?
What operations does a heap (priority queue) support efficiently, and what's a classic use case?
What are the tradeoffs between solving a problem recursively vs iteratively?
Quickly compare the time complexity of bubble sort, merge sort, quicksort, and heap sort — best, average, and worst case.
Describe how to merge two already-sorted arrays into one sorted array in O(n + m).