Technical Interview

Workshop
Jeremy Aguilon
Download this!

https://github.com/JerAguilon/TechnicalInterviewCodeSnippets

Repository with actual implementations of these algorithms.

Also has a few bonus Qs :)
Why do companies do technical interviews?

They are... But they also...

+ easy to do at scale - tend to filter great
+ a standardized candidates
approach to - are a common source of
interviewing frustration
+ great at filtering unfit
candidates
Who am I?

Interned

Student
My motivation

Theoretical Practical Practical...er

What you’ll get

80%
of interview questions

1 hour
of learning
Curriculum Prerequisites
1. Sliding Window 1. Big-O

2. Nested Intervals 2. How recursion works

3. Recursion/Search 3. Basic data structures

(sets, maps, graphs, etc.)
4. Dynamic Programming
Why these 4 topics?

I’ve found that you can reduce many

interview questions into essentially
these 4 questions.
 Sliding Window
Problem

file: slidingWindow/slidingWindow.py
Problem example
Given a string and a set of characters, find the length of the smallest substring
that contains all of the characters
input: ABCZDACB, set: {A,B,C,D}

solution: DACB → 4

input: AAAAABAA, set: {A}

solution: A → 1

Sliding Window Problem

Observations
A) We could just test every substring in O(n2) time. Bad!
B) The global maximum will start and end with different characters in the set
input: ABEEEEEECEBBEAEEEEEEBAGDC, set: {A, B, C}

solution: CEBEA → 5

C) There may be many substrings that have all the characters and start and
end with different characters in the set
input: ABEEEEEECEBBEAEEEEEEBAGDC, set: {A, B, C}

(and many more)

Sliding Window Problem

Algorithmic approach
A) Have two pointers: left and right, starting at 0
B) Increment right until all the characters in the set have
been encountered
C) When the set has been completed, increment left until
one character in the set no longer lies within left and
right.
Note: a minimized string now lies from left - 1 to right. If this is the
smallest string found so far, then store it in some variable
D) Repeat B and C while right is less than the length of
the string

Runtime: O(n)
Sliding Window Problem
Algorithm visualization
input: DADDDBBDCA, set: {A, B, C}

bestScore = infinity
encounteredCharacters {‘a’:0, ‘b’:0, ‘c’ :0, ‘d’:0}

currently: incrementing right

D A D D D B B D C A

0 1 2 3 4 5 6 7 8 9

right

left

Sliding Window Problem

Algorithm visualization
input: DADDDBBDCA, set: {A, B, C}

bestScore = infinity
encounteredCharacters {‘a’:0, ‘b’:0, ‘c’:0, ‘d’:1}

currently: incrementing right

D A D D D B B D C A

0 1 2 3 4 5 6 7 8 9

right

left

Sliding Window Problem

Algorithm visualization
input: DADDDBBDCA, set: {A, B, C}

bestScore = infinity
encounteredCharacters {‘a’:1, ‘b’:0, ‘c’:0, ‘d’:1}

currently: incrementing right

D A D D D B B D C A

0 1 2 3 4 5 6 7 8 9

right

left

Sliding Window Problem

Algorithm visualization
input: DADDDBBDCA, set: {A, B, C}

bestScore = infinity
encounteredCharacters {‘a’:1, ‘b’:0, ‘c’:0, ‘d’:2}

currently: incrementing right

D A D D D B B D C A

0 1 2 3 4 5 6 7 8 9

right

left

Sliding Window Problem

Algorithm visualization
input: DADDDBBDCA, set: {A, B, C}

bestScore = infinity
encounteredCharacters {‘a’:1, ‘b’:0, ‘c’:0, ‘d’:3}

currently: incrementing right

D A D D D B B D C A

0 1 2 3 4 5 6 7 8 9

right

left

Sliding Window Problem

Algorithm visualization
input: DADDDBBDCA, set: {A, B, C}

bestScore = infinity
encounteredCharacters {‘a’:1, ‘b’:0, ‘c’:0, ‘d’:4}

currently: incrementing right

D A D D D B B D C A

0 1 2 3 4 5 6 7 8 9

right

