# 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