Phase 1 Exit Criteria and Projects

This is your gate. Phase 2 covers sorting, searching, and recursion — and every single topic there assumes you have the Phase 1 data structures locked. If you advance without meeting these criteria, you will hit a wall at the first medium-hard sorting problem and spend time re-learning what you should have known cold. The exit criteria below are not suggestions. Treat them as a pass/fail test you run on yourself.

---

Exit Criteria

You are ready for Phase 2 when you can do all of the following without looking anything up:

Implementation

• Implement a dynamic array (with doubling resizing) with correct push, pop, get, set operations — in under 30 minutes

• Implement a doubly linked list with insert_at_head, insert_at_tail, delete_node (given node reference), reverse — in under 40 minutes

• Implement a stack (array-backed) and a queue (circular buffer) — in under 30 minutes total

• Implement a hash map with separate chaining, including correct put, get, remove, and resize-on-load-factor — in under 45 minutes

• Implement a min-heap with insert, extract_min, and build_heap from array — in under 40 minutes

Complexity

• State the time complexity of every core operation for every data structure in this phase, with derivations if asked (not just lookup)

• Explain why build-heap is O(n) and not O(n log n), clearly, in under 90 seconds

• Explain the amortized O(1) cost of dynamic array push and hash map insert

Problem Solving

• Solve any easy LeetCode problem in these data structures in under 15 minutes

• Solve any medium LeetCode problem in these data structures in under 25 minutes

• Recognize the monotonic stack pattern from a problem description and implement it without reference

Mechanical Understanding

• Explain Floyd’s cycle detection algorithm — why it works, not just what it does — in under 2 minutes

• Describe the difference between separate chaining and open addressing, including which Java/C++/Python uses

---

Project 1: From-Scratch Implementations

What: Implement the following 6 data structures in your language of choice (Java recommended — strong typing forces you to be precise). Write them in a single file or a well-organized package.

Structure	Required Operations	Notes
Dynamic Array	push(x), pop(), get(i), set(i,x), size(), resize()	Internal array doubles on overflow
Doubly Linked List	insertHead(x), insertTail(x), delete(node), toArray(), reverse()	Use dummy head+tail sentinels
Stack (array-backed)	push(x), pop(), peek(), isEmpty()	Throw on underflow
Queue (circular buffer)	enqueue(x), dequeue(), peek(), isFull(), isEmpty()	Fixed-capacity version
Min-Heap	insert(x), extractMin(), peek(), buildHeap(arr[])	Must include both siftUp and siftDown
HashMap with Chaining	put(k,v), get(k), remove(k), containsKey(k), resize	Resize when load factor > 0.75

Write your own tests. For each implementation, write at least 5 test cases covering:

1. Empty structure operations (should handle gracefully)

2. Single element

3. Multiple elements with one removal

4. Edge case specific to the structure (e.g., circular buffer wrap-around for Queue; collision handling for HashMap)

5. Stress test: insert 1000 random elements, verify correctness

Acceptance criteria: All operations correct. All 5 test cases pass per structure. No references used during the final write (it’s fine to look things up while learning, but do a clean implementation pass at the end).

Estimated time: 12–16 hours spread across Week 8 and Week 9.

---

Project 2: LeetCode 30-Problem Sprint

What: Solve exactly 30 LeetCode problems, distributed as follows. Track your time-to-first-acceptance and whether you solved it independently or with hints.

Arrays & Strings (8 problems)

#	Title	Difficulty	Pattern
26	Remove Duplicates from Sorted Array	Easy	Fast/slow pointer
121	Best Time to Buy and Sell Stock	Easy	Single pass, track min
283	Move Zeroes	Easy	Fast/slow pointer
11	Container With Most Water	Medium	Left/right pointer
15	3Sum	Medium	Sort + two pointer
238	Product of Array Except Self	Medium	Prefix + suffix product
560	Subarray Sum Equals K	Medium	Prefix sum + hash map
42	Trapping Rain Water	Hard	Two-pointer or prefix max

Linked Lists (6 problems)

#	Title	Difficulty	Pattern
206	Reverse Linked List	Easy	Iterative pointer surgery
21	Merge Two Sorted Lists	Easy	Sentinel + merge
141	Linked List Cycle	Medium	Floyd’s slow/fast
142	Linked List Cycle II	Medium	Floyd’s + phase 2
19	Remove Nth Node From End	Medium	Two-pointer with gap
25	Reverse Nodes in k-Group	Hard	Group pointer surgery

Stacks & Queues (6 problems)

#	Title	Difficulty	Pattern
20	Valid Parentheses	Easy	Stack matching
155	Min Stack	Medium	Auxiliary min tracking
739	Daily Temperatures	Medium	Monotonic stack
150	Evaluate Reverse Polish Notation	Medium	Stack expression eval
239	Sliding Window Maximum	Hard	Monotonic deque
84	Largest Rectangle in Histogram	Hard	Monotonic stack (both sides)

Hash Tables (5 problems)

#	Title	Difficulty	Pattern
242	Valid Anagram	Easy	Frequency count
49	Group Anagrams	Medium	Sorted key grouping
128	Longest Consecutive Sequence	Medium	Hash set O(n)
347	Top K Frequent Elements	Medium	Frequency + heap
41	First Missing Positive	Hard	Array as hash map

