Chapter 18: Common Patterns & Problem-Solving Strategy

18.1

Toptal Coding Test Format

Understand the exact format, evaluation criteria, and scoring methodology. 90 minutes. 3 problems. Precision matters.

Test Structure

Aspect	Details
Duration	90 minutes total
Problems	3 (typically Easy, Medium, Hard)
Environment	Web-based IDE with syntax highlighting
Languages	C#, Java, Python, JavaScript, Go, C++, Rust
Test Cases	Visible + Hidden (no access to hidden until submit)
Resubmission	Unlimited (no penalty)
Compilation	Real-time error feedback

Evaluation Rubric (Weighted)

Criterion	Weight	What Reviewers Check
Correctness	40%	Passes all test cases (visible & hidden). Handles edge cases. Logic is sound.
Efficiency	30%	Time complexity optimal or near-optimal. Space usage reasonable. No TLE (Time Limit Exceeded).
Edge Cases	20%	Empty inputs, single element, negatives, overflow, unicode, duplicates, off-by-one. All handled explicitly.
Code Quality	10%	Clear naming, no magic numbers, helper methods, readable structure, proper formatting.

Time Strategy

Easy (15 min): 2min read + 5min understand + 8min code = guarantee 100%
Medium (25 min): 3min read + 10min plan + 15min code + 2min test = target 90%
Hard (50 min): 5min read + 15min plan + 25min code + 5min test = target 60%+
Buffer (5 min): Review, fix syntax, handle new edge cases

Hidden Test Case Patterns

Toptal's hidden tests typically check:

Empty arrays/strings, null values
Single element (n=1)
Maximum constraints (n=10^6 or 10^9, testing limits)
All duplicates
All negatives
Sorted/reverse sorted
Integer overflow scenarios (near int.MaxValue)
Unicode and special characters
Off-by-one boundary conditions

⚠️

Critical: Always solve Easy first to lock in base score. Never spend >40 min on Hard if Medium is unsolved.

18.2

UMPIRE Framework

A six-step methodology that eliminates guessing and reduces careless errors. Follow this for every single problem.

1

Understand — Read problem twice. Identify inputs, outputs, constraints. Ask yourself: What is being asked exactly? Write down 2-3 examples by hand.

2

Match — Recognize the pattern. Look at signal words. Is this two-pointers? Hash map? DP? Trees? Instantly classify into a pattern family.

3

Plan — Write pseudocode. Decide on algorithm. State target time/space complexity. Outline steps without touching the IDE.

4

Implement — Code cleanly. Add brief comments. Use meaningful variable names. Compile and fix syntax errors immediately.

5

Review — Walk through your code line-by-line with example inputs. Spot logical errors. Check boundary conditions. Verify data types.

6

Evaluate — Test with edge cases. Confirm time/space complexity. Run all visible test cases. Submit with confidence.