left

Sliding Window Problem

Algorithm visualization
input: DADDDBBDCA, set: {A, B, C}

bestScore = infinity
encounteredCharacters {‘a’:1, ‘b’:1, ‘c’:0, ‘d’:4}

currently: incrementing right

D A D D D B B D C A

0 1 2 3 4 5 6 7 8 9

right

left

Sliding Window Problem

Algorithm visualization
input: DADDDBBDCA, set: {A, B, C}

bestScore = infinity
encounteredCharacters {‘a’:1, ‘b’:2, ‘c’:0, ‘d’:4}

currently: incrementing right

D A D D D B B D C A

0 1 2 3 4 5 6 7 8 9

right

left

Sliding Window Problem

Algorithm visualization
input: DADDDBBDCA, set: {A, B, C}

bestScore = infinity
encounteredCharacters {‘a’:1, ‘b’:2, ‘c’:0, ‘d’:5}

currently: incrementing right

D A D D D B B D C A

0 1 2 3 4 5 6 7 8 9

right

left

Sliding Window Problem

Algorithm visualization
input: DADDDBBDCA, set: {A, B, C}

bestScore = infinity
encounteredCharacters {‘a’:1, ‘b’:2, ‘c’:1, ‘d’:5}

currently: incrementing right

D A D D D B B D C A

0 1 2 3 4 5 6 7 8 9

right

left

Sliding Window Problem

Algorithm visualization
input: DADDDBBDCA, set: {A, B, C}

bestScore = infinity
encounteredCharacters {‘a’:1, ‘b’:2, ‘c’:1, ‘d’:4}

currently: incrementing left

D A D D D B B D C A

0 1 2 3 4 5 6 7 8 9

right

left

Sliding Window Problem

Algorithm visualization
input: DADDDBBDCA, set: {A, B, C}

bestScore = infinity
encounteredCharacters {‘a’:0, ‘b’:2, ‘c’:1, ‘d’:4}

currently: incrementing left

D A D D D B B D C A

0 1 2 3 4 5 6 7 8 9

right

left

Sliding Window Problem

Algorithm visualization
input: DADDDBBDCA, set: {A, B, C}

bestScore = right - left + 1 = 8

encounteredCharacters {‘a’:0, ‘b’:2, ‘c’:1, ‘d’:4}

currently: incrementing left

D A D D D B B D C A

0 1 2 3 4 5 6 7 8 9

right

left

Sliding Window Problem

Algorithm visualization
input: DADDDBBDCA, set: {A, B, C}

bestScore = 8
encounteredCharacters {‘a’:0, ‘b’:2, ‘c’:1, ‘d’:4}

currently: incrementing right

D A D D D B B D C A

0 1 2 3 4 5 6 7 8 9

right

left

Sliding Window Problem

Algorithm visualization
input: DADDDBBDCA, set: {A, B, C}

bestScore = 8
encounteredCharacters {‘a’:1, ‘b’:2, ‘c’:1, ‘d’:4}

currently: incrementing right

D A D D D B B D C A

0 1 2 3 4 5 6 7 8 9

right

left

Sliding Window Problem

Algorithm visualization
input: DADDDBBDCA, set: {A, B, C}

bestScore = 8
encounteredCharacters {‘a’:1, ‘b’:2, ‘c’:1, ‘d’:3}

currently: incrementing left

D A D D D B B D C A

0 1 2 3 4 5 6 7 8 9

right

left

Sliding Window Problem

Algorithm visualization
input: DADDDBBDCA, set: {A, B, C}

bestScore = 8
encounteredCharacters {‘a’:1, ‘b’:2, ‘c’:1, ‘d’:2}

currently: incrementing left

D A D D D B B D C A

0 1 2 3 4 5 6 7 8 9

right

left

Sliding Window Problem

Algorithm visualization
input: DADDDBBDCA, set: {A, B, C}

bestScore = 8
encounteredCharacters {‘a’:1, ‘b’:2, ‘c’:1, ‘d’:1}

currently: incrementing left

D A D D D B B D C A

0 1 2 3 4 5 6 7 8 9

right

left

Sliding Window Problem

