Implement Core Data Structures From Scratch with Complexity Analysis

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

Common mistakes

• Writing implementation code before the design document — this milestone specifically requires design to precede code
• Copying complexity tables from Wikipedia without understanding them — the justification sentences will reveal whether the submitter understands why each complexity holds

Resources

What a verifier looks for

• You are a CS professional (software engineer, researcher, or CS educator) reviewing a data structures implementation. Start with the design document — check that the complexity claims are correct. Common errors: claiming O(1) BST search without noting this requires a balanced tree, or claiming O(1) hash table operations without noting worst-case is O(n).
• The design document must predate the code — ask the submitter when they wrote it relative to starting implementation.

Proof required

Submit a public GitHub repository (or equivalent) containing the five implementations in a single language. The repository must include: (a) one source file or module per data structure, (b) a README with build and run instructions, (c) at least three worked examples per data structure showing correct output, and (d) confirmation that no standard library data structure types (e.g., Python's list as a linked list, Java's TreeMap as a BST) are used in the implementations.

What gets checked

• All five implementations are complete with all specified operations — none of the five may be partially implemented
• Worked examples show correct output for non-trivial cases (e.g., BST deletion with two children, hash table collision resolution, heap extraction with re-heapification)
• No standard library data structure is used as the underlying implementation — an ArrayList wrapping Java's LinkedList is not 'from scratch'

Common mistakes

• BST deletion is not implemented or is implemented incorrectly for the three-case scenario (leaf, one child, two children) — this is the hardest operation and most commonly skipped
• Hash table collision resolution strategy is not implemented — a hash table without collision handling is incorrect

Resources

What a verifier looks for

• Clone the repository and attempt to build and run it. Check that the build instructions in the README work.
• Test edge cases: delete the root of a BST, try to extract-min from an empty heap, add items that collide in the hash table. Correct implementations handle these without crashes or incorrect output.
• Ask the submitter to explain their BST deletion implementation — this is the most complex operation and reveals whether they understand the algorithm or just found working code.

Proof required

Submit the test suite as part of the same repository. The suite must include: (a) at least eight tests per data structure (40 minimum total), (b) at least two edge-case tests per data structure, (c) a test runner output showing all tests passing, and (d) a brief description of what each test group covers. The test runner output must be reproducible — tests pass on a fresh clone.

What gets checked

• At least 40 tests total (8 minimum per structure) — tests must cover the operations listed in the design document
• Edge cases are present for all five structures — empty-structure operations, single-element structures, and boundary conditions
• Test runner output is clean — all tests pass, no test skipped

Common mistakes

• Tests only cover the happy path — no tests for edge cases or error conditions
• Tests are written as print-and-inspect scripts without assertions — a proper test suite uses assert() or equivalent and fails automatically on incorrect output

Resources

What a verifier looks for

• Clone the repository, follow the README instructions, and run the test suite. All tests must pass.
• Count the tests: fewer than 40 total or fewer than 8 per structure means the suite is incomplete. Ask the submitter which edge cases their tests cover for the hash table — collision handling tests are the most revealing.
• If any test fails on a clean clone, the submission is incomplete regardless of the submitter's local result.

Proof required

Submit: (a) a written record of the expert Q&A session (minimum 500 words) documenting the questions asked and your responses, or a link to a recording, and (b) written confirmation from the reviewer stating their professional background, the date of the session, that the questions were technical and not pre-shared, and their overall assessment of your understanding. The reviewer must confirm you answered at least four technical questions in real time without consulting notes.

What gets checked

• Q&A record documents at least four distinct technical questions and substantive answers — not just 'what is a BST' but 'explain why your BST implementation's worst-case is O(n), not O(log n)'
• Reviewer confirmation includes a genuine assessment — 'their explanation of hash collision resolution was clear and correct' not just 'passed'
• Questions were adversarial — the reviewer should have asked at least one question the submitter found difficult

Common mistakes

• Q&A record shows only easy questions with obvious answers — a real technical reviewer will probe edge cases and worst-case scenarios
• Reviewer has no relevant CS or software engineering background — the qualification matters because complexity analysis is domain-specific

Resources

What a verifier looks for

• You are a CS professional conducting a technical review of data structure implementations. Prepare three to five questions before the session based on the submitted code — for example: 'Your hash table uses linear probing. What happens to your search time as the load factor approaches 1?' or 'Why did you choose this collision resolution strategy over chaining?'
• Ask at least one question the submitter cannot answer from memory — a 'what if' question that requires reasoning: 'If you needed to support O(1) find-min on your BST, what would you change?'
• Your written confirmation must name you, state your professional background, give the date, confirm that questions were technical and not pre-shared, and provide a brief assessment of the submitter's understanding. This is the external verification anchor for this milestone.