☕ The Future of Quantum Computing

Hey Everyone,

Hope you’re all having a fantastic day!

Today’s interview question is from Facebook.

The previous solution is on finding string isomorphisms.

Tech Snippets

Architecture All Access is a fantastic series by Intel that goes into depth on various topics in computer architecture.

Their past videos were on

Their video on Quantum Computing goes into

  • Quantum Superposition and Quantum Entanglement

  • How Quantum Computing can help with the Protein Folding problem

  • The engineering behind Quantum Computers

  • This is an awesome blog post by Andrej Karpathy (director of AI/Autopilot at Tesla)

  • It goes into

    • Creating a private, public key pair using Elliptic Curve Cryptography and also deriving your associated Bitcoin address.

    • Creating a Bitcoin transaction and digitally signing it.

    • Broadcasting this transaction to the Bitcoin network for validation and inclusion in the blockchain.

  • Ken Shirriff also wrote an awesome article delving into how Bitcoin mining works. You can view that here.

  • If you’re interested in the Decentralized Finance space (financial applications built on decentralized blockchains), then this is a great GitHub repo with a roadmap on how to get started.

Interview Question

Write a function that takes a string num and an integer k.

The string num represents a non-negative integer.

The function should return the smallest possible integer after removing k digits from num.

You cannot reorder any of the digits! You can only remove them.

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 a list of strings called words and a string pattern.

Return a list of the strings inside words that match pattern.

A word matches the pattern if the letters in the word can be mapped one-to-one to characters in the pattern.

Example

Input: words = ["abc","deq","mee","aqq","dkd","ccc"], pattern = "abb"Output: ["mee","aqq"]

Explanation: “mee” matches “abb” since m can be mapped to a and e can be mapped to b. The same is true for “aqq”

Solution

This question is a bit of an extension on another common interview question, which is to find if two strings are isomorphic.

An isomorphism is a one-to-one mapping (bijection) between two graphs.

In this question, our “graphs” are represented by character strings.

So, we need to find out if a one-to-one mapping can be formed between two strings.

For an example, let’s look at the strings “abb” and “mee”.

We can form a one-to-one mapping with a maps to m and b maps to e.

For “apple” and “zaapy”, we can form a one-to-one mapping with a maps to z, p maps to a, l maps to p and e maps to y.

Each character in the first string maps to only one character in the second string and vice-versa.

How can we calculate if two strings are isomorphic in O(n) time?

One way is to just iterate through both strings and try to create a mapping from the first string to the second and from the second string to the first.

If creating the mapping fails at any point, then you return False.

Here’s the Python 3 code implementing this.

Now, to answer the original question, we can iterate through the string of words and check each word to see if it’s isomorphic with our pattern.

If it is, we add it to an isomorphicWords array and then return that array after the loop terminates.

Here’s the Python 3 code.

If you want to practice more questions like this with top engineers at Google, Facebook, etc. then check out Interviewing.io.

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.

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

Check them out here.