competitive programming
This was definitely an interesting challenge, as i started with being very bad and became good (good enough?) exponentially quickly. In this note, i'll review my performance, my approach, as well as some of my favourite algorithms with visualizations.
Table of Contents
How did i do?
After many months of learning and practice i became good, by good i mean i could:
- solve easy / medium / hard questions
- within the time limit
- pass FAANG-grade mock exams (e.g for Facebook)
- pass FAANG-grade systems design mock interviews
- pass FAANG-grade behavioural interviews
Since i did lots of pramp interviews i got a lot of feedback from my peers.
I genuinely enjoyed the interactions with my peers, and made many friends along the way. We'd connect and do study sessions together. I met so many nice and really smart people; absolute blessing.
Things i need to improve
time complexity analysis
I feel my weakest area is time complexity analysis. I can wing it, however the mathematical proofs are brutal e.g recurrence relation with for loop or recurrence relation for a simple decreasing function.
double & triple checking my work
My stats on Leetcode are not that impressive because for the majority of my time doing this work, i'd submit my answer too quickly.
I did get into the habit of double and triple checking my work, but Leetcode's unit tests are utterly brutal so my ratio of failed / correct submissions is not where i'd want it to be.
More thoughts
Overall i feel i could spend a lifetime studying, implementing, optimizing, and writing about algorithms. As such, i feel i hardly even dented the subject.
But that's the point isn't it? The moment you start knowing a subject is the moment you get utterly humbled by how little you know about it.
Leetcode Progress
Classes of problems covered
- Dynamic programming
- Backtracking
- Divide and Conquer
- Quickselect
- Union Find
- Monotonic Stack
- Trie
- Binary Index Tree
- Tabla Hash
- DFS
- Tree
- Binary Tree
- BST
- Math
- BFS
- Recursion
- Arrays
- Strings
- Two Pointers
- Sorting
- Matrices
- Linked Lists
- Stracks
- Simulations
My Learning setup
Following my initial failure to solve even easy questions on leetcode, i quickly decided to purchase Elements of Programming Interviews in Python (aka EPIP - highly recommend).
- Leetcode pro account.
- Pramp.com account.
- iPad pro 12.9 + Apple Pencil 2 .
- Good Notes.
- Anki
I also wrote a custom plugin for Anki. The plugin enabled me to:
- answer cards by typing in 1 line of code within a multi-line code answer.
- the better i knew the code snippet, the longer the selected line would get.
Does it make you a better programmer?
Yes! Absolutely. But there are some caveats.
Pros:
Write more interesting software
Algorithms help you solve hard and interesting problems. This makes you more likely to work on interesting things, rather than plain old CRUD.
Learn how to handle complexity
It's really interesting how even things that seem really complex can be broken down into simpler parts. For me, illustrations helped me a lot. I also developed a process for debugging code by hand that enables me to evaluate code.. well.. by hand and with 100% accuracy.
Raise your complexity threshold
Some of the problems are really really hard to reason about. Spending time reasoning about hard things makes your daily work seem easy in comparison.
Build a general framework for problem solving
Competitive algorithmic programming builds you a cognitive framework to solve many problems, not just algorithmic ones.
Cons
Narrow mindedness
This point is very well illustrated in this Joma comedy skit where he over-prepares for the interview, and answers "hash map" to a soft-skill question.
When you're a hammer everything looks like a nail.
Expert beginner
Competitive programming helped me escape the expert beginner trap, and strangely landed me back into a new one.
It is very closely tied to narrow mindedness. After getting really good at this, i thought i was invincible and the quality of my work deteriorated as a result. After noticing this i was able to relax, slow down, open my mind, and pick up again.
Going too fast
Competitive programming really trains you to solve problems fast! But the problems are actually a very narrow set, and when returning to real world everyday programming, most of the skills are not transferrable.
As a result, i was plowing through things too quickly.
It's about the problem space
The most important skill i got to learn is to spend as much time as possible in the problem space before jumping into the solution space.
This may sound counter-intuitive... why waste time lingering on the problem? The reason is simple: even if you can't think of the solution, you can walk on the edges of the wrong paths, even if they are the wrong paths. Just don't take them. You're mapping out the territory. You don't know the answer yet, so you keep on contemplating the wrong paths. Just don't take them until you find the good one.
The steps to solving any algorithmic problem at speed basically go like this:
- Make sure you fully understand the question... really.
- Flesh out the problem space.
- What class of problem is it?
- Think of the solution space.
- Propose an approach.
- Discuss space & time complexity.
- Pseudocode it.
- Code it.
- Think of edge-cases.
- Test it.
- Submit.
Of course, these problems can land in many classes, e.g they may involve statistics, set theory, recursion, dynamic programming etc. it's really challenging, and rather addictive.
Overview
Preliminary skills
drawing data tables
It may sound obvious, but one of the advantages i often had over my peers when working through these problems was my meticulousness at writing down all the required tables of data required before starting to work through the problem space.
Writing the actual data, and being able to represent it neatly in the editor in ASCII definitely confers a strong advantage.
tracing recursion trees
Before embarking on his journey i was hopeless at recursion. EPIP helped me a lot get good at it, and i was surprised by how many problems involved recursion. For example dynamic programming problems can usually be solved with either data tables or recursion, not to mention graph or tree problems.
So not only is mastering recursion a pre-requisite for many classes of problems, but the ability of quickly tracing the recursion tree helps a lot with solving many classes of problems.
Visualisations
I'm a visual & kinesthetic thinker. Initially i started drawing out the problems on the iPad using Good Notes. By the end of this process, i created high quality animations of some of my favourite problems using manim from 3 blue 1 brown .
Above is a video of one of my favourite problems, shortest distance from all buildings. Good example of a problem labelled 'hard' but is actually quite easy once visualized properly.
Rabin Karp
rabin karp offers a really elegant solution for string matching in linear time. It's quite often used in DNA sequencing!
Linked list algorithms
Linked list algorithms are a really great primer to getting used to the meticulousness involved with data structure work.
The reverse sublist problem is definitely harder than it sounds.
Finding a linked list cycle is, once again, one of these things that has to be seen to be believed.
The add two numbers problem sounds simple, but is a lot harder to implement than it sounds.
I could never imagine deeply grasping this algorithm without actually seeing it in action: merge k sorted lists.
drone flight planner
longest arithmetic sequence
best time to buy and sell stock
Given time & price data, pick the best time to buy and sell stock.
depth first search
Visualisations of pre-order, in-order and post-order depth first search.
Before
Validate Sudoku
writing a sudoku solver, it's important to fully understand how to validate sudoku.
Here's my implementation of a sudoku solver. Fastest Python solver i've come across to date.
We use a visual metaphor of hopping down a road to gain a visceral understanding of subarray sum equals k.
generating primes is one of the true classics in computer science. We explore brute force versus using a sieve.
Levenshtein distance
levenshtein distance is quite a simple problem with a fascinating dynamic programming solution.
Find the celebrity
Fascinating graph problem. Solution can be expressed as a 2 line find the celebrity.
Somewhat documented
Here's a list of my realtime notes. It's still unstructured and probably unfinished.
binary search
splitting a list into two distinct sublists
huffman encoding
optimal merge pattern
Undocumented
divide two integers
roman to numeral
reorder routes to make all paths lead to city zero
number of submatrices
number of paths
rotated digits
next closest time
rotten oranges
spiral matrix II
[[trapping rain water]]
product of array except self
diameter of binary tree
merge intervals
minimum remove to make valid parentheses
integer to english words
serialize and deserialize binary tree
alien dictionary
word break
verifying an alien dictionary
next permutation
add strings
minimum window substring
merge sorted array
binary tree right side view
binary tree maximum path sum
remove invalid parentheses
valid palindrome
vertical order traversal of a binary tree
binary tree vertical order traversal
task scheduler
random pick with weight
longest substrinct with at most k distinct characters
exclusive time of functions
intersection of two arrays
accounts merge wip
range sum of bst
continuous subarray sum
closest binary search tree value
maximum swap
k closest points to origin
is graph bipartitie
random pick index
maximum sum of 3 non overlapping subarrays
maximum difference between node and ancestor
binary tree vertical order traversal
online stock span
maximum size subarray sum equals k
longest palindrome
zigzag conversion
regular expression matching
multiply strings
mincost tickets
permuting a string
binary search tree iterator
pow x n
find connected components
num encodings
subsets
subsets II
the skyline problem
split array with equal sums
exclusive time of functions
basic calculator II
maximum sum of 3 non overlapping subarrays
design add and search words data structure
matrix diagonal sum
path sum iii
power of two
meeting rooms ii
lru cache
inorder successor in bst
largest time for given digits
range sum query mutable
intersection of three sorted arrays
next greater element i
pythonic tricks
string formatting
enumerate
reversing a subarray
shifted zip
return a list with 0 or 1 items
slicing to prevent list index out of range
array min
max array
max array from right
matrix transpose
matrix clockwise rotation
matrix anticlockwise rotation
itertools.product
single bidirectional pass
string contains all chars unordered
string contains all chars ordered
using xor for signedness
find missing number in array
int to base
depth first search
bfs
dp array sum
enum
Huffman Encoding
Splitting a list into to distinct lists
Advanced Python
Trees
minimum cost spanning tree
multistage graph
pramp algorithms
budget cuts
flatten a dictionary
find first occurrence of k in array
substring search
move zeroes to end
toeplitz matrix
spiral order matrix
number of islands
product of array except self
pancake sort
draw h tree
decoding a string
getting a different number
shifted array search
busiest time at the mall
bracket match
minimum deletion
diff between two strings
word count engine
TBD:
EPIP
rotate a 2d array
binary tree level order traversal
search first key
remove duplicates
levenshtein distance
2d matrix ways
binomial coefficients
time complexity analysis
n
quadratic
n(n+1) over 2
sqrt(n)
recurrence relation for a simple decreasing function
recurrence relation with for loop
big oh definition
theta definition
big omega definition