Base Context

Joe thinks this might be the hardest interview so far.

Architecture: might be some kind of system design interview
Programming challenge: maybe a real work scenario

Expecting some kind of back-of-napkin math, space and time complexity…

Big Os

Joe recalls:

O(N): Linear complexity. Scales linearly.
O(1): Constant time. Doesn’t matter the input size.
O(log(N)): Equivalent of binary search. Each time you cut it in half (essentially doubling in speed).
O(N^2): Quadratic. Two loops (a loop within a loop).

Recap: O(log(N))

log(N) is how many times you have to square 2 to get to a number N. In other words, it’s the height of a binary tree with N nodes in it. I think that’s kind of beautiful!

This is why sorting is N * log(N). It’s for each element (N), how long it takes to find its place in the binary search tree (log(N)).

Interview Question: Learner Progress

Example: logging into the user dashboard, I should see (for example) (among other things):

Course: Learn Ruby
Progress: 60%