Hey Guys,

Hope you’re all having an awesome day!

Interview Problem

Given an N x N matrix, rotate it 90 degrees clockwise. You cannot use any extra space!

Example

Input - [ [1, 2, 3],

[4, 5, 6],

[7, 8, 9]]

Output - [[7, 4, 1],

[8, 5, 2],

[9, 6, 3]]

We’ll send a detailed solution with test cases 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 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”

Industry News

Paypal takes an interest in Bitcoin

PayPal will allow it’s ~350 million users to buy and sell bitcoin and a couple other cryptocurrencies within PayPal. However, users will NOT be allowed to transfer their BTC in or out of PayPal. They will also not have access to their private keys.

This most likely means that the way PayPal is implementing this is through a customer ledger. They simply keep track of how much Bitcoin customers own, and they just make the purchase on behalf of PayPal. PayPal will have control over the Bitcoin, but you’ll get exposed to the price movements in your account.

The company is also exploring the acquisition of cryptocurrency companies including Bitcoin custodian BitGo Inc.

A Bitcoin custodian is a company that holds on to your Bitcoin for you. Many people don’t feel comfortable keeping thousands of dollars on a USB drive or on a laptop (hardware faults will be very expensive), so they use custodians instead. Common custodians include companies like Coinbase or Gemini.

BitGo is another Bitcoin custodian and they were founded in 2013. In 2018, they raised $58.5 million dollars at a $170 million dollar valuation. The company is backed by investors including Goldman Sachs, Craft Ventures, DRW and Founders Fund.

These moves by PayPal may be in response to Square, the PayPal competitor founded by Jack Dorsey. Square has been far more bullish on Bitcoin, going to the point where a percentage of Square’s balance sheet is invested in the cryptocurrency. Square already has a feature where you can buy and sell Bitcoin in the app.

Previous Solution

As a refresher, here’s the previous question

You’re given an integer N as input.

Write a function that determines the smallest number of perfect squares that sum up to N.

Examples

Input - 16

Output - 1 (16 is a perfect square)

Input - 21

Output - 3 (1 + 4 + 16 = 21)

Solution

Your first instinct might be to go with a greedy algorithm. Find the largest perfect square that is smaller than N and subtract that. Then, recursively do the same on whatever number is left. The base case of the recursion is when N = 0 or N = 1. Then, the answer is obviously N. We must keep track of the number of squares we subtract.

So, with 10, you first subtract 9 and get 1. Then, you can subtract 1 and you get 0. Therefore the answer is 2, 10 = 9 + 1.

However, the greedy approach fails!

A counter-example is if N is 18. The largest square that is smaller than 18 is 16. Then, you’re left with 2 so that would be 2 1’s. Therefore, your answer would be 3 using the greedy algorithm, 18 = 16 + 1 + 1.

But, 3 is incorrect! The answer is 2. 18 = 9 + 9.

So, we will have to try every possible combination of squares.

We will subtract every perfect square that is smaller than N and call our function again on the difference. Every function call will return the number of perfect squares needed to reach 0 (our base case) and we’ll keep track of the minimum. Then, we’ll return the minimum + 1 (since we subtracted by one perfect square in our function).

The issue with this approach is that we have exponential time complexity. How can we improve this? By using Dynamic Programming!

We can implement a bottom up DP solution by iteratively building up a table that contains the fewest number of perfect squares to sum all the numbers from 1 to N.

Here’s the Python 3 code to do this with test cases.