The Interview Cake Course

You left off on The Cake Thief

Go there

0. Algorithmic thinking

Readings

Big O Notation

Learn how to compare the efficiency of different approaches to a problem.

Data Structures

Build the main data structures from the ground up. Learn when to use an array vs. a linked list vs.…

Logarithms

Logarithms come up a lot in algorithms. Review how they work and learn the situations where they're…

1. Array and string manipulation

Readings

Array

An array is a low-level data structure where elements are identified by integer indices. Arrays are…

Array Slicing

This is a common tool, but you need to know what it does under the hood!

In-Place Algorithms

An in-place algorithm operates directly on its input and changes it, instead of creating and return…

Dynamic Array

A dynamic array automatically doubles its size when you try to make an insertion and there's no mor…

Practice

Merging Meeting Times

Write a function for merging meeting times given everyone's schedules. It's an enterprise end-to-en…

Reverse String in Place

Write a function to reverse a string in place.

Reverse Words

Write a function to reverse the word order of a string, in place. It's to decipher a supersecret me…

Merge Sorted Arrays

Write a function for consolidating cookie orders and taking over the world.

Cafe Order Checker

Write a function to tell us if cafe customer orders are served in the same order they're paid for.

2. Hashing and hash tables

Readings

Hashing and Hash Functions

Suppose you wanted a short but unique identifier for a file or dataset. That's the idea behind hash…

Hash Table

A hash table (also called a hash, hash map or dictionary) is a data structure that pairs keys to va…

Practice

Inflight Entertainment

Writing a simple recommendation algorithm that helps people choose which movies to watch during fli…

Permutation Palindrome

Check if any permutation of an input string is a palindrome.

Word Cloud Data

You're building a word cloud. Write a function to figure out how many times each word appears so we…

3. Greedy algorithms

Readings

Greedy Algorithms

A greedy algorithm builds up a solution by choosing the option that looks the best at every step.

Practice

Apple Stocks

Figure out the optimal buy and sell time for a given stock, given its prices yesterday.

Highest Product of 3

Find the highest possible product that you can get by multiplying any 3 numbers from an input array.

Product of All Other Numbers

For each number in an array, find the product of all the other numbers. You can do it faster than y…

Cafe Order Checker

Write a function to tell us if cafe customer orders are served in the same order they're paid for.

In-Place Shuffle

Do an in-place shuffle on an array of numbers. It's trickier than you might think!

4. Sorting, searching, and logarithms

Readings

Binary Search Algorithm

Binary search is a clever way to find an item in a sorted array in O(lg n) time. It involves iterat…

Practice

Find Rotation Point

I wanted to learn some big words to make people think I'm smart, but I messed up. Write a function …

Find Repeat, Space Edition

Figure out which number is repeated. But here's the catch: optimize for space.

Top Scores

Efficiently sort numbers in an array, where each number is below a certain maximum.

Merging Meeting Times

Write a function for merging meeting times given everyone's schedules. It's an enterprise end-to-en…

5. Trees and graphs

Readings

Binary Tree

A binary tree is a tree where every node has two or fewer children. The children are usually called…

Graph

Graphs are like a trees, but with no set root node. They can be directed or undirected, cyclic or a…

Breadth-First Search (BFS)

Breadth-first search is a method for walking through a tree or graph where you "fan out" as much as…

Depth-First Search (DFS)

Depth-first search is a method for walking through a tree or graph where you go as deep as possible…

Practice

Balanced Binary Tree

Write a function to see if a binary tree is 'superbalanced'--a new tree property we just made up.

Binary Search Tree Checker

Write a function to check that a binary tree is a valid binary search tree.

2nd Largest Item in a Binary Search Tree

Find the second largest element in a binary search tree.

Graph Coloring

Color the nodes in a graph so adjacent nodes always have different colors.

MeshMessage

You wrote a trendy new messaging app, MeshMessage, to get around flaky cell phone coverage. But mes…

Find Repeat, Space Edition BEAST MODE

Figure out which number is repeated. But here's the catch: do it in linear time and constant space!

6. Dynamic programming and recursion

Readings

Overlapping Subproblems

A problem has overlapping subproblems if finding its solution involves solving the same subproblem …

Memoization

Memoization ensures that a function doesn't run for the same inputs more than once. It's generally …

Bottom-Up Algorithms

Going bottom-up is a way to avoid recursion, saving memory cost in the call stack. It's a common st…

Practice

Recursive String Permutations

Write a recursive function of generating all permutations of an input string.

Compute the nth Fibonacci Number

Computer the nth Fibonacci number. Careful--the recursion can quickly spin out of control!

Making Change

Write a function that will replace your role as a cashier and make everyone rich or something.

The Cake Thief

You've hit the mother lode: the cake vault of the Queen of England. Figure out how much of each cak…

