Algorithms & Data Structures Practice

My solutions to algorithm problems (LeetCode and others), written to be read. Every solution includes the approach, time/space complexity, and short notes — explained as if to another junior developer.

Русская версия

Why this repo

I'm sharpening my problem-solving and Python fundamentals on the way to a career in Data / ML / AI. The aim is to understand each solution — the approach, the complexity, and the one insight that makes it work — rather than to collect green check-marks. Every file is written to be read and explained, so the repo doubles as a study resource I revise from.

How it's organized

Problems are grouped by topic. Each file is self-documenting: a short docstring states the problem, the idea behind the solution, and its complexity.

algorithms-practice/
├── arrays_and_hashing/
├── two_pointers/
├── sliding_window/
├── stack/
├── binary_search/
├── linked_list/
├── trees/
├── heap/
├── backtracking/
├── graphs/
├── advanced_graphs/
├── dynamic_programming/
├── greedy/
├── intervals/
├── tries/
├── bit_manipulation/
├── ml_and_data/          ← ML/data-specific interview questions
└── sql/                  ← analytics SQL, runnable on stdlib sqlite3

ml_and_data/ is deliberately a different kind of block. The rest of the repo follows the NeetCode roadmap; this one holds what actually gets asked in Data Scientist / ML Engineer interviews — implement ROC-AUC, k-means, or a stable softmax without a library, and explain the numerics. Still pure Python, so the algorithm is visible instead of hidden behind a numpy call.

Several files in it are the machinery from the pet projects, extracted and written from scratch: the chi-square test reproduces the SRM numbers from ab-test-analysis to three decimals, PSI is the drift alarm from bank-marketing-ml, and the time-series splits are what macro-nowcast backtests on.

sql/ is the same idea for SQL: cohort retention, funnels, sessionization, point-in-time joins. It runs on sqlite3 from the standard library — python sql/run.py --all executes every query against a fixture small enough to verify by hand. See sql/README.md.

Where a naive solution is worth contrasting with the optimal one, the file keeps both — the brute force first, then the idea that removes the extra work.

How to read a solution

Each file follows the same shape, so a reviewer can find what they need fast:

class Solution:
    """LeetCode #NN - Problem Name (Difficulty)
    https://leetcode.com/problems/...

    One-paragraph restatement of the problem in plain words.
    """

    def solve(self, ...):
        """The approach, the key insight, and why it is correct.

        Time:  O(...) - with a sentence on where the cost comes from.
        Space: O(...)
        """
        ...

The comments favour why over what — the invariant a loop maintains, the reason a particular data structure fits, the edge case that a line guards against.

Coverage

108 problems across 17 topics — the NeetCode 150 / Blind 75 roadmap, plus a block of ML/data interview questions:

Topic	Solved	Topic	Solved
ML & Data	16	Backtracking	6
Trees	10	Binary Search	5
Dynamic Programming	9	Stack	5
Arrays & Hashing	8	Two Pointers	5
Graphs	7	Heap	5
Sliding Window	6	Intervals	5
Linked List	6	Bit Manipulation	5
		Greedy	4
		Advanced Graphs	3
		Tries	3

Includes fifteen Hard problems: Trapping Rain Water, Merge k Sorted Lists, Binary Tree Maximum Path Sum, Find Median from Data Stream, Minimum Window Substring, Sliding Window Maximum, Largest Rectangle in Histogram, Median of Two Sorted Arrays, Reverse Nodes in k-Group, Serialize and Deserialize Binary Tree, N-Queens, Word Ladder, Edit Distance, Reconstruct Itinerary, and Word Search II.

Running

Pure Python 3, no dependencies. Each file defines a Solution class matching the LeetCode signature, so any solution can be imported and exercised directly:

from arrays_and_hashing.two_sum import Solution
Solution().twoSum([2, 7, 11, 15], 9)   # -> [0, 1]

Progress