Algorithm visualization
input: DADDDBBDCA, set: {A, B, C}

bestScore = 8
encounteredCharacters {‘a’:1, ‘b’:1, ‘c’:1, ‘d’:1}

currently: incrementing left

D A D D D B B D C A

0 1 2 3 4 5 6 7 8 9

right

left

Sliding Window Problem

Algorithm visualization
input: DADDDBBDCA, set: {A, B, C}

bestScore = 8
encounteredCharacters {‘a’:1, ‘b’:0, ‘c’:1, ‘d’:1}

currently: incrementing left

D A D D D B B D C A

0 1 2 3 4 5 6 7 8 9

right

left

Sliding Window Problem

Algorithm visualization
input: DADDDBBDCA, set: {A, B, C}

bestScore = 10 - 7 + 1 = 4
encounteredCharacters {‘a’:1, ‘b’:0, ‘c’:1, ‘d’:1}

currently: incrementing left

D A D D D B B D C A

0 1 2 3 4 5 6 7 8 9

right

left

Sliding Window Problem

Algorithm visualization
input: DADDDBBDCA, set: {A, B, C}

bestScore = 4
encounteredCharacters {‘a’:1, ‘b’:0, ‘c’:1, ‘d’:1}

currently: DONE!

D A D D D B B D C A

0 1 2 3 4 5 6 7 8 9

right

left

Sliding Window Problem

 Pseudocode solution!
* some edge cases ignored for brevity
def solution(string, set):
left = 0
right = 0
letterMap = {letter : 0 for every letter in alphabet}
bestScore = infinity
while (right < length(string)):
*continue incrementing right
letterMap.get(right) += 1
right += 1
if (letterMap.get(char) > 0 for every char in set): *minimize the str!
while (letterMap.get(char) > 0 for every char in set):
letterMap.get(left) -= 1
left += 1
if right - left + 1 < bestScore:
bestScore = right - left + 1
return bestScore
Sliding Window Problem
 Recognizing this algorithm
A) The question involves an ordered sequence of elements
B) The output is supposed to be a global minimum or maximum
C) The trivial solution (testing all substrings) is O(n2)
D) Order doesn’t matter (you’re not matching patterns)

input: ABCZDACB, set: {A,B,C,D} input: ABCZDCAB, set: {A,B,C,D}

solution: DACB solution: DCAB

Sliding Window Problem

Popular questions
A) Given an array of integers, find subarray with the largest total
sum
B) You’re given a string, a mapping from characters → score
(integer), and an integer n. Find the longest substring with a
score less than or equal to n

Sliding Window Problem

 Nested Intervals

file: nestedIntervals/nestedIntervals.py
Problem example
Given a mathematical equation as a string, return whether or not the brackets are
appropriately balanced

input:{3*[1+5(6+8)]} input:{3*[1+5(6+8])}

solution: true solution: false

input:{3*[1+5(6+8)]

solution: false

Nested Intervals
Observations
1. For every opening bracket, there has to be an
equivalent closing bracket
a. openingBrackets - closedBrackets = 0
2. Brackets can be nested, but there can’t be an “offset”
overlap: {(3+1})

Nested Intervals
Algorithm
A) Initialize an empty stack
B) Iterate over the equation. When an opening bracket is encountered, push
the character to the stack
C) If a closing character is encountered, the equation is valid if: the stack is not
empty and if the popped item in the stack matches the closing character
D) If C is never violated and the stack is empty after iterating, return true;
otherwise, return false

Runtime: O(n)

Nested Intervals
Algorithm visualization
input: (3 + 9{12 + 4})(25)

stack

( 3 + 9 { 1 2 + 4 } ) ( 2 5 )

curr

Nested Intervals
Algorithm visualization
input: (3 + 9{12 + 4})(25)

