☕ Google Interview Question
Bitcoin reaches a new all time high, Google unveils a BERT model pre-trained on 17 Indian languages and CoachHub raises a lot of money.
Hi Everyone!
Hope you’re all having a fantastic day!
Tech Dive
Our next tech dive will be on the basics of Distributed Systems!
With microservices being all the rage, distributed computing is more important now than ever!
We’ll be talking about the challenges that come about when you’re working with a distributed system and the potential solutions.
It’ll come out on Monday!
Our last tech dive was on Database Sharding!
Snippets
Bitcoin reaches a new all-time high! The price of Bitcoin has now topped $23,000 dollars. Cue music. The Winklevoss twins wrote a pretty interesting article on Bitcoin a couple of months ago (back when it was ~$11,000) making the case for $500k a bitcoin. The main thesis is that inflation will increase in the coming years and that bitcoin is the best asset class to protect against it (compared to gold or other traditional inflation hedges).
Google unveils MuRIL, a BERT model pre-trained on 17 Indian languages. The model is trained on corpora from Wikipedia and Common Crawl for 17 Indian languages.
CoachHub raises $30 million dollars in their Series B. They develop a product that uses an AI-based matching system (hmmm) to recommend coaches for an individual where coaches teach skills like leadership or stress management. They’ve gone the B2B route with this product (whereas most similar products go B2C) and it seems to have worked well for them.
Interview 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 ).
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
You are given a non-negative number n.
Count the number of primes less than n and return the count.
Here’s the question in LeetCode.
Solution
There are quite a few Prime Number Sieves conceived to quickly find prime numbers.
One of the most efficient is the Sieve of Eratosthenes.
Here’s a fantastic explanation of how the sieve works.
We implement the sieve using an array of booleans.
We set all the booleans to True as we start by assuming every number is prime.
Then, we use a for loop to iterate through all the values from 2 to sqrt(n).
For every prime number we encounter ( the value in the array has not been set to False), we iterate through all the multiples of that prime number. We mark each multiple as False (marking it as a composite number).
At the end, we can get the count by counting the number of True booleans. This can be done with the sum function.