Implement Core Data Structures From Scratch with Complexity Analysis
6 weeks · 0 milestones
Implement a linked list, binary search tree, hash table, min-heap, and adjacency-list graph from scratch in any language — no library primitives for the core data structure logic. Each implementation must include a full test suite covering edge cases and a documented time and space complexity analysis explaining why each operation has the stated complexity (not just stating it). Proof: the implementations and analysis reviewed by a CS lecturer or senior software engineer who asks 'why is your hash table O(1) amortised for insertion rather than O(1) worst-case?' — you must answer by pointing to your specific implementation and the conditions that trigger rehashing.
Milestone map
Milestone map
4 milestones
Before writing implementation code, design the interface (API) for each data structure: linked list, binary search tree, hash table, min-heap, and adjacency-list graph. For each structure, specify the supported operations, their time and space complexity, and any preconditions or invariants. This design-first step enforces understanding before implementation and is required documentation for the completeness of this milestone.
Proof required
Submit a design document (or README) defining the interface for all five data structures. For each structure, provide: (a) a list of all supported operations with method signatures, (b) the time complexity (Big-O) of each operation with a one-sentence justification, (c) the space complexity, and (d) one invariant the implementation must maintain (e.g., 'BST property: for any node N, all values in N's left subtree are less than N.key'). The document must be written before any implementation code exists.
What gets checked
- All five data structures are covered with complete operation lists — not just the most common operations
- Time complexity justifications are correct and specific — 'O(log n) because BST height is log n for a balanced tree' not just 'O(log n)'
- Invariants are stated precisely — they should be checkable programmatically