☕ The newest billion dollar startup in gaming?

Hey everyone,

Hope you’re all having a fantastic day!

Here’s your interview problem and industry news for the day.

Interview Problem

Given an integer, write a function to determine if the integer is a power of two.

Try to do this in O(1) time.

We’ll send out the solution (with working code & test-cases) in our next email, 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 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”

Industry News

• Microsoft acquires Bethesda for $7.5 billion dollars in cash - Bethesda is the enormously popular gaming studio behind Fallout, The Elder Scrolls and Doom (amongst many other games). Microsoft has now acquired the company for $7.5 billion dollars. An obvious question is whether Bethesda games will now be exclusive to Xbox/PC. Microsoft has announced that they plan on honoring the PS5 exclusivity commitments for Deathloop and Ghostwire. However, for future Bethesda games, they will be on Xbox, PC and other consoles on a “case by case” basis.

• Mixpanel says that iOS 14 adoption has hit 26% five days after release - According to Mixpanel, iOS 14 adoption has hit 26% of active iPhone, iPad and iPod touch devices after only five days. This is much faster than iOS 13, which was installed on approximately 20% of active devices one week after launch. Home Screen widgets, picture-in-picture videos and the ability to set third-party browser and email apps have all encouraged users to update to the new OS.

• Playco raises $100M series A at $1B+ valuation - Playco, a Tokyo-headquartered mobile gaming startup, has announced their existence with a $100M series A at a valuation just north of $1 billion dollars. Yep, the company is at unicorn status at announcement.The problem Playco is trying to solve is how “it’s very difficult to get two people into a single game in the App Store.” There are hurdles around getting your friends to download the same app. Playco’s solution is to create games where sharing and playing them with your friends is as simple as texting them a hyperlink.Technologies that can enable this “instant play” experience are things like Cloud Gaming ( which Google is doing with Stadia), HTML5 and platform specific tools like Apple’s newly introduced App Clips.Playco thinks this will represent the next big platform shift in gaming, as social gaming creates completely new opportunities in the space.

Previous Solution

As a refresher, here’s the previous question

You’re given a list of 2-dimensional points (x, y coordinates) and an integer K.

Return the K closest points to the origin (0, 0).

You should use the Euclidean Distance Formula. If K is greater than the number of points, then just return all the points in the list. The answer is guaranteed to be unique and can be in any order.

Example

Input - [[1, 1], [-1, 0], [2,2]], K = 2

Output - [[-1, 0], [1,1]]

Solution

We’re going to go through 3 different approaches to this question, in order of least efficient to most efficient.

1. The first possible solution is to sort the input list with the key being the point’s Euclidean Distance from the origin. After you sort the input list, you can just return the first K points. The time complexity of this solution is O(N log N).

2. The second possible solution is to use a maxheap. We iterate through the list of points and push each point to our heap. The value that the heap will sort by is the Euclidean distance from the origin. If the number of points in our heap is greater than K, then we can pop out a point from the heap (that will make the size of the heap equivalent to K). Since this is a maxheap, the point that will be popped out is the point that is the farthest from the origin (compared to all the other points in the heap). At the end of the iteration, we can just return whichever points are in the heap.Insertion in a heap takes O(log A) where A is the number of items in the heap. Since our heap will never contain more than K + 1 items, pushing and popping from the heap will take O(k) time. This makes our time complexity O(N log K). This is more efficient than our previous algorithm in situations where K < N.

3. The third possible solution is to use the Quickselect algorithm. We can run Quickselect on the Euclidean distances and use it to get the K points with the smallest Euclidean Distances. The algorithm takes an average time complexity of O(N). The worst case time complexity, however, is O(N**2)You can view the solution in Python 3 here.

Thanks for reading!

If you enjoyed this, please share it with your friends! It really helps us out!