☕ Facebook Interview Question
We talk about using ML to curate Biology Studies, Self-driving cars and Ripple! We also give a detailed solution to our last Google Interview Question.
Hi Everyone!
Hope you’re all having a fantastic day!
Tech Dive
Our last tech dives were on Distributed Systems and Database Sharding!
Snippets
Lex Fridman talks to the CTO of Waymo (Dmitri Dolgov) about V2V communication with self-driving cars. V2V communication is where cars in Waymo’s self-driving fleet can talk to each other.
Currently, Waymo’s cars will share information about mapping and the real world with the rest of the fleet ( car accidents, road obstructions, construction zones, etc.). This helps with handling dynamic information that can’t be preconfigured.
V2V communication is not required for self-driving however. Waymo cars are able to drive completely independently.
Industry News
Using ML to curate Biological Studies?
Curating biological studies is a very labor-intensive process performed by researchers in life science fields. Curators must recognize experiment methods and identify the research protocols used to get the figures published in the research papers.
Researchers at UCLA have now published a new dataset with the goal of automating this process. MELINDA - A Multimodal Dataset for Biomedical Experiment Method Classification is a dataset with over 5,371 labeled data records.
The input labels consist of a figure from a research article and an associated caption. The output label is the experiment methodology used in that paper. The dataset comes from PubMed Central, an archive of freely available life science journals.
Researchers achieved the best results with a multimodal model, VL-BERT, that achieved between 66.49% and 90.83% accuracy. This is still quite far from the 100% accuracy that can be achieved from humans.
SEC charges Ripple with conducting a $1.3 billion dollar unregistered securities
The Securities and Exchange Commission has sued Ripple Labs, the creators of the XRP cryptocurrency, with a lawsuit alleging that Ripple has raised $1.3 billion dollars in unregistered securities offerings (for XRP).
The exact definition of a security is a bit hazy, but anything that the SEC requires that a security must be registered with the SEC before being sold to investors. The SEC is claiming Ripple Labs didn’t register XRP when they sold it to the public.
XRP was the third-largest cryptocurrency at the time of the lawsuit with a market cap of over $20 billion US dollars.
Interview Question
You are given a string s and an array of strings words of the same length.
Given two strings s and t, return the minimum window in s which will contain all the characters in t. If there is no such window in s that covers all characters in t, return the empty string "".
Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"Here’s the question on LeetCode.
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 previous question
The set [1, 2, 3, …, n] contains a total of n! permutations.
You can arrange these permutations in order from smallest to largest.
For n = 3, the permutation sequence is
“123”
“132”
“213”
“231”
“312”
“321”
Given n and an integer k, return the kth permutation sequence.
For n = 3 and k = 2, the kth permutation sequence is “132”.
Find the most efficient solution ( better than O(n!) time-complexity ).
Here’s the question on LeetCode.
Solution
The brute force solution would be to enumerate all permutations. Then, you return the kth sequence. Can we do better?
First, it’s important to understand why a sequence of n items can be ordered in n! ways.
When you want to find the number of orderings for n items, you have n possible slots to place the items in.
For the first slot, you have n choices.
For the second slot, you have (n - 1) choices.
You have (n - 2) choices for the third slot and so on.
The last slot will have 1 choice, which is the last remaining item.
You can find the total number of choices by multiplying the number of choices at each slot together.
The total number of choices = n * (n - 1) * (n -2) *…* 1 or n!.
If you want to find the number of orderings for (n-1) items, then it will be (n-1)!.
So, we have a sequence of numbers of [1,2,…, n] and we want to find the kth sequence.
How many sequences start with 1?
Well, if we pick 1 for the first slot, then there are (n-1) remaining numbers. That means that there are (n-1)! sequences that start with 1.
If k is less than (n-1)!, then we know that the kth sequence starts with 1.
If k is greater, then we can check the sequences that start with 2, the next (n-1)! sequences.
Once we figure out the first digit for the kth sequence, then we can apply the same logic for the second digit.
How many sequences start with “1” and then have a “2”?
It would be (n-2)! since we’ve picked the first two slots.
We can keep doing this recursively to find the kth sequence.
The way we code it is with a while loop.
We find the first digit by dividing k by n!.
The quotient tells us what the digit will be and the remainder gives us the value of k for the remaining digits.
We continuously repeat this process until we've filed up all the slots in our permutation of n digits and identified the kth permutation.