Hey Guys,

Interviewing.io is a fantastic resource I wanted to share with you all.

You can book realistic mock interviews with senior FAANG engineers who will give you detailed and actionable feedback on exactly what you need to work on.

Mastering algorithms on LeetCode and system design on SystemsExpert is great, but they don’t prepare you for the pressure and stress that comes from an actual interview setting.

The best part?

You don’t pay anything until you’re hired.

Check them out here.

Special thanks to Interviewing.io for sponsoring Quastor Daily. I’m a user of the service!

Tech Snippets

• Making an AI powered Linux Shell with OpenAI’s GPT-3

  • A hilarious video on using GPT-3 to create a program that can take in natural language commands and turn them into shell commands.

  • Example - find all files ending in .log in /var/log turns into find /var/log -name “*.log”

  • Here’s the blog post.

• Internet Search Tips

  • If you haven’t heard of Gwern’s blog, you’re seriously missing out. It’s some of the best content on the web.

  • Being good at using Google (or whatever search engine you prefer) is obviously an incredibly important skill for a programmer.

  • Gwern goes through some great tips on how you craft better search engine queries.

Interview Question

You are given n non-negative integers that represent the height of an elevation-map. The width of each bar in the map is 1.

Compute how much water would be trapped in the elevation map after a rainstorm.

Here’s the question in LeetCode.

Example

Input: [0,1,0,2,1,0,1,3,2,1,2,1]

Output: 6

Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

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”

Previous Solution

As a refresher, here’s the last question

You are given an array with all the numbers from 1 to N appearing exactly once, except for one number that is missing.

How can you find the missing number in O(n) time and O(1) space?

What if there are two numbers missing?

Solution

Let’s start with just one number missing.

We can solve this by doing some sort of computation with the values in the given array.

Then, we can do that same computation on the values for all the numbers from 1 to N.

After, we can compare the results from both computations and use that to figure out which number is missing.

The result of the computation must uniquely correspond to the specific numbers used.

One computation we could do is just take the sum of all the numbers.

We take the sum of all the numbers in the array we’re given.

Then, we take the sum of all the numbers from 1 to N.

We subtract the second sum minus the first sum and that’ll give us the missing number.

We can do this in O(N) time and using constant space.

Now, what if two numbers are missing?

Let’s say the two missing numbers are represented by n1 and n2.

If we repeat the process we did with sums, then we’ll know what the sum of n1 + n2 is.

Unfortunately, that isn’t enough information to figure out exactly what n1 and n2 are.

But, we could incorporate another computation that gives us more information about n1 and n2.

We could use multiplication.

We multiply all the numbers in the array we’re given and find the total product.

Then, we multiply all the numbers from 1 to N and find that total product.

Then, we divide the second product by the first product and that will give us n1 * n2.

Now, we use some algebra (with n1 * n2 and n1 + n2) to create a quadratic equation that will give us the value of n1 and n2.

Here’s the Python 3 code.

Want more practice with real FAANG software engineers?

Check out Interviewing.io!

You don’t have to pay anything until you get that job at FAANG!