# ☕ 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 `k`

th 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.

## Create your profile

## Only paid subscribers can comment on this post

Log in## Check your email

For your security, we need to re-authenticate you.

Click the link we sent to , or click here to log in.