☕ 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.

Hey Guys,

Tech Snippets

• Content-Aware Image Resizing in JavaScript

  • 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.

• A cool introduction to how online payments work

  • This is by Google Developers, so it specifically covers Google Pay but the concepts translate over to other payment platforms / digital wallets.

Previous Solution

As a refresher, here’s the last question

Write a function that adds two numbers.

You cannot use + or any arithmetic operators!

Solution

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 addition variable being equal to b since (0 ^ n) = n.

• the Carry Over Part will result in the carryOver variable being equal to 0 since (0 & n) << 1 will 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 add(a, b).

Also, the recursive call in our function (last line) is add(addition, carryOver).

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 max(a, b).

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 log(max(a, b).

Please feel free to reply if you have any further questions!

Interview Question

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”