Heaps (5 problems)

#	Title	Difficulty	Pattern
703	Kth Largest in Stream	Easy	Min-heap size k
215	Kth Largest in Array	Medium	Min-heap or quickselect
1046	Last Stone Weight	Medium	Max-heap simulation
373	Find K Pairs Smallest Sums	Medium	Heap + lazy evaluation
23	Merge K Sorted Lists	Hard	Heap over list heads

Tracking sheet: For each problem, record:

• Date solved

• Time to first acceptance (minutes)

• Independent (I) / Hint needed (H) / Had to look up solution (L)

• Pattern used (in your own words, one sentence)

Acceptance criteria: ≥ 24/30 solved independently (80%). For the 6 you looked up, write a 3-sentence explanation of the key insight you missed.

Estimated time: 20–25 hours spread across Weeks 9–11.

---

Project 3: Pattern Taxonomy Document

What: A single-page (or two-page) personal cheatsheet — written by hand or typed — containing every pattern you encountered in this phase, with one concrete problem per pattern.

Required Patterns

Pattern	One-Line Description	Canonical Problem
Two-Pointer (left/right)	Shrink from both ends of sorted data	LeetCode #15 3Sum
Two-Pointer (fast/slow)	Fast scans, slow writes valid elements	LeetCode #26 Remove Duplicates
Prefix Sum	Precompute cumulative sums for O(1) range queries	LeetCode #560 Subarray Sum = K
Sentinel Node	Dummy head avoids head-pointer edge cases	LeetCode #21 Merge Two Sorted Lists
Floyd’s Cycle Detection	Slow/fast pointers meet in a cycle	LeetCode #142 Cycle II
Monotonic Stack	Maintain sorted stack for next-greater queries	LeetCode #739 Daily Temperatures
Monotonic Deque	Maintain sorted deque for window extrema	LeetCode #239 Sliding Window Max
Frequency Map	Count occurrences, group by property	LeetCode #49 Group Anagrams
Two-Sum with Hash Map	Store complements for O(1) lookup	LeetCode #1 Two Sum
Min-Heap Size K	Track top-k largest with min-heap	LeetCode #215 Kth Largest

You must be able to reproduce this table from memory. The test: close the document, open a blank text editor, and reproduce it in under 5 minutes.

Acceptance criteria: Can reproduce from memory. Can explain each pattern’s time complexity improvement over the brute-force approach.

Estimated time: 2–3 hours in Week 12 to write; ongoing to memorize.

---

Week-by-Week Micro-Schedule (Weeks 6–12)

Week 6 (Sep 8–14): Arrays and Strings

• Study 01_arrays_and_strings.md in full (2h)

• Solve array warmup problems: LC #26, #121, #283 (1.5h)

• Solve two-pointer problems: LC #11, #15 (2h)

• Begin Project 1: Dynamic Array implementation (1.5h)

Week 7 (Sep 15–21): Linked Lists

• Study 02_linked_lists.md in full (2h)

• Solve LC #206, #21, #141 (1.5h)

• Solve LC #142, #19 (2h)

• Continue Project 1: Doubly Linked List implementation (2h)

Week 8 (Sep 22–28): Stacks, Queues, and Monotonic Structures

• Study 03_stacks_and_queues.md in full (2h)

• Solve LC #20, #155, #739 (1.5h)

• Solve LC #150, #239 (2h)

• Continue Project 1: Stack + Queue implementations (2h)

Week 9 (Sep 29 – Oct 5): Hash Tables

• Study 04_hash_tables.md in full (2h)

• Solve LC #242, #49, #128, #347 (2.5h)

• Continue Project 1: HashMap with chaining implementation (3h)

Week 10 (Oct 6–12): Heaps and Priority Queues

• Study 05_heaps_and_priority_queues.md in full (2h)

• Solve LC #703, #215, #1046, #373, #23 (3h)

• Continue Project 1: Min-Heap implementation (2h)

• Finalize Project 1: tests + clean pass (2h)

Week 11 (Oct 13–17): Hard Problems + Sprint Completion

• Finish any remaining 30-problem sprint problems (4h)

• Attempt LC #84, #41, #25 (hard problems — allocate more time per problem) (3h)

• Review problems you used hints on: write 3-sentence insights (1h)

Week 12 (Oct 18): Exit Gate

• Write Project 3 Pattern Taxonomy from scratch (1.5h)

• Self-test: implement HashMap from scratch with no reference. Pass/fail. (1.5h)

• Review exit criteria checklist — honestly mark each item

• If any criteria are unmet: do not advance. Spend 1 more week on the gaps.

---

Note on Advancing

Delay > Debt. Spending one more week on Phase 1 to lock in the fundamentals is a better investment than spending three weeks in Phase 2 with shaky foundations. The problems in Phase 2 and beyond are harder, the feedback loops are longer, and debugging a misconception about linked lists while also learning divide-and-conquer is miserable. If you’re 80% done with the criteria at week 12, finish the 20% before moving on. No exceptions.

---

Return to README.md · Next: ../03_sorting_and_searching/README.md