#	Problem	Topic	Difficulty	Key idea
1	Two Sum	Arrays & Hashing	Easy	Hash map: store seen values, look up target - x in O(1)
2	Contains Duplicate	Arrays & Hashing	Easy	Set of seen values; order is irrelevant, membership is O(1)
3	Valid Anagram	Arrays & Hashing	Easy	Count characters instead of sorting — anagram is a statement about counts
4	Group Anagrams	Arrays & Hashing	Medium	26-letter count vector as a hashable dict key, built in O(k)
5	Top K Frequent Elements	Arrays & Hashing	Medium	Bucket sort by frequency — frequency ≤ n, so use it as an index
6	Product of Array Except Self	Arrays & Hashing	Medium	Prefix pass × suffix pass, no division, O(1) extra space
7	Valid Palindrome	Two Pointers	Easy	Two pointers skipping non-alphanumerics — no cleaned copy needed
8	Two Sum II	Two Pointers	Medium	Sorted input: each move discards a pair that could never work
9	3Sum	Two Pointers	Medium	Sort, fix one number, run Two Sum II on the rest; skip duplicates
10	Container With Most Water	Two Pointers	Medium	Always move the shorter line — the taller one can only lose width
11	Best Time to Buy and Sell Stock	Sliding Window	Easy	Carry the cheapest price seen so far; sell against it in one pass
12	Longest Substring Without Repeating Characters	Sliding Window	Medium	Window + map of last positions; left jumps past the repeat in O(1)
13	Longest Repeating Character Replacement	Sliding Window	Medium	Window is valid while length - max_count <= k
14	Valid Parentheses	Stack	Easy	Brackets nest → LIFO; the top of the stack must match the closer
15	Min Stack	Stack	Medium	Parallel stack of running minimums → O(1) getMin, O(n) memory
16	Binary Search	Binary Search	Easy	Halve a closed interval [left, right]; while left <= right
17	Valid Sudoku	Arrays & Hashing	Medium	One pass feeding three sets; box id is (r // 3, c // 3)
18	Longest Consecutive Sequence	Arrays & Hashing	Medium	Only walk a run from its head (x - 1 absent) — that guard keeps it O(n)
19	Permutation in String	Sliding Window	Medium	Fixed-size window + a matches counter instead of recomparing 26 slots
20	Evaluate Reverse Polish Notation	Stack	Medium	Stack eval; division must truncate toward zero, not floor like //
21	Daily Temperatures	Stack	Medium	Monotonic decreasing stack — the "next greater element" pattern
22	Search a 2D Matrix	Binary Search	Medium	Treat the matrix as one flat sorted array: row = i // cols, col = i % cols
23	Koko Eating Bananas	Binary Search	Medium	Binary search on the answer — the predicate is monotonic, the array isn't sorted
24	Find Minimum in Rotated Sorted Array	Binary Search	Medium	Compare mid with the right end, not the left — no special case for zero rotation
25	Reverse Linked List	Linked List	Easy	Flip each next toward the predecessor; save next before overwriting it
26	Merge Two Sorted Lists	Linked List	Easy	Merge step of merge sort; a dummy head removes the "list is empty" special case
27	Linked List Cycle	Linked List	Easy	Floyd's tortoise and hare — fast gains one step per iteration, so it can't skip past slow
28	Remove Nth Node From End	Linked List	Medium	Two pointers with a fixed gap of n; dummy head covers removing the head
29	Invert Binary Tree	Trees	Easy	Swap children at every node — recursion, plus a BFS version for deep trees
30	Maximum Depth of Binary Tree	Trees	Easy	1 + max(depth(left), depth(right)); BFS variant counts levels
31	Binary Tree Level Order Traversal	Trees	Medium	Snapshot len(queue) to get level boundaries; deque so popleft is O(1)
32	Same Tree	Trees	Easy	Lockstep recursion; the "exactly one is None" case must come before .val
33	Subtree of Another Tree	Trees	Easy	Reuse "same tree" as a helper, try it at every node
34	Diameter of Binary Tree	Trees	Easy	One DFS returns depth and records left + right at each turning point
35	Validate BST	Trees	Medium	Pass a (low, high) range down — checking parent/child pairs alone is wrong
36	Lowest Common Ancestor of a BST	Trees	Medium	Walk down until the two values straddle the node — that's the split point
37	Kth Largest Element in a Stream	Heap	Easy	Min-heap capped at size k — its root is the k-th largest
38	Last Stone Weight	Heap	Easy	Negate values to fake a max-heap out of Python's min-only heapq
39	K Closest Points to Origin	Heap	Medium	Compare squared distances (sqrt is monotonic); heapify is O(n), not O(n log n)
40	Subsets	Backtracking	Medium	Take/skip branch per element; choose → explore → undo, and copy with [:]
41	Combination Sum	Backtracking	Medium	start index kills permutation duplicates; recurse with i, not i + 1, to allow reuse
42	Permutations	Backtracking	Medium	Order matters, so no start — a used[] flag excludes what's already placed
43	Number of Islands	Graphs	Medium	Connected components on an implicit grid graph; BFS flood-fill, mark on enqueue
44	Clone Graph	Graphs	Medium	original → copy map doubles as visited; register the copy before recursing
45	Climbing Stairs	Dynamic Programming	Easy	Fibonacci in disguise; two rolling variables replace the DP table
46	House Robber	Dynamic Programming	Medium	best(i) = max(best(i-1), best(i-2) + nums[i]); greedy fails on [2,1,1,2]
47	Trapping Rain Water	Two Pointers	Hard	Only the smaller running max matters — so it's already final and can be committed
48	Merge k Sorted Lists	Linked List	Hard	Pair up and merge in rounds: O(n log k), not O(n·k); heap version needs a tie-breaker
49	Binary Tree Maximum Path Sum	Trees	Hard	Return "best downward path", record "best path turning here"; clamp negatives to 0
50	Find Median from Data Stream	Heap	Hard	Two heaps: max-heap for the lower half, min-heap for the upper — median sits at the roots
51	Implement Trie	Tries	Medium	Prefix tree; every op is O(len(word)), independent of how many words are stored
52	Design Add and Search Words	Tries	Medium	. wildcard turns the walk into a DFS that fans out over all children
53	Insert Interval	Intervals	Medium	Input is pre-sorted → three phases (before / overlapping / after), no re-sorting
54	Merge Intervals	Intervals	Medium	Sort by start; compare only against the last kept interval, extend with max
55	Non-overlapping Intervals	Intervals	Medium	Sort by end and keep greedily — sorting by start breaks it
56	Maximum Subarray	Greedy	Medium	Kadane: a negative prefix is never worth carrying, so drop it
57	Jump Game	Greedy	Medium	Walk backwards moving the goal post; forward-reach variant included
58	Counting Bits	Bit Manipulation	Medium	bits(i) = bits(i >> 1) + (i & 1) — reuse the already-solved smaller number
59	Reverse Bits	Bit Manipulation	Easy	Pop from the bottom of n, push onto the bottom of the result; exactly 32 rounds
60	Course Schedule	Graphs	Medium	Topological sort (Kahn) — the real question is cycle detection
61	Network Delay Time	Advanced Graphs	Medium	Dijkstra — BFS is wrong once edges carry different weights
62	Min Cost to Connect All Points	Advanced Graphs	Medium	Prim's MST — minimising total edge weight, not distance from a source
63	Minimum Window Substring	Sliding Window	Hard	A satisfied counter updated only on ==/< keeps validity O(1) per step
64	Sliding Window Maximum	Sliding Window	Hard	Monotonic deque of indices — a smaller earlier value can never win again
65	Largest Rectangle in Histogram	Stack	Hard	Each bar is settled when a shorter one arrives; inherit start from what you popped
66	Median of Two Sorted Arrays	Binary Search	Hard	Binary-search the partition: fix the left half's size, check two inequalities
67	Reverse Nodes in k-Group	Linked List	Hard	Check the k-th node exists first; seed the reversal with group_next to stitch as you go
68	Serialize and Deserialize Binary Tree	Trees	Hard	Pre-order with explicit null markers; one shared iterator replays the walk
69	N-Queens	Backtracking	Hard	One queen per row by construction; r - c and r + c make attack checks O(1)
70	Word Ladder	Graphs	Hard	BFS on an implicit graph; h*t wildcard buckets replace O(N²) pairwise comparison
71	Edit Distance	Dynamic Programming	Hard	Levenshtein: equal → diagonal, else 1 + min(replace, delete, insert); rolled to two rows
72	Reconstruct Itinerary	Advanced Graphs	Hard	Eulerian path (Hierholzer) — a stuck airport must be the end, so build the route backwards
73	ROC-AUC from scratch	ML & Data	Medium	AUC = P(pos > neg) + ½P(tie); the Mann-Whitney rank sum computes it in O(n log n)
74	Welford's online statistics	ML & Data	Medium	One-pass mean/variance without catastrophic cancellation; merges across partitions
75	Reservoir sampling	ML & Data	Medium	Keep item i with probability k/(i+1) — uniform over a stream of unknown length
76	K-means from scratch	ML & Data	Hard	Lloyd's algorithm converges to a local optimum — hence k-means++ seeding and restarts
77	Logistic regression by gradient descent	ML & Data	Hard	The sigmoid derivative cancels against log-loss: the gradient is just (p − y)·x
78	Softmax & cross-entropy	ML & Data	Medium	Softmax is shift-invariant, so subtracting max is free — that's the log-sum-exp trick
79	Sparse Matrix Multiplication	ML & Data	Medium	Loop i→k→j so a zero in A skips a whole row of B; dict-of-keys version for real scale
80	k-nearest neighbours	ML & Data	Medium	Lazy learner: O(1) to train, O(n·d) to predict; bounded heap gives top-k in O(n log k)
81	Random Pick with Weight	ML & Data	Medium	Prefix sums + binary search; alias method gets it to O(1) per draw
82	Shuffle an Array	ML & Data	Medium	Fisher-Yates swaps with [0, i] inclusive; the naive version is provably biased
83	Coin Change	Dynamic Programming	Medium	best[a] = 1 + min(best[a - c]); greedy fails on coins [1,3,4], amount 6
84	Longest Increasing Subsequence	Dynamic Programming	Medium	Patience sorting: tails[i] = smallest end of a length-i+1 run, so binary search places each number
85	Word Break	Dynamic Programming	Medium	reachable[i] from any earlier reachable cut; greedy strands the tail on "aaaaab"
86	Longest Common Subsequence	Dynamic Programming	Medium	Match → diagonal (both strings shrink); mismatch takes a max, not a reset — that's what makes it subsequence
87	Partition Equal Subset Sum	Dynamic Programming	Medium	0/1 knapsack on reachable sums; iterate descending so each number is used once
88	Maximum Product Subarray	Dynamic Programming	Medium	Carry min as well as max — a negative swaps their roles, unlike Kadane on sums
89	Pacific Atlantic Water Flow	Graphs	Medium	Flood from both oceans uphill and intersect, instead of searching from every cell
90	Rotting Oranges	Graphs	Medium	Multi-source BFS — seed every rotten cell at distance 0, one level per minute
91	Surrounded Regions	Graphs	Medium	Mark what the border reaches, then flip the rest — proving "enclosed" directly is the hard direction
92	Word Search	Backtracking	Medium	Blank the cell, recurse, restore; letter-count prune and reversing the word cut the branching
93	Palindrome Partitioning	Backtracking	Medium	Precomputed is_pal table prunes before recursing rather than after
94	Word Search II	Tries	Hard	One board DFS guided by a trie; refcount nodes and unlink found words so dead branches disappear
95	Single Number	Bit Manipulation	Easy	XOR annihilates pairs; the mod-3 bit count variant handles the "appears three times" version
96	Missing Number	Bit Manipulation	Easy	XOR indices against values so every present number cancels; Gauss sum is the overflow-prone alternative
97	Sum of Two Integers	Bit Manipulation	Medium	a ^ b sums, (a & b) << 1 carries; Python needs a 32-bit mask or the carry never terminates
98	Meeting Rooms	Intervals	Easy	Sort by start — then only adjacent pairs can clash, so one scan suffices
99	Meeting Rooms II	Intervals	Medium	Min-heap of end times; heap size is the room count. Sweep-line version generalises to concurrency
100	Gas Station	Greedy	Medium	Total decides whether, running tank decides where — a negative prefix rules out every start inside it
101	Hand of Straights	Greedy	Medium	The smallest card must head a run, so there is nothing to branch on
102	Task Scheduler	Heap	Medium	The most frequent task fixes the skeleton: (k-1)(n+1) + ties, floored by len(tasks)
103	Bootstrap confidence intervals	ML & Data	Hard	Resample to get an interval for a statistic with no closed-form SE; BCa corrects bias and skew
104	Chi-square tests from scratch	ML & Data	Medium	Goodness-of-fit (SRM) and independence, with the p-value from the incomplete gamma rather than a library
105	Population Stability Index	ML & Data	Medium	Drift alarm needing no labels; freeze the bin edges on the reference or it reports no drift, ever
106	Time-series splitting	ML & Data	Medium	Expanding / sliding / purged windows; the embargo covers labels whose window extends past the cut
107	Bayesian A/B test	ML & Data	Medium	Beta-Binomial conjugacy answers "P(B wins)"; expected loss is the number to act on, not the win rate

| 108 | Classification metrics | ML & Data | Medium | Confusion matrix to precision/recall/F1, plus precision@k and lift@k - the ranking metrics a call list is actually judged on |

Tech

• Python 3.13