☕ Microsoft Acquisition
Microsoft is in advanced talks to acquire an extremely popular messaging platform... Plus a solution to our last Google Interview question!
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!
Industry News
Microsoft in advanced talks to acquire Discord for $10 billion or more
Discord is an extremely popular messaging platform that offers voice, text and video chatting. The company was started in 2015 as a platform that made it easy for gamers to chat while playing online games together.
They’ve since expanded to many more communities and have 140 million monthly users. They generated $130 million dollars in revenue in 2020.
Microsoft and Discord are in exclusive talks and could complete a deal next month assuming the negotiations don’t fall apart. Microsoft has been on the hunt for an acquisition that would help them reach more consumers (especially in the social space).
Last year, Microsoft was in talks to purchase the video-sharing app TikTok, but they abandoned the effort.
This could also be a strategic move to boost Microsoft’s gaming business with an integration between Discord and the Xbox platform.
Microsoft’s last big move in the gaming space was Mixer, a live-streaming platform that was meant to compete with Amazon’s Twitch. However, that was a failure and Microsoft gave up on the platform.
Tech Snippets
Figma to React is an awesome app that can convert your Figma designs to React code.
All you have to do is add a link to your figma file and it’ll code the component up for you!
Awesome blog post by Facebook engineering on scaling a distributed priority queue.
FOQS (Facebook Ordered Queueing Service) is a horizontally scalable priority queue built on top of MySQL.
Facebook relies on thousands of microservices and needs a queueing service to be able to run their workload asynchronously. FOQS helps fill that role.
Interview Question
Imagine you have a 100 gigabyte file with one string per line.
The string consists of integers.
How would you sort all the integers in the file?
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’re given an infinite complete binary tree.
Every level of the tree is filled with values from 1 to infinity.
However, the ordering of the nodes has been flipped for even numbered rows, where they go from largest to smallest.
Given the label of a node in this tree, return the labels in the path from the root of the tree to that row.
Example
Input: 14
Output: [1, 3, 4, 14]
Can you solve this in O(log n) time?
Here’s the question in LeetCode.
Solution
You first instinct might be to think of some kind of tree traversal or binary search algorithm.
But, that’s actually wrong.
You don’t need to interact with a binary tree data structure to solve this question!
Instead, try and work backwards.
We’re at the label node, but can we figure out what the parent node is based off the properties of a complete tree?
We can find what level of the tree we’re in by taking int(log(label)) where it’s log base 2. The first level will be level 0.
If our level is even, then the nodes will be ordered from smallest to largest. If our level is odd, then they will be ordered from largest to smallest.
Therefore, we can calculate the label of the first node in our level. If we’re on an even level, then our first node is 2**(level). Otherwise, the first node is 2**(level + 1) - 1.
Now that we have the first node, we can find our current node’s position in the level by subtracting label and first.
Given the current node’s position, our parent node’s position (in its own level) will be the current node’s position divided by 2 (rounded down). That is a property of complete binary trees.
Now, we have to find the first node in our parent node’s level and then we can add our parent node’s position (or subtract, depending on if the parent node’s level is even or odd) to find the parent node’s label.
Now, we repeat the same exact process until we come to our root node, which has the label 1.
While doing the process, we’ll append our labels on to an array that will keep track of the path.