Worked Example: Two Sum (LeetCode #1)

Problem: Given array of integers and target sum, return indices of two numbers that add to target. Use each element at most once.

Understand

Input: nums=[2,7,11,15], target=9. Output: [0,1] (nums[0]+nums[1]=9). Exactly one solution guaranteed. O(n) time preferred.

Match

Signal: "find pair with property". Hash map pattern. Store num→index, then for each num check if complement exists.

Plan

Iterate through array. For each num, check if (target-num) in dict. If yes, return both indices. Else add num to dict. Time O(n), Space O(n).

Implement

Create Dictionary<int,int>. Loop with index. Check ContainsKey before insertion to handle duplicates.

C#

public int[] TwoSum(int[] nums, int target)
{
    var map = new Dictionary<int, int>();
    
    for (int i = 0; i < nums.Length; i++)
    {
        int complement = target - nums[i];
        if (map.ContainsKey(complement))
            return new int[] { map[complement], i };
        
        if (!map.ContainsKey(nums[i]))
            map[nums[i]] = i;
    }
    return new int[] { };
}

Review

Check complement before adding (correct order). Handle duplicates with ContainsKey check. Clear variable names. No off-by-one errors.

Evaluate

Time: O(n) single pass. Space: O(n) for dict. Optimal for this problem. Ready to submit.

18.3

Pattern Recognition Master Guide (30+ Patterns)

Instantly recognize problem types by signal words. This table is your cheat sheet.

Pattern	Signal Words	Technique	Why It Works	LC Examples	Chapter
Two Pointers	Sorted, pair, target, reverse, meeting	Converging pointers from ends	Exploit ordering to eliminate binary search	#1, #15, #11, #167	Ch. 5
Sliding Window	Subarray, substring, longest, shortest, contiguous	Expand/contract window with 2 pointers	Each element enters/exits once = O(n)	#3, #76, #209, #424	Ch. 6
Hash Map	Duplicate, frequency, count, anagram, complement	Map value→count or value→index	O(1) lookup replaces O(n) search	#1, #49, #242, #347	Ch. 7
Prefix Sum	Subarray sum, range, cumulative, zero-sum	Precompute cumulative sums	Range sum O(n) → O(1)	#303, #560, #724	Ch. 9
Binary Search	Sorted, find position, log complexity, rotation	Divide search space by 2	Eliminate half remaining options each step	#704, #35, #74, #153	Ch. 8
Monotonic Stack	Next greater, previous smaller, trapping, histogram	Push/pop to maintain monotonic order	Each element pushed/popped once = O(n)	#20, #155, #739, #84	Ch. 10
BFS / Queue	Shortest path, level order, distance, matrix layers	Layer-by-layer exploration with queue	Guarantees shortest path in unweighted graph	#102, #542, #994, #1091	Ch. 13
DFS / Recursion	Traversal, path, permutation, reachability, connected	Recursive or stack-based graph traversal	Explores all paths; backtracking prunes branches	#104, #200, #332, #46	Ch. 12
Fast-Slow Pointers	Cycle, middle, kth from end, circular list	Two pointers: one 2x speed	Floyd's algorithm: meeting point indicates cycle	#141, #142, #876, #202	Ch. 11
Tree Recursion	Depth, path, LCA, balanced, diameter, subtree sum	Recurse on left/right, combine results	Leverage subtree solutions for superproblems	#104, #110, #236, #257	Ch. 12
BST Property	Search tree, validate, in-order, kth, successor	In-order → sorted; use min/max bounds	BST property eliminates half of tree	#98, #230, #700, #235	Ch. 12
Union-Find	Connected, components, cycle, grouping, parent	Maintain connected components via parent pointers	O(α(n)) amortized for find/union	#684, #547, #323, #1319	Ch. 14
Topological Sort	Prerequisite, dependency, DAG, ordering, course	Kahn (BFS) or DFS for dependency order	Detects cycles; ensures deps processed first	#207, #210, #269, #310	Ch. 14
Dijkstra	Shortest path, positive weights, weighted graph	Priority queue: always process min distance	Greedy: shortest path to node is final	#743, #787, #882, #1334	Ch. 14
0/1 DP	Climb stairs, house robber, partition, max	dp[i]=best solution for subproblem i	Avoid recalculating overlapping subproblems	#70, #198, #322, #416	Ch. 15
Unbounded DP	Coin change, unlimited, target sum, combinations	Item can be used multiple times	Recurrence: dp[i] uses all smaller j	#322, #518, #494, #377	Ch. 15
2D DP	Edit distance, unique paths, max square, triangle	dp[i][j]=solution for subgrid (i,j)	2D state space: explore all cell combinations	#64, #62, #97, #1143	Ch. 15
Knapsack	Weight capacity, subset sum, target, bounded	dp[i][w]=max value with i items, weight w	Item taken or skipped; optimize weight	#416, #1049, #474, #494	Ch. 15
Greedy	Interval, activity, max profit, minimum cost, sort	Make locally optimal choice at each step	Works when greedy leads to global optimum	#435, #452, #945, #881	Ch. 16
Backtracking	Permutation, combination, subset, N-Queens, Sudoku	Explore all possibilities; prune invalid branches	Systematically exhaust with early termination	#46, #47, #78, #51	Ch. 17
Bit Manipulation	Power of 2, bit count, XOR swap, subset, mask	AND/OR/XOR/shift for compact operations	O(1) bit ops vs. O(n) array ops	#191, #231, #136, #268	Ch. 4
Math/Number Theory	Palindrome, prime, GCD, Fibonacci, modular, digit	Apply mathematical insight instead of brute force	Skip redundant computation via math property	#204, #172, #69, #1401	Ch. 3
Heap / Priority Queue	Kth largest, median, top K, frequent, min/max	Min/Max heap for quick access to extreme	O(log n) insertion; O(1) peak access	#215, #295, #347, #313	Ch. 10
Graph Coloring	Bipartite, conflict, map coloring, scheduling	Assign colors: no adjacent same color	BFS/DFS detects odd cycles; 2 colors = bipartite	#785, #1042, #886, #210	Ch. 13
Interval Merging	Merge overlapping, non-overlapping, insert, schedule	Sort by start; merge if overlapping	Linear scan post-sort identifies all overlaps	#56, #57, #435, #986	Ch. 6
Matrix Traversal	Spiral, rotate, search sorted, spiral order	Row-major, spiral, or direction-change iteration	Layer-by-layer approach handles complexity	#54, #48, #240, #1572	Ch. 6
Simulation	State machine, game logic, step-by-step, rules	Implement rules directly; iterate state	Sometimes no pattern; just simulate correctly	#54, #67, #1306, #1849	Ch. 2
Trie	Word search, autocomplete, prefix, dictionary	Tree of characters; each node has children	O(m) word search vs. O(m log n) hash	#208, #211, #212, #1268	Ch. 10
Segment Tree/Fenwick	Range query, point update, sum rectangle	Build tree for fast range aggregation	O(log n) query/update vs. O(n) naive	#307, #308, #1157, #1606	Ch. 10

How to Use This Table

Read problem and highlight keywords
Match keywords to "Signal Words" column
Find the pattern row
Study the "Technique" and "Why It Works" columns
Solve the "LC Examples" problems in that pattern
Reference the chapter for detailed explanation

18.4

Complexity Target Guide

Match input size to target complexity class. This prevents TLE and guides algorithm selection.

Input Size (n)	Typical Operations	Target Complexity	Algorithm Examples
n ≤ 10	~10M ops	O(n!) or O(n^6)	Brute force all permutations, full backtracking
n ≤ 20	~1M ops	O(2^n) or O(n^5)	Bitmask DP, subset enumeration, exponential
n ≤ 500	~250K ops	O(n^3) or O(n^2 log n)	Floyd-Warshall, DP with 2D state, cubic iteration
n ≤ 10^4	~100M ops	O(n^2)	Nested loops, bubble sort, all pairs
n ≤ 10^5	~1B ops	O(n log n)	Merge sort, heap sort, binary search variants
n ≤ 10^6	~1B ops	O(n) or O(n log n)	Single pass, hash map, sorting, linear scan
n ≤ 10^8	~100M ops	O(n) only	Must be linear; very tight constants required
n > 10^8	Varies	O(log n)	Binary search, bit operations, math only

Time Budget Examples

n=10^4: O(n²)=10^8 ops ≈ 1 second (safe). O(n³)=10^12 (TLE).
n=10^5: O(n log n)=1.7×10^6 ops ≈ 10ms (safe). O(n²)=10^10 (TLE).
n=10^6: O(n)=10^6 ops ≈ 1ms (safe). O(n log n)=2×10^7 (tight, risky).

ℹ️

Rule of Thumb: 10^8-10^9 simple operations per second. If uncertain, aim one complexity class better than minimum.

18.5

C# Tips for Competitive Coding

C#-specific tricks to write faster, safer, cleaner code in contests.

Essential Data Structures & Methods

Feature	Usage	Time/Space
Dictionary<K,V>	Hash map for O(1) lookup	O(1) avg, O(n) worst
HashSet<T>	Fast membership testing, deduplication	O(1) avg Add/Contains
List<T>	Dynamic array, sorted lists	O(n) insertion, O(1) access
Queue<T>	BFS, level-order traversal	O(1) Enqueue/Dequeue
Stack<T>	DFS, monotonic stack, parsing	O(1) Push/Pop
PriorityQueue<T> (C# 10+)	Min/Max heap, Dijkstra	O(log n) Enqueue/Dequeue
SortedDictionary<K,V>	Ordered key access, range queries	O(log n) operations
StringBuilder	String concatenation (never use + in loop)	O(n) for n appends vs O(n²)
Array.Sort(T[], IComparer)	Custom sort order with comparers	O(n log n)

Common Patterns & Gotchas

1. StringBuilder for String Building

C# (Bad)

string result = "";
for (int i = 0; i < 1000; i++)
    result += i.ToString(); // O(n²) string copying!

C# (Good)

var sb = new StringBuilder();
for (int i = 0; i < 1000; i++)
    sb.Append(i); // O(n)
string result = sb.ToString();

2. Dictionary Patterns

C#

// Count frequencies
var freq = new Dictionary<int, int>();
foreach (int num in nums)
    freq[num] = freq.GetValueOrDefault(num, 0) + 1;

// Or use TryGetValue for safety
if (freq.TryGetValue(key, out int val))
    // Use val safely

3. PriorityQueue (C# 10+)

C#

var minHeap = new PriorityQueue<int, int>();
minHeap.Enqueue(5, 5); // value, priority
minHeap.Enqueue(3, 3);
int min = minHeap.Dequeue(); // 3

// For max heap, negate priorities
var maxHeap = new PriorityQueue<int, int>();
maxHeap.Enqueue(5, -5); // negate

4. LINQ Gotchas

LINQ is lazy-evaluated. Call .ToList() to materialize.
OrderBy() is O(n log n); don't call multiple times on result.
Count() on IEnumerable is O(n); pre-materialize for multiple uses.
.FirstOrDefault() is safer than .First() for empty sequences.

5. Span<T> for Performance

C#

// Use Span<T> for zero-copy slicing
int[] arr = new int[] { 1, 2, 3, 4, 5 };
Span<int> slice = arr.AsSpan(1, 3); // No allocation

6. Integer Overflow Safety

C#

// Check bounds before arithmetic
if (a > int.MaxValue - b) // would overflow

// Use long for large intermediate values
long product = (long)a * b;

7. Array.Sort with Custom Comparer

C#

// Sort by custom logic
Array.Sort(intervals, (a, b) => a[0].CompareTo(b[0]));

// Or reverse order
Array.Sort(nums, (a, b) => b.CompareTo(a));

8. Common Math Methods

C#

Math.Abs(x);
Math.Max(a, b); Math.Min(a, b);
Math.Pow(base, exp);
Math.Sqrt(x);
Math.Floor(x); Math.Ceiling(x);
x % m; // modulo

18.6

Edge Cases Master Checklist

These account for 20% of your score. Missing one means wrong answer on hidden tests.

Category	Examples to Test	Code Implications
Empty Input	[], "", null, 0 length	Check array bounds before access. Handle null gracefully.
Single Element	n=1, one node, one char	Loops should handle i=0 case. Base case matters.
Duplicates	All same value, freq=n	Dict handling, set dedup, comparison logic.
Sorted/Reverse	Ascending, descending, already sorted	Early exit conditions, comparison directions.
Negatives	All negative, mixed signs, -1	Abs(), sign handling, comparison logic.
Zero	Zeros in array, divide by zero	Check denominator != 0. Handle x=0 specially.
Integer Overflow	int.MaxValue, near limits	Use long, check before arithmetic, modulo.
Large Input	n=10^6, stress memory	O(n²) becomes TLE. Use efficient structures.
Off-by-One	Boundary indices, fencepost	Loop conditions: i < n vs i <= n. Array indices.
Unicode/Special Chars	UTF-8, emoji, accents, newlines	String length vs byte length. Char encoding.
Floating Point	NaN, Infinity, rounding	Equality checks use epsilon. Integer conversion issues.
Null/Undefined	null references, uninitialized	Null checks. Dictionary.TryGetValue not direct access.

Pre-Submission Edge Case Routine

Empty input: Does it crash or return correctly?
Single element: Does the loop handle n=1?
All same value: Does deduplication work?
Boundary values: int.MaxValue, 0, -1?
Off-by-one: Loop indices correct? Array access safe?
Large input: Would it TLE or MLE?

18.7

Code Quality & Refactoring

The final 10% of your score. Clean code reads like prose. Make reviewers happy.

Naming Conventions (C#)

Methods: PascalCase. TwoSum, IsValid, BuildGraph
Local vars: camelCase. leftPointer, freqMap, result
Constants: UPPER_SNAKE_CASE or PascalCase. MAX_SIZE or MaxSize
Booleans: Prefix with "is", "has", "can". isValid, hasNext, canReach

Code Quality Principles

Avoid Magic Numbers

if (i % 2 == 0) is unclear. Better: const int MOD = 2; if (i % MOD == 0). Or comment: // Check if even

Helper Methods

Complex logic in separate methods. IsValid(), GetNeighbors(), Swap() make main logic readable.

Meaningful Comments

Comment the WHY, not the WHAT. // Greedy: always pick min cost option is better than // Loop through array

Consistent Formatting

Proper indentation, spacing around operators, blank lines between logical blocks. Use IDE's formatter.

Before/After Refactoring Example

BEFORE (Poor Quality):

C#

public bool isvalid(string s)
{
    var st = new Stack<char>();
    for(int i=0;i<s.Length;i++)
    {
        char c=s[i];
        if(c=='('||c=='{'||c=='[')st.Push(c);
        else
        {
            if(st.Count==0)return false;
            char t=st.Pop();
            if(!(c==')'&&t=='('||c=='}'&&t=='{'||c==']'&&t=='['))return false;
        }
    }
    return st.Count==0;
}

AFTER (Good Quality):

C#

public bool IsValid(string s)
{
    var stack = new Stack<char>();
    
    foreach (char c in s)
    {
        if (IsOpeningBracket(c))
        {
            stack.Push(c);
        }
        else if (IsClosingBracket(c))
        {
            if (stack.Count == 0 || !IsMatching(stack.Pop(), c))
                return false;
        }
    }
    
    return stack.Count == 0;
}

private bool IsOpeningBracket(char c) => c == '(' || c == '{' || c == '[';

private bool IsClosingBracket(char c) => c == ')' || c == '}' || c == ']';

private bool IsMatching(char open, char close)
    => (open == '(' && close == ')') ||
       (open == '{' && close == '}') ||
       (open == '[' && close == ']');

Quality Checklist

Variable names are clear (not a, b, x unless mathematical)
Methods do one thing (helper methods extract complexity)
No magic numbers (use const or explain in comments)
Proper indentation and spacing
Comments explain WHY, not WHAT
Error/edge cases handled explicitly, not ignored

18.8

Problem	LC#	Difficulty	Pattern	Chapter
Two Sum	#1	Easy	Hash Map	7
Best Time to Buy & Sell Stock	#121	Easy	Dynamic Programming	15
Contains Duplicate	#217	Easy	Hash Set	7
3Sum	#15	Medium	Two Pointers	5
Product of Array Except Self	#238	Medium	Prefix Sum	9
Merge Intervals	#56	Medium	Interval Merging	6
Search in Rotated Sorted Array	#33	Medium	Binary Search	8
Maximum Subarray	#53	Medium	Dynamic Programming	15
Spiral Matrix	#54	Medium	Matrix Traversal	6
Set Matrix Zeroes	#73	Medium	In-Place Modification	2
Rotate Image	#48	Medium	Matrix Rotation	6
First Missing Positive	#41	Hard	Array Indexing	2

Problem	LC#	Difficulty	Pattern	Chapter
Valid Parentheses	#20	Easy	Stack	10
Reverse String	#344	Easy	Two Pointers	5
Longest Substring Without Repeating Chars	#3	Medium	Sliding Window	6
Group Anagrams	#49	Medium	Hash Map	7
Valid Palindrome	#125	Medium	Two Pointers	5
Longest Palindromic Substring	#5	Medium	Dynamic Programming	15
Word Ladder	#127	Medium	BFS	13
Edit Distance	#72	Hard	2D DP	15
Word Break II	#140	Hard	Backtracking DP	17
Regular Expression Matching	#10	Hard	2D DP	15

Problem	LC#	Difficulty	Pattern	Chapter
Reverse Linked List	#206	Easy	Linked List Manipulation	11
Merge Two Sorted Lists	#21	Easy	Two Pointers	5
Linked List Cycle	#141	Easy	Fast-Slow Pointers	11
Add Two Numbers	#2	Medium	Linked List Traversal	11
Remove Nth Node From End	#19	Medium	Two Pointers	5
Reorder List	#143	Medium	Fast-Slow + Reverse	11
Copy List with Random Pointer	#138	Medium	Hash Map	7
LRU Cache	#146	Hard	Hash Map + Linked List	11

Problem	LC#	Difficulty	Pattern	Chapter
Binary Tree Inorder Traversal	#94	Easy	Tree Traversal	12
Invert Binary Tree	#226	Easy	Tree Recursion	12
Same Tree	#100	Easy	Tree Comparison	12
Balanced Binary Tree	#110	Easy	Tree Recursion	12
Lowest Common Ancestor of BST	#235	Easy	BST Property	12
Binary Tree Level Order	#102	Medium	BFS	13
Binary Tree Zigzag Traversal	#103	Medium	BFS	13
Lowest Common Ancestor	#236	Medium	Tree Recursion	12
Validate BST	#98	Medium	BST Property	12
Path Sum II	#113	Medium	Backtracking	17
Number of Islands	#200	Medium	DFS/BFS	13
Clone Graph	#133	Medium	Graph Traversal	13
Course Schedule	#207	Medium	Topological Sort	14
Binary Tree Maximum Path Sum	#124	Hard	Tree Recursion	12
Alien Dictionary	#269	Hard	Topological Sort	14

Problem	LC#	Difficulty	Pattern	Chapter
Climbing Stairs	#70	Easy	0/1 DP	15
House Robber	#198	Medium	0/1 DP	15
Coin Change	#322	Medium	Unbounded DP	15
Unique Paths	#62	Medium	2D DP	15
Partition Equal Subset Sum	#416	Medium	Knapsack	15
Word Break	#139	Medium	1D DP	15
Longest Increasing Subsequence	#300	Medium	1D DP	15
Target Sum	#494	Medium	Knapsack	15
Distinct Subsequences	#115	Hard	2D DP	15
Interleaving String	#97	Hard	2D DP	15
Best Time to Buy Stock IV	#188	Hard	DP with State	15
Longest Substring w/ At Most K Distinct	#340	Hard	Sliding Window DP	6

Problem	LC#	Difficulty	Pattern	Chapter
Trapping Rain Water	#42	Medium	Monotonic Stack	10
Largest Rectangle in Histogram	#84	Medium	Monotonic Stack	10
Kth Largest Element	#215	Medium	Heap/Quickselect	10
Top K Frequent Elements	#347	Medium	Heap	10
Find Median from Data Stream	#295	Hard	Heap	10
Meeting Rooms II	#253	Medium	Greedy Sorting	16
Interval Scheduling Maximization	#452	Medium	Greedy	16
Two Sum III - Data Structure Design	#170	Medium	Hash Map	7
Sort Colors	#75	Medium	Two Pointers	5
Minimum Window Substring	#76	Hard	Sliding Window	6
Permutations	#46	Medium	Backtracking	17
Combinations	#77	Medium	Backtracking	17
Subsets	#78	Medium	Backtracking	17
Letter Combinations	#17	Medium	Backtracking	17
N-Queens	#51	Hard	Backtracking	17
Sudoku Solver	#37	Hard	Backtracking	17
Surrounded Regions	#130	Medium	DFS/BFS	13
Accounts Merge	#721	Medium	Union-Find	14

8-Week (60-Day) Study Plan

You have 60 days — use them wisely. This 8-week plan at ~2 hrs/day gives you 120 total hours of deep, structured practice. That's 3x what most candidates invest.

Week 1: Foundations & Big O (Days 1–7)

Goal: Master Big O, arrays, strings, prefix sums. Solve all easy Codility problems. 100% on Codility Lessons 1-5.

Mon: Big O & Complexity (Ch 1). Practice estimating complexity from code snippets. (2 hrs)

Tue: Arrays & Strings (Ch 2). C# arrays, List, StringBuilder. Codility Lessons 1-2. (2 hrs)

Wed: Prefix Sums (Ch 19). Codility Lesson 5. Solve: PassingCars, GenomicRangeQuery, MinAvgTwoSlice. (2 hrs)

Thu: Counting Elements. Codility Lesson 3-4. Solve: MissingInteger, MaxCounters, PermCheck. (2 hrs)

Fri: Practice: Solve 5 easy problems timed (10 min each). Review edge cases. (2 hrs)

Sat: Revisit any problems not at 100%. Write prefix sum template from memory 3 times. (3 hrs)

Sun: Light review. Rest.

Week 2–3: Core Patterns (Days 8–21)

Goal: Master hash maps, two pointers, sliding window, binary search, stacks. Take Mock Test 1.

Week 2 Mon-Fri: Hash Maps (Ch 5), Two Pointers & Sliding Window (Ch 15), Binary Search (Ch 10). 2 problems/day. (2 hrs/day)

Week 2 Sat: Sorting algorithms (Ch 9). Codility Lesson 6. Problems: Distinct, Triangle, NumberOfDiscIntersections. (3 hrs)

Week 3 Mon-Fri: Stacks & Queues (Ch 4). Monotonic stack. Problems: Brackets, Fish, StoneWall, Largest Rectangle, Daily Temperatures. (2 hrs/day)

Week 3 Sat: Review all patterns. Re-solve 5 hardest problems from Weeks 2-3. (3 hrs)

Week 3 Sun: MOCK TEST 1 (90 min timed). Score target: 200+/300. (3 hrs)

Week 4–5: Data Structures Deep Dive (Days 22–35)

Goal: Master trees, graphs, heaps, linked lists. Complete ALL 17 Codility lessons at 100%. Take Mock Test 2.

Week 4 Mon-Wed: Linked Lists (Ch 3). Problems: Reverse, Merge, Cycle Detection, Palindrome. (2 hrs/day)

Week 4 Thu-Sat: Trees & BST (Ch 6). Traversals, Validate BST, LCA, Path Sum, Kth Smallest. (2-3 hrs/day)

Week 5 Mon-Wed: Graphs (Ch 8). BFS, DFS, Dijkstra. Problems: Number of Islands, Course Schedule, Word Ladder. (2 hrs/day)

Week 5 Thu-Fri: Heaps (Ch 7). PriorityQueue. Codility Lessons 8-17 (complete ALL). (2 hrs/day)

Week 5 Sat: Verify ALL 17 Codility lessons are 100%. Fix any that aren't. (3 hrs)

Week 5 Sun: MOCK TEST 2 (90 min timed). Score target: 230+/300. (3 hrs)

Week 6–7: Algorithm Paradigms (Days 36–49)

Goal: Master DP, greedy, backtracking. Solve 50+ medium/hard problems. Take Mock Test 3.

Week 6 Mon-Wed: Dynamic Programming (Ch 12). 1D DP: Climbing Stairs, House Robber, Coin Change, LIS. (2 hrs/day)

Week 6 Thu-Fri: 2D DP: Edit Distance, LCS, Knapsack, Unique Paths. Draw DP tables by hand. (2 hrs/day)

Week 6 Sat: DP Advanced: Stock with Cooldown, Burst Balloons concept, bitmask intro. (3 hrs)

Week 7 Mon-Tue: Greedy (Ch 13): Jump Game, Gas Station, Task Scheduler, Partition Labels. (2 hrs/day)

Week 7 Wed-Thu: Backtracking (Ch 11): Subsets, Permutations, Combination Sum, N-Queens. (2 hrs/day)

Week 7 Fri: Strings, Bit Manipulation, Intervals — solve remaining problems. (2 hrs)

Week 7 Sat: Hard Problem Day: 3 hard problems (1 DP, 1 graph, 1 design). 40 min each. (3 hrs)

Week 7 Sun: MOCK TEST 3 (90 min timed). Score target: 250+/300. (3 hrs)

Week 8+: Polish, Mock Tests & All 4 Rounds (Days 50–60)

Goal: Score 260+/300 consistently. Prepare for all 4 Toptal rounds. Build supreme confidence.

Day 50-51: Weak point audit. Identify 2 weakest categories. Drill those exclusively. (2 hrs/day)

Day 52-53: Speed drills: 6 easy in 60 min, 3 mediums in 75 min. Edge case mastery. (2 hrs/day)

Day 54: Random problem mix from LeetCode — no category chosen. Practice pattern recognition. (2 hrs)

Day 55: MOCK TEST 4 (full simulation, no breaks). Target: 270+/300. (3 hrs)

Day 56: Live Coding prep (REACTO method). Practice talking through solutions aloud. (3 hrs)

Day 57: Take-Home Project prep. Set up .NET template with Clean Architecture, DI, tests. (2 hrs)

Day 58: Communication Round prep. Practice answering common questions aloud. (2 hrs)

Day 59: FINAL MOCK TEST. Dress rehearsal. Score target: 260+/300. (2 hrs)

Day 60: Light review of cheatsheet and golden rules. No new problems. Sleep early. You're ready.

✓

Pro Tip: If stuck on a problem >20 min, read solution/hint, understand, then retry without looking. Solve same problem 3 times on different days = mastery. With 60 days you have time for proper spaced repetition.

18.10

Mock Interview Tips & Time Management

How to think under pressure, communicate, and recover. Master this and you'll ace the real test.

Time Allocation (90 Minutes Total)

Easy: 2min read + 5min plan + 8min code + 2min test = 17 min. Target: 100%
Medium: 3min read + 10min plan + 18min code + 4min test = 35 min. Target: 85%+
Hard: 4min read + 15min plan + 25min code + 5min test = 49 min. Target: 60%+
Buffer: 5-10 min for review, fixes, edge case testing

Communication Template (Thinking Aloud)

ℹ️

Setup: "Let me make sure I understand the problem. Input: array of integers. Output: two indices. Constraint: use each element once."

ℹ️

Pattern Match: "This looks like a classic hash map problem — find pair with property."

ℹ️

Approach: "My approach: iterate through array, for each element check if complement exists in map. Time O(n), Space O(n)."

When You Get Stuck

Minute 1-5: Reread

Read the problem 2x. Highlight key words. Ask yourself what constraints change the problem.

Minute 6-10: Simplify

Solve the easiest version. E.g., if "subarray", start with "single element". Build up.

Minute 11-15: Pattern Match

Think of 3 similar problems you've solved. What patterns apply? Hash map, two pointers, DP?

Minute 16+: Move On

If still stuck, move to next problem. Partial credit >zero. Try again with fresh eyes later.

Before Final Submission

Walk through code line-by-line with example
Check: empty input, single element, large input
Check: off-by-one in loops and array access
Check: integer overflow for large values
Verify: time complexity meets target
Verify: no syntax errors (IDE shows red squiggles?)
Format: proper indentation, clear variable names

Pressure Management

Calm down: First 30 seconds, take a breath. You've practiced this.
Easy wins: Solve Easy first, lock in base score. Confidence builder.
Time awareness: Check time every 15 min. Adjust strategy if behind.
Don't panic: Hard problem unsolved? That's OK. Partial credit exists. Keep moving.
Code quality: Last 5 min: review naming, comments, formatting. Reviewers notice.

18.11

Common Mistakes to Avoid

Learn from others' failures. These 20 mistakes cost interview offers.

Mistake	Why It Fails	Fix
Skipping edge cases	Hidden tests catch empty, single element, overflow	Always test: [], [1], max values
Off-by-one errors	Loop conditions wrong; access out of bounds	Trace: i < n vs i <= n. Check indices.
Modifying input	Problem says don't modify; you did. Wrong answer.	Use auxiliary arrays/maps instead.
Integer overflow	a + b overflows to negative; logic breaks	Use long, check before arithmetic.
Wrong complexity	O(n²) on n=10^5 = TLE	Match input size to complexity target.
Forgetting to return	Function returns null; crashes	Check all paths return a value.
Mutating shared state	If multiple test cases, leftover data breaks next test	Initialize fresh variables each run.
String concatenation in loops	O(n²) copying; TLE	Use StringBuilder.
Assuming sorted input	Problem never says sorted; you assume it	Reread constraints. Don't assume.
Dictionary access without check	KeyNotFoundException when key missing	Use TryGetValue or GetValueOrDefault.
Modifying collection during iteration	IndexOutOfRangeException or skip elements	Build new list or iterate over copy.
Floating-point equality	0.1 + 0.2 != 0.3 due to precision	Use epsilon: Math.Abs(a - b) < 1e-9
Not null-checking	NullReferenceException on null input	Check params: if (s == null) return ...
Wrong complexity analysis	"It's O(n)!" but actually O(n²)"	Count nested loops, recursion depth.
Not testing with examples	Code passes visible tests, fails hidden	Always run all provided examples first.
Unclear variable names	Reviewers dock points for readability	Use descriptive names: leftPointer, freqMap
Magic numbers	"What does 2 mean?" Code unclear	const int MOD = 2; or comment why.
No comments on complex logic	Reviewers can't follow intent	Comment the WHY: "Greedy: pick min..."
Inefficient brute force	Correct but O(n³); TLE	Optimize to O(n log n) or O(n).
Forgetting base case in recursion	Stack overflow or infinite recursion	Always define: if (n == 0) return ...

⚠️

Critical Mistakes: Off-by-one (50% of bugs), integer overflow (10%), wrong complexity (15%), edge cases (20%). Focus on these.

18.12

Quick Reference Cheat Sheet

One-page summary of critical facts. Print and review 1 hr before test.

Data Structure Operations Complexity

Data Structure	Access	Search	Insert	Delete	Space
Array	O(1)	O(n)	O(n)	O(n)	O(n)
Hash Table	O(1)	O(1)	O(1)	O(1)	O(n)
Linked List	O(n)	O(n)	O(1)	O(1)	O(n)
Stack	O(n)	O(n)	O(1)	O(1)	O(n)
Queue	O(n)	O(n)	O(1)	O(1)	O(n)
Binary Tree	O(log n)	O(log n)	O(log n)	O(log n)	O(n)
Heap	O(1)	O(n)	O(log n)	O(log n)	O(n)
Graph (Adjacency List)	—	O(V+E)	O(1)	O(V)	O(V+E)
Trie	—	O(m)	O(m)	O(m)	O(ALPHABET_SIZE * N)

Algorithm Decision Tree

Is the input sorted?

YES → Binary Search, Two Pointers, Merge operations
NO → Hash Map, Sort first (O(n log n)), then algorithm

Is it a graph/tree problem?

YES → BFS (shortest path), DFS (all paths), Topological Sort (DAG), Dijkstra (weights)

Can you build optimal solution from subproblems?

YES → Dynamic Programming (memoization or tabulation)

Is it a string/substring problem?

Longest/Shortest → Sliding Window. Anagram/Frequency → Hash Map. Pattern Match → DP/KMP.

Is it an optimization problem (max/min)?

Greedy works? → Greedy. Otherwise → DP. Need ranking/top-k? → Heap.

Big O Time Complexity Reference

O(1) < O(log n) < O(√n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)

Input Size → Target Complexity Quick Map

n ≤ 10 → O(n!) or O(n⁶)
n ≤ 20 → O(2ⁿ) or O(n⁵)
n ≤ 500 → O(n³) or O(n² log n)
n ≤ 10⁴ → O(n²)
n ≤ 10⁶ → O(n log n) or O(n)
n > 10⁶ → O(n) only

UMPIRE Framework Summary

Understand — Read 2x, write examples
Match — Recognize pattern type
Plan — Write pseudocode, complexity
Implement — Code cleanly
Review — Walk-through with example
Evaluate — Test edges, confirm complexity

C# Essentials

Dictionary<K,V> for hash maps. .TryGetValue() to avoid crashes.
HashSet<T> for membership. .Contains() O(1).
PriorityQueue<T, P> for heaps. Negate priority for max heap.
StringBuilder for string building. Never += in loops.
Stack<T> for DFS/monotonic. Queue<T> for BFS.
int.MaxValue for overflow checks. Use long for large arithmetic.

Final Checklist (5 Min Before Submit)

✓ Code compiles, no red squiggles
✓ Tested with all visible examples
✓ Edge cases: empty, single, max values
✓ No off-by-one errors (loop conditions)
✓ No integer overflow (use long if needed)
✓ Time complexity on target
✓ Variable names clear, comments on complex logic
✓ No magic numbers, proper formatting

✓

Final Words: You've prepared well. Trust your training. Follow UMPIRE. Manage time. Think clearly. You will ace this.

Bonus

Advanced Problem-Solving Techniques

Beyond the basics: techniques used by top performers in competitive programming.

Memoization vs. Tabulation

Memoization (Top-Down DP): Start from the problem and recursively solve subproblems, caching results. Easier to code, but risk of stack overflow.

Tabulation (Bottom-Up DP): Build solution from base cases upward. More efficient, no recursion overhead, better for large inputs.

Example: Fibonacci

Memoization:

C#

private int[] memo;
public int Fib(int n)
{
    if (memo[n] != -1) return memo[n];
    if (n <= 1) return n;
    memo[n] = Fib(n - 1) + Fib(n - 2);
    return memo[n];
}

Tabulation:

C#

public int Fib(int n)
{
    int[] dp = new int[n + 1];
    dp[0] = 0; dp[1] = 1;
    for (int i = 2; i <= n; i++)
        dp[i] = dp[i - 1] + dp[i - 2];
    return dp[n];
}

Backtracking vs. DFS: When to Use Each

DFS (Depth-First Search): General graph/tree traversal. Visit all nodes. Use when you need to explore entire structure.

Backtracking: DFS + constraint checking. Prune branches that violate constraints. Use for permutations, combinations, Sudoku, N-Queens.

Key Difference: Backtracking explicitly undoes choices (removes from current solution set) when backtracking. DFS just visits.

Binary Search Variants

Standard Binary Search: Find exact element in sorted array.

Left Boundary: Find leftmost position of target.

Right Boundary: Find rightmost position of target.

Insert Position: If target not found, return insertion position.

Rotated Array: Find peak or search in rotation point.

Two Pointers: Common Patterns

Converging: Start from both ends, move toward middle. E.g., #1 (Two Sum sorted), #125 (Valid Palindrome).

Fast-Slow: One pointer 2x speed. E.g., #141 (Linked List Cycle), #876 (Middle of Linked List).

Sliding: Both move in same direction, window size varies. E.g., #3 (Longest Substring), #209 (Minimum Subarray).

Graph Traversal Decision Matrix

Goal	BFS or DFS?	Why	Example
Shortest path (unweighted)	BFS	Guarantees shortest	#127 (Word Ladder)
All paths	DFS	Explore all	#797 (All Paths)
Connected components	Either	Both work; DFS uses less memory	#200 (Islands)
Cycle detection (undirected)	Either	Both work	#261 (Cycle)
Topological order	DFS	Natural fit	#207 (Courses)
Shortest path (weighted)	Dijkstra	Handles weights	#743 (Network Delay)

DP Optimization Techniques

Space Optimization: If dp[i] depends only on dp[i-1], use rolling array. O(n) space → O(1).

State Compression: Use bitmask for small state. E.g., #1495 (Happy Ending) with n≤20.

Convex Hull Trick: Optimize DP with monotonic property. Advanced, rarely needed in interviews.

Greedy Proof Strategy

When greedy works, prove with exchange argument:

Assume optimal solution differs from greedy
Show you can swap one choice without worsening result
Repeat until greedy choice matched optimal
Conclude greedy is optimal

Example: Activity Selection. Greedy: always pick activity ending earliest. Proof: if optimal picks different first activity, swap it with earliest-ending without losing future activities.

Common Pitfalls by Category

Arrays: Off-by-one in loops, not handling duplicates, modifying input when shouldn't.

Strings: Forgetting about unicode, space vs. trimming, case sensitivity.

Trees: Not handling null children, infinite recursion (missing base case), not checking if BST property holds.

Graphs: Visited set not updated, cycle detection missed, disconnected components ignored.

DP: Wrong subproblem definition, incorrect transitions, base case missing.

Greedy: Forgetting to prove greedy works, edge case where greedy fails.

Performance Optimization Tricks

Constant Factor Improvements:

Avoid repeated method calls. Cache array.Length in loop.
Use ref and out to avoid struct copying.
Preallocate collections with capacity.
Avoid LINQ in inner loops (use for loops).
Use Span<T> for zero-copy slicing.

Interviewer Signals (During Mock/Real Test)

Good signs: Interviewer asking follow-up questions about approach, edge cases, or improvements. Means they're engaged.

Red flags: Long silence. May indicate you're off track. Ask clarifying questions.

Recovery: If stuck, think aloud. "This looks like X, let me try..." Interviewer may nudge you.

How to Use Toptal Resources

Code Review Tab: They show you feedback on past submissions. Learn from it.

Discussion Forum: Read solutions, see different approaches. Don't copy; understand.

Practice Problems: Start easy, progressively harder. Don't skip medium to jump to hard.

Post-Interview Debrief

After each mock or real test:

Write down which problems you solved, which you didn't
For each unsolved: What pattern did you miss?
Review the solution: Did it use a technique you haven't mastered?
Solve the problem again 3 days later without looking
Track patterns you're weak in; practice more in that category

Last-Minute Cram Sheet

If you have 1 hour before test:

Review UMPIRE (2 min)
Review Pattern Master Guide table (15 min)
Scan Complexity Target Guide (5 min)
Review Top 5 mistakes you personally made (10 min)
Run through Quick Reference Cheat Sheet (10 min)
Rest, hydrate, deep breathing (18 min)

Long-Term Growth Beyond Toptal

After passing Toptal, continue with:

LeetCode Hard problems: Polish your skills further.
System Design: Learn for senior roles (outside scope of this chapter).
Contribute to open source: Real-world coding experience.
Mentor others: Teaching reinforces your own mastery.

ℹ️

Celebrate Progress: Every problem solved, every pattern mastered, every mock passed—these are wins. Build confidence. You're getting closer.

Common Patterns & Problem-Solving Strategy

Toptal Coding Test Format

Test Structure

Evaluation Rubric (Weighted)

Time Strategy

Hidden Test Case Patterns

UMPIRE Framework

Worked Example: Two Sum (LeetCode #1)

Pattern Recognition Master Guide (30+ Patterns)

How to Use This Table

Complexity Target Guide

Time Budget Examples

C# Tips for Competitive Coding

Essential Data Structures & Methods

Common Patterns & Gotchas

Edge Cases Master Checklist

Pre-Submission Edge Case Routine

Code Quality & Refactoring

Naming Conventions (C#)

Code Quality Principles

Before/After Refactoring Example

Quality Checklist

Top 75 Must-Solve Problems

Arrays & Sorting (12 problems)

Strings (10 problems)

Linked Lists (8 problems)

Trees & Graphs (15 problems)

Dynamic Programming (12 problems)

Remaining High-Value Problems (18 problems)

8-Week (60-Day) Study Plan

Week 1: Foundations & Big O (Days 1–7)

Week 2–3: Core Patterns (Days 8–21)

Week 4–5: Data Structures Deep Dive (Days 22–35)

Week 6–7: Algorithm Paradigms (Days 36–49)

Week 8+: Polish, Mock Tests & All 4 Rounds (Days 50–60)

Mock Interview Tips & Time Management

Time Allocation (90 Minutes Total)

Communication Template (Thinking Aloud)

When You Get Stuck

Before Final Submission

Pressure Management

Common Mistakes to Avoid

Quick Reference Cheat Sheet

Data Structure Operations Complexity

Algorithm Decision Tree

Big O Time Complexity Reference

Input Size → Target Complexity Quick Map

UMPIRE Framework Summary

C# Essentials

Final Checklist (5 Min Before Submit)

Advanced Problem-Solving Techniques

Memoization vs. Tabulation

Backtracking vs. DFS: When to Use Each

Binary Search Variants

Two Pointers: Common Patterns

Graph Traversal Decision Matrix

DP Optimization Techniques

Greedy Proof Strategy

Common Pitfalls by Category

Performance Optimization Tricks

Interviewer Signals (During Mock/Real Test)

How to Use Toptal Resources

Post-Interview Debrief

Last-Minute Cram Sheet

Long-Term Growth Beyond Toptal