Balanced Binary Tree

Write a function to see if a binary tree is 'superbalanced'--a new tree property we just made up.

Binary Search Tree Checker

Write a function to check that a binary tree is a valid binary search tree.

2nd Largest Item in a Binary Search Tree

Find the second largest element in a binary search tree.

7. Queues and stacks

Readings

Queue

A queue is like a line at the movie theater. It's "first in, first out" (FIFO). It's usually best t…

Stack

A stack is like a stack of plates. It's "last in, first out" (LIFO), which means that the item that…

Practice

Largest Stack

You've implemented a Stack class, but you want to access the largest element in your stack from tim…

Implement A Queue With Two Stacks

Implement a queue with two stacks. Assume you already have a stack implementation.

Parenthesis Matching

Write a function that finds the corresponding closing parenthesis given the position of an opening …

Bracket Validator

Write a super-simple JavaScript parser that can find bugs in your intern's code.

8. Linked lists

Readings

Linked List

A linked list is a low-level data structure that stores an ordered list of "nodes." The order is st…

Practice

Delete Node

Write a function to delete a node from a linked list. Turns out you can do it in constant time!

Does This Linked List Have A Cycle?

Check to see if a linked list has a cycle. We'll start with a simple solution and move on to some p…

Reverse A Linked List

Write a function to reverse a linked list in place.

Kth to Last Node in a Singly-Linked List

Find the kth to last node in a singly-linked list. We'll start with a simple solution and move on t…

Find Repeat, Space Edition BEAST MODE

Figure out which number is repeated. But here's the catch: do it in linear time and constant space!

9. System design

Practice

URL Shortener

Design a URL shortener, like bit.ly

MillionGazillion

I'm making a new search engine called MillionGazillion(tm), and I need help figuring out what data …

Find Duplicate Files

Your friend copied a bunch of your files and put them in random places around your hard drive. Writ…

10. General programming

Readings

Short Circuit Evaluation

Short circuit evaluation avoids unnecessary work. Here are some examples.

Garbage Collection

If you create an object (like an array) inside a function and that function doesn't return a refere…

Closures

A closure is a function that accesses a variable "outside" itself. Here's an example where "message…

Mutable vs Immutable Objects

Mutable objects can be changed, while immutable objects can't. In Python, strings are immutable, so…

Practice

Rectangular Love

Find the area of overlap between two rectangles. In the name of love.

Temperature Tracker

Write code to continually track the max, min, mean, and mode as new numbers are inserted into a tra…

11. Bit manipulation

Readings

Binary Numbers

An easy-to-understand explanation of how numbers are represented in binary, including negative numb…

Bitwise AND

Think of bitwise AND like a hose with two knobs. /Both/ knobs must be set to "on" for water to come…

Bitwise OR

Think of bitwise OR like a bucket with two holes in it. If both holes are closed, no water comes ou…

Bitwise XOR (eXclusive OR)

Think of bitwise XOR like a narrow bag of chips with that can only fit 1 hand at a time. The only w…

Bitwise NOT

Bitwise NOT basically "flips" the set of bits you give it, changing all the 1s to 0s and all the 0s…

Bit Shifting

A bit shift moves each digit in a set of bits left or right. The last bit in the direction of the s…

Integer Overflow

When you create an integer variable, your computer allocates 64 bits for storing it. What if your n…

Practice

The Stolen Breakfast Drone

In a beautiful Amazon utopia where breakfast is delivered by drones, one drone has gone missing. Wr…

12. Combinatorics, probability, and other math

Readings

Triangular Series

Triangular series are simple increasing integers starting from 1, like {1,2,3,4,5}. There's a formu…

Practice

Which Appears Twice

Find the repeat number in an array of numbers. Optimize for runtime.

Find in Ordered Set

Given an array of numbers in sorted order, how quickly could we check if a given number is present …

In-Place Shuffle

Do an in-place shuffle on an array of numbers. It's trickier than you might think!

Simulate 5-sided die

Given a 7-sided die, make a 5-sided die.

Simulate 7-sided die

Given a 5-sided die, make a 7-sided die.

Two Egg Problem

A building has 100 floors. Figure out the highest floor an egg can be dropped from without breaking.

13. JavaScript

Readings

Closures

A closure is a function that accesses a variable "outside" itself. Here's an example where "message…

In-Place Algorithms

An in-place algorithm operates directly on its input and changes it, instead of creating and return…

Practice

JavaScript Scope

There's something tricky going on with scope in this JavaScript. Can you guess what will get logged…

What's Wrong with This JavaScript?

There's a tricky bug in this JavaScript. Can you find it?

14. Coding Interview Tips

Random Practice

Knowing ahead of time what topic the problem deals with can give things away. Be sure to supplement your linear walk through the course with some randomized practice.

Random question