(
stack

( 3 + 9 { 1 2 + 4 } ) ( 2 5 )

curr

Nested Intervals
Algorithm visualization
input: (3 + 9{12 + 4})(25)

(
stack

( 3 + 9 { 1 2 + 4 } ) ( 2 5 )

curr

Nested Intervals
Algorithm visualization
input: (3 + 9{12 + 4})(25)

(
stack

( 3 + 9 { 1 2 + 4 } ) ( 2 5 )

curr

Nested Intervals
Algorithm visualization
input: (3 + 9{12 + 4})(25)

(
stack

( 3 + 9 { 1 2 + 4 } ) ( 2 5 )

curr

Nested Intervals
Algorithm visualization
input: (3 + 9{12 + 4})(25)

{
(
stack

( 3 + 9 { 1 2 + 4 } ) ( 2 5 )

curr

Nested Intervals
Algorithm visualization
input: (3 + 9{12 + 4})(25)

{
(
stack

( 3 + 9 { 1 2 + 4 } ) ( 2 5 )

curr

Nested Intervals
Algorithm visualization
input: (3 + 9{12 + 4})(25)

{
(
stack

( 3 + 9 { 1 2 + 4 } ) ( 2 5 )

curr

Nested Intervals
Algorithm visualization
input: (3 + 9{12 + 4})(25)

{
(
stack

( 3 + 9 { 1 2 + 4 } ) ( 2 5 )

curr

Nested Intervals
Algorithm visualization
input: (3 + 9{12 + 4})(25)

{
(
stack

( 3 + 9 { 1 2 + 4 } ) ( 2 5 )

curr

Nested Intervals
Algorithm visualization
input: (3 + 9{12 + 4})(25)

popped item:{ (matches)

(
stack

( 3 + 9 { 1 2 + 4 } ) ( 2 5 )

curr

Nested Intervals
Algorithm visualization
input: (3 + 9{12 + 4})(25)

popped item:( (matches)

stack

( 3 + 9 { 1 2 + 4 } ) ( 2 5 )

curr

Nested Intervals
Algorithm visualization
input: (3 + 9{12 + 4})(25)

(
stack

( 3 + 9 { 1 2 + 4 } ) ( 2 5 )

curr

Nested Intervals
Algorithm visualization
input: (3 + 9{12 + 4})(25)

(
stack

( 3 + 9 { 1 2 + 4 } ) ( 2 5 )

curr

Nested Intervals
Algorithm visualization
input: (3 + 9{12 + 4})(25)

(
stack

( 3 + 9 { 1 2 + 4 } ) ( 2 5 )

curr

Nested Intervals
Algorithm visualization
input: (3 + 9{12 + 4})(25)

popped item:( (matches)

stack

( 3 + 9 { 1 2 + 4 } ) ( 2 5 )

curr

Nested Intervals
Algorithm visualization
input: (3 + 9{12 + 4})(25)

return true: stack has been cleared

stack

( 3 + 9 { 1 2 + 4 } ) ( 2 5 )

curr

Nested Intervals
 Pseudocode solution!
def solution(string):
stack = Stack()
for letter in string:
if isOpeningBracket(letter):
stack.push(letter)
else if isClosingBracket(letter):
if stack is empty:
return false
lastOpener = stack.pop()
if not matches(letter, lastOpener):
return false
return stack.isEmpty() *iterated successfully over the string, just
make sure that the stack has been cleared

Nested Intervals
Popular questions
A) Given a list of start and end times, return a list of
merged times:
[[1,6], [2,8],[10, 20]] → [[1,8],[10,20]]
*(item 0 and item 1 overlap)

hint: the starting interval values are like opening brackets and the
ending interval values are like ending brackets. Think about how you
can sort these endpoints.

B) (Trickier) Verify preorder serialization of a binary tree

Nested Intervals
 Recursion: DFS

file: countingIslands/countingIslands.py
Problem example
Given a 2d grid, count the number of “islands” in the array. Land is represented as
a 1 that’s connected in the NSEW direction.
input: input: input:

1 1 0 1 0 0 1 1 1
1 0 0 0 1 0 1 0 1
0 1 0 0 0 1 0 1 1

solution: solution: solution:

2 3 1

Recursion: DFS
Observations
A) The grid is almost like a graph:

1 1 0 1 1

1 0 0
0 1 0
1

B) We can access every “node” by simply iterating over the array

Recursion: DFS
Algorithm
1. Iterate over the array using a nested for loop w/ variables x and
y. If you encounter a 1, perform a depth-first-search (DFS)
traversal and increment the islandCount variable by 1
2. DFS search using recursion
a. Base Case: stop recursing if:
i. The index of x and y are out of bounds of the array
ii. The item at arr[x][y] is 0 (not land)
b. Recursive case:
i. Change the element at arr[x][y] to be 0, so that it is not
re-recursed on
ii. Call the recursive function on [x-1][y], [x+1][y], [x][y-1], and
[x][y+1]

Runtime: O(width*height)
Recursion: DFS
Algorithm visualization
input: [[1,1,1], [1,0,0], [0,1,0]]

total = 0
x = 0 1 1 1
y = 0
1 0 0
currently: iterating
0 1 0

Recursion: DFS
Algorithm visualization
input: [[1,1,1], [1,0,0], [0,1,0]]

total = 1 recX = 0
x = 0 recY = 0 1 1 1
y = 0
1 0 0
currently: recursing
0 1 0

Recursion: DFS
Algorithm visualization
input: [[1,1,1], [1,0,0], [0,1,0]]

total = 1 recX = 0
x = 0 recY = 0 0 1 1
y = 0
1 0 0
currently: recursing
0 1 0

Recursion: DFS
Algorithm visualization
input: [[1,1,1], [1,0,0], [0,1,0]]

total = 1 recX = 1
x = 0 recY = 0 0 1 1
y = 0
1 0 0
currently: recursing
0 1 0

Recursion: DFS
Algorithm visualization
input: [[1,1,1], [1,0,0], [0,1,0]]

total = 1 recX = 1
x = 0 recY = 0 0 0 1
y = 0
1 0 0
currently: recursing
0 1 0

Recursion: DFS
Algorithm visualization
input: [[1,1,1], [1,0,0], [0,1,0]]

total = 1 recX = 2
x = 0 recY = 0 0 0 1
y = 0
1 0 0
currently: recursing
0 1 0

Recursion: DFS
Algorithm visualization
input: [[1,1,1], [1,0,0], [0,1,0]]

total = 1 recX = 2
x = 0 recY = 0 0 0 0
y = 0
1 0 0
currently: recursing
0 1 0

Recursion: DFS
Algorithm visualization
input: [[1,1,1], [1,0,0], [0,1,0]]

total = 1 recX = 2
0 0 0 all
x = 0 recY = 0
recursive
y = 0
calls
1 0 0 terminate!
currently: recursing
0 1 0
curr

Recursion: DFS
Algorithm visualization
input: [[1,1,1], [1,0,0], [0,1,0]]

total = 1 recX = 1
x = 0 recY = 0 0 0 0
y = 0
1 0 0
currently: recursing
0 1 0

Recursion: DFS
Algorithm visualization
input: [[1,1,1], [1,0,0], [0,1,0]]

total = 1 recX = 0
x = 0 recY = 0 0 0 0
y = 0
1 0 0
currently: recursing
0 1 0

Recursion: DFS
Algorithm visualization
input: [[1,1,1], [1,0,0], [0,1,0]]

total = 1 recX = 0
x = 0 recY = 1 0 0 0
y = 0
1 0 0
currently: recursing
0 1 0

Recursion: DFS
Algorithm visualization
input: [[1,1,1], [1,0,0], [0,1,0]]

total = 1 recX = 0
x = 0 recY = 1 0 0 0
y = 0
1 0 0
currently: recursing
0 1 0
Algorithm visualization
input: [[1,1,1], [1,0,0], [0,1,0]]

total = 1 recX = 0
x = 0 recY = 1 0 0 0
y = 0
0 0 0
currently: recursing
0 1 0

Recursion: DFS
Algorithm visualization
input: [[1,1,1], [1,0,0], [0,1,0]]

total = 1
x = 0 0 0 0
y = 0
0 0 0
currently: iterating
0 1 0

Recursion: DFS
Algorithm visualization
input: [[1,1,1], [1,0,0], [0,1,0]]

total = 1
x = 1 0 0 0
y = 0
0 0 0
currently: iterating
0 1 0

Recursion: DFS
Algorithm visualization
input: [[1,1,1], [1,0,0], [0,1,0]]

total = 1
x = 2 0 0 0
y = 0
0 0 0
currently: iterating
0 1 0

Recursion: DFS
Algorithm visualization
input: [[1,1,1], [1,0,0], [0,1,0]]

total = 1
x = 0 0 0 0
y = 1
0 0 0
currently: iterating
0 1 0

Recursion: DFS
Algorithm visualization
input: [[1,1,1], [1,0,0], [0,1,0]]

total = 1
x = 1 0 0 0
y = 1
0 0 0
currently: iterating
0 1 0

Recursion: DFS
Algorithm visualization
input: [[1,1,1], [1,0,0], [0,1,0]]

total = 1
x = 2 0 0 0
y = 1
0 0 0
currently: iterating
0 1 0

Recursion: DFS
Algorithm visualization
input: [[1,1,1], [1,0,0], [0,1,0]]

total = 1
x = 0 0 0 0
y = 2
0 0 0
currently: iterating
0 1 0

Recursion: DFS
Algorithm visualization
input: [[1,1,1], [1,0,0], [0,1,0]]

total = 1
x = 1 0 0 0
y = 2
0 0 0
currently: iterating
0 1 0

Recursion: DFS
Algorithm visualization
input: [[1,1,1], [1,0,0], [0,1,0]]

total = 2 recX = 1
x = 1 recY = 2 0 0 0
y = 2
0 0 0
currently: recursing
0 1 0

Recursion: DFS
Algorithm visualization
input: [[1,1,1], [1,0,0], [0,1,0]]

total = 2 recX = 1
x = 1 recY = 2 0 0 0
y = 2
0 0 0
currently: recursing
0 0 0

Recursion: DFS
Algorithm visualization
input: [[1,1,1], [1,0,0], [0,1,0]]

total = 2 recX = 1
0 0 0 all
x = 1 recY = 2
recursive
y = 2
calls
0 0 0 terminate!
currently: recursing
0 0 0

Recursion: DFS
Algorithm visualization
input: [[1,1,1], [1,0,0], [0,1,0]]

total = 2
x = 1 0 0 0
y = 2
0 0 0
currently: iterating
0 0 0

Recursion: DFS
Algorithm visualization
input: [[1,1,1], [1,0,0], [0,1,0]]

total = 2
x = 2 0 0 0
y = 2
0 0 0
currently: iterating
0 0 0

Recursion: DFS
Algorithm visualization
input: [[1,1,1], [1,0,0], [0,1,0]]

total = 2
x = 2 0 0 0
y = 2
0 0 0
currently: iterating
0 0 0
return 2

Recursion: DFS
 Pseudocode solution!
def solution(arr):
total = 0
for y from 0 to length(arr):
for x from 0 to length(arr[y]):
if arr[x][y] == 1:
total += 1
dfs(x, y, arr)
return total

Recursion: DFS
 Pseudocode solution!
def dfs(x, y, arr):
* base cases
if x < 0 or x >= length(arr) or y < 0 or y >= length(arr):
return
if arr[x][y] == 0:
return
* recursive case
arr[x][y] = 0
dfs(x+1, y, arr)
dfs(x-1, y, arr)
dfs(x, y-1, arr)
dfs(x, y+1, arr)

Recursion: DFS
Popular questions
A) Given a 2d grid of characters and a string, return
whether the word exists in the grid using the same rules
as the example question (can only recurse in the NSEW
direction, can’t re-use a cell)
a) Bonus: given a set of words, return whether all the words are in the
grid or not

Hint: look up what a prefix tree is

Recursion: DFS
Other recursive questions
A) Given an array of integers, count the number of
inversions in it. The number of inversions is the number
of adjacent swaps necessary to sort the array.

[2, 3, 1] → 2 (swap index 1 & 2, swap index 0 & 1)

Hint: look up merge sort

Recursion: DFS
 Dynamic
Programming

file: dynamicProgramming/dynamicProgramming.py
What is it?
Dynamic programming:

a) Involved when there are many “overlapping” subproblems to an

algorithm
b) Centers on using past solutions to improve the runtime of an
algorithm

Dynamic Programming
Problem example
Given a number n representing total cents and a set of numbers
representing coins how many ways can you make n cents? You have
an infinite supply of each coin.

input: n=15 coins={1,5}

solution:
15 pennies
2 nickels, 5 pennies
1 nickel, 10 pennies
3 nickels
4 ways
Dynamic Programming
Attempt #1: Recursion
We can recursively reduce n until n<=0

base cases

n = 0 → return 1
n < 0 → return 0

recursive case

total = 0
for every coin c less than or equal to the last used coin:
total += recursivelySolve(n-c, coins, c)
return total

Effectively, we are recursing on two cases: for any coin ci, generate solutions
including ci and excluding ci

Dynamic Programming
 Attempt #1: Python
def solve(n, coins, curr_coin_index):
* base cases
if n == 0:
return 1
if n < 0:
return 0
* recursive case
total = 0
for i in range(0, curr_coin_index):
total += solve(n - coins[i], coins, i)
return total

Dynamic Programming
Attempt #1: Recursive Tree
input: n=15 coins={1,5} n=7
penny
n=8
penny
n=9

(several)
pennies
n = 15 n=8
penny
nickel n=9
penny
n = 10 n=4
nickel penny
n=5
nickel
n = 0 return 1

Dynamic Programming
Attempt #1: Recursive Tree
input: n=15 coins={1,5} n=7
penny
n=8
penny
n=9

(several) Runtime: O(2n)

pennies
Not good!
n = 15 n=8
penny
nickel n=9
penny
n = 10 n=4
nickel penny
n=5
nickel
n = 0 return 1

Dynamic Programming
Attempt #1: Recursive Tree
input: n=15 coins={1,5} n=7
penny
n=8
penny
n=9

(several)
pennies
n = 15 n=8
penny
How can we nickel n=9
reduce these penny
overlapping n = 10 n=4
problems? nickel penny
n=5
nickel
n = 0 return 1

Dynamic Programming
Memoization Yes, it’s really spelled that way

● Technique to cache cache = {}

solutions so that they don’t def solve(n, coins, curr_coin_index):

* base cases
need to be recomputed if n == 0:
● Maintain a mapping from n return 1
if n < 0:
to total return 0
if (n, curr_coin_index) in cache:
○ No recomputing when return cache.get((n, curr_coin_index))
overlapping states are
encountered * recursive case
total = 0
for i in range(0, curr_coin_index):
total += solve(n - coins[i], coins, i)

cache.[(n, curr_coin_index)] = total

return total

Dynamic Programming
Runtime analysis
● Depth of the tree: O(n) cache = {}
○ O(n) solutions are computed def solve(n, coins, curr_coin_index):
due to caching * base cases
if n == 0:
● Each subproblem requires return 1
O(len(coins)) iterations if n < 0:
return 0
if (n, curr_coin_index) in cache:
time complexity: O(n*len(coins)) return cache.get((n, curr_coin_index))

* recursive case
● Number of items in the total = 0
for i in range(0, curr_coin_index):
cache: O(n) total += solve(n - coins[i], coins, i)

space complexity: O(n) cache.[(n, curr_coin_index)] = total

return total

Dynamic Programming
Popular questions
Optimize the fibonacci recursive function.

How many ways can Jim jump up n stairs if he can jump 1, 2,

or 3 steps at a time?

Given a n*n matrix where all numbers are distinct, find the
maximum length path (starting from any cell) such that all
cells along the path are in increasing order with a
difference of 1. You can traverse in the NSEW direction.

Dynamic Programming
return;
That’s all! What next?

● Apply the principles of these four concepts into your

interview questions
● Practice, practice, practice
● With experience, you will start recognizing what
algorithm to use instantly if they match one of these
four categories
Favorite resources
CodeRust 2.0
Introduction to $60 (but worth it if you
Algorithms by CLRS enjoy algorithm
visualizations)

Cracking the Coding

Cracking the Coding Interview HackerRank
Interview by Gayle Totally free!
Laakmann McDowell