☕ Dynamic Programming in the Real World
I break down the time complexity to yesterday's solution. Also, an awesome article on the Seam Carving Algorithm for Image Resizing. Plus, an introduction to how the online payments ecosystem works.
Content Aware resizing arises when you want to change the height and width of your image without distorting the picture.
One algorithm that solves this is the Seam Carving Algorithm, where you find the seam (continuous sequence of pixels) with the lowest contribution to the image content and then carve (remove) it.
Finding the best seam is a computationally expensive task, and can be implemented efficiently using dynamic programming.
This is a fantastic article that goes through the algorithm and approach.
This is by Google Developers, so it specifically covers Google Pay but the concepts translate over to other payment platforms / digital wallets.
As a refresher, here’s the last question
Write a function that adds two numbers.
You cannot use + or any arithmetic operators!
I got a TON of questions around how to calculate the time complexity for yesterday’s solution.
Therefore, I’ll dedicate today’s solution to break the time complexity calculation down further.
To reiterate, here’s the Python 3 solution to the interview question.
def add(a, b): if a == 0: return b if b == 0: return a # Addition Part addition = a ^ b # Carry Over Part carryOver = (a & b) << 1 return add(addition, carryOver)
If you’d like to see the explanation for why this code works, you can read yesterday’s email.
So, in terms of calculating the time complexity of this function, we first have to answer the question of when the function will terminate.
We can simplify the base case a bit by removing
if a == 0: return b.
So, here’s the new Python function for add…
def add(a, b): if b == 0: return a # Addition Part addition = a ^ b # Carry Over Part carryOver = (a & b) << 1 return add(addition, carryOver)
This function will still work, since if
a == 0 and
b != 0 then
the Addition Part will result in the
additionvariable being equal to
0 ^ n) = n.
the Carry Over Part will result in the
carryOvervariable being equal to 0 since
(0 & n) << 1will always result in 0.
Therefore, if we call our function with
add(0, n) where n is any integer, the next function call will be
add(n,0) which will hit our base case.
So, our function’s base case is that it will terminate when
b == 0 where our function is called with
Also, the recursive call in our function (last line) is
In other words, our function will terminate when the
carryOver is 0.
So, we can bound our time complexity by calculating the maximum number of carry overs our function will have to do!
So, what kind of input results in a large number of carry overs?
Well, if we look at Base 10, that would be an input like 999 + 999.
This would result in a carry over for every digit (3 carryovers).
It is impossible to have more carry overs than 3 since we only have 3 digits in our largest input.
Therefore, the number of carry overs is bounded by the number of digits in
We can calculate the number of digits in a number by taking it’s logarithm. The number of digits in
n is equal to
floor(log(n)) + 1.
Therefore, our time complexity is
Please feel free to reply if you have any further questions!
You are given a binary tree in which each node contains an integer value. The integer value can be positive or negative.
Write a function that counts the number of paths in the binary tree that sum to a given value (the value will be provided as a function parameter).
The path does not need to start or end at the root or a leaf, but it must only go downwards.
We’ll send a detailed solution tomorrow, so make sure you move our emails to primary, so you don’t miss them!
Gmail users—move us to your primary inbox
On your phone? Hit the 3 dots at the top right corner, click "Move to" then "Primary"
On desktop? Back out of this email then drag and drop this email into the "Primary" tab near the top left of your screen
Apple mail users—tap on our email address at the top of this email (next to "From:" on mobile) and click “Add to VIPs”