Big-O, arrays, hashing, trees, graphs, DP, coding-round patterns
Practise these as flashcards. One or two lines each; the ones you miss come back first.
Start freeBig-O notation describes how an algorithm's time or space requirements grow as the input size increases. It's important because it helps us compare and choose efficient algorithms, especially for large datasets.
I iterate through the list, changing each node's next pointer to point to the previous node. At the end, the last node becomes the new head. This is an O(n) time, O(1) space operation.
A hash map is a data structure that stores key-value pairs and allows fast lookups, inserts, and deletes. I use it when I need to count elements, check for duplicates, or map values efficiently.
A stack is Last-In-First-Out (LIFO), so the last element added is removed first. A queue is First-In-First-Out (FIFO), so the first element added is removed first.
The sliding window technique maintains a window of elements and moves it across the array or string to solve problems efficiently. For example, to find the maximum sum of k consecutive elements, I sum the first k, then slide the window by adding the next element and removing the first, updating the sum each time.
I use two pointers: one moves one step at a time (slow), the other moves two steps (fast). If there's a cycle, they will eventually meet; if not, the fast pointer will reach the end. This is Floyd's algorithm and runs in O(n) time.
Collisions occur when two keys hash to the same bucket. They're handled by chaining (storing multiple items in a bucket, usually as a list) or open addressing (finding another bucket using a probing sequence).
BFS explores nodes level by level using a queue, making it ideal for shortest path in unweighted graphs. DFS explores as deep as possible using a stack or recursion, which is useful for connectivity and cycle detection.
Binary search finds an element or boundary in a sorted array by repeatedly dividing the search interval in half. I use it when the data is sorted and I need O(log n) search time.
A heap is a binary tree where each parent node is smaller (min-heap) or larger (max-heap) than its children. It's used for priority queues, scheduling, and efficiently finding the minimum or maximum element.
Memoization is a top-down approach where I cache results of recursive calls. Tabulation is a bottom-up approach where I fill a table iteratively. Both avoid redundant calculations, but tabulation is often more space-efficient and avoids recursion stack limits.
A monotonic stack maintains elements in increasing or decreasing order. It's used for problems like finding the next greater or smaller element in an array, which can be solved in O(n) time.