Last Minute Notes Data Structures with Python
In the final hours before GATE DA, memorizing the exact time and space complexities of core data structure operations is one of the highest-return activiti...
Core Data Structure Complexities: Cheat Sheet for GATE
In the final hours before GATE DA, memorizing the exact time and space complexities of core data structure operations is one of the highest-return activities. Questions that ask for the complexity of a specific operation require instant recall, not derivation under pressure.
For Python lists (dynamic arrays): indexing is O(1); append is amortized O(1); insert at index i is O(n); delete at index i is O(n); search for a value is O(n); len() is O(1). For collections.deque: appendleft and popleft are O(1); indexed access is O(n). Never use a plain list as a queue because pop(0) is O(n).
For dictionaries and sets (hash tables): average-case lookup, insertion, and deletion are O(1); worst case is O(n) due to hash collisions, but this is rare in practice. For heapq (min-heap): heappush and heappop are O(log n); heapify is O(n); the minimum element is always at index 0 in O(1). For sorted containers (not built-in, but logically): binary search is O(log n) using the bisect module.
Binary search trees: average O(log n) for search, insert, delete when balanced; O(n) worst case when degenerate. AVL and Red-Black trees guarantee O(log n) by maintaining balance invariants through rotations. Python does not have a built-in balanced BST; sortedcontainers.SortedList from the third-party library provides O(log n) operations.
Graph traversal complexities with an adjacency list representation: BFS and DFS are both O(V + E) where V is the number of vertices and E is the number of edges. With an adjacency matrix, both are O(V^2). Dijkstra's algorithm with a priority queue is O((V + E) log V). Floyd-Warshall for all-pairs shortest paths is O(V^3).
Quick recall trick: when you see a problem involving finding the k-th largest element in a stream, the answer is a min-heap of size k, maintained with O(log k) per insertion. This pattern appears repeatedly in GATE DA and knowing the data structure immediately leads to the complexity answer.
Tree and Graph Algorithms: Last-Minute Key Points
Tree problems dominate the data structures section of GATE DA. Before the exam, confirm that you can trace through all four traversal orders on a given tree, compute the height of a tree, and determine whether a BST is valid. These skills underlie a large fraction of tree-related questions.
The height of a binary tree is defined as the number of edges on the longest path from the root to a leaf. A tree with a single node has height 0. An empty tree has height -1 by convention. The number of nodes in a complete binary tree of height h is between 2^h and 2^(h+1) - 1. A perfect binary tree of height h has exactly 2^(h+1) - 1 nodes.
AVL trees maintain the AVL property: for every node, the heights of left and right subtrees differ by at most 1. When this property is violated after insertion or deletion, rotations restore it. There are four rotation cases: left-left (single right rotation), right-right (single left rotation), left-right (left rotation then right rotation), and right-left (right rotation then left rotation). Knowing which rotation applies to which imbalance pattern is a common GATE question.
Heap properties: a max-heap requires every parent to be greater than or equal to its children. A min-heap requires every parent to be less than or equal to its children. Heaps are stored as arrays where the parent of element at index i is at index (i-1)//2, the left child is at 2i+1, and the right child is at 2i+2. Heapsort builds a max-heap from an array in O(n) and then extracts the maximum n times, achieving O(n log n) total with O(1) extra space.
Topological sort applies to directed acyclic graphs (DAGs). It produces an ordering of vertices such that for every directed edge u -> v, u appears before v. Kahn's algorithm uses in-degree counts and a queue. DFS-based topological sort pushes vertices to a stack in reverse finish order. Both run in O(V + E). Detecting a cycle invalidates topological sort; if the algorithm finishes without processing all nodes, a cycle exists.
Dynamic Programming and Recursion Patterns: Final Review
Dynamic programming is one of the most tested topics in GATE DA computer science sections. The core idea is to avoid recomputing overlapping subproblems by storing their results. The two approaches are top-down memoization (recursive with caching) and bottom-up tabulation (iterative with a DP table).
Identifying a DP problem requires recognizing two properties: optimal substructure, meaning the optimal solution contains optimal solutions to subproblems, and overlapping subproblems, meaning the same subproblems recur many times. Classic DP problems include Fibonacci, longest common subsequence, longest increasing subsequence, 0/1 knapsack, coin change, and edit distance. Each of these is worth practicing until you can code the solution from memory.
The 0/1 knapsack problem: given n items each with weight w_i and value v_i, and a knapsack of capacity W, maximize total value without exceeding weight. The DP table dp[i][j] = maximum value using items 1..i with capacity j. Recurrence: dp[i][j] = max(dp[i-1][j], dp[i-1][j-w_i] + v_i) if j >= w_i, else dp[i-1][j]. Time complexity O(nW), space O(nW), reducible to O(W) with a 1D table.
The longest common subsequence (LCS) of sequences X and Y: dp[i][j] = length of LCS of X[1..i] and Y[1..j]. Recurrence: if X[i] == Y[j], dp[i][j] = dp[i-1][j-1] + 1; else dp[i][j] = max(dp[i-1][j], dp[i][j-1]). Time and space O(mn) where m and n are the lengths of X and Y.
Final tip for GATE: when a DP question gives you a recurrence relation and asks for the base cases, think about what the smallest meaningful subproblem is. For subsequence problems it is empty strings (length 0). For knapsack it is zero items or zero capacity. Getting base cases wrong produces incorrect answers even with a correct recurrence, so double-check them before filling the table.