☕ CryptoKitties

Hey,

Hope you’re having an awesome day!

On to the Interview Problem and Industry News!

Interview Problem

A number is sparse if there are no adjacent ones in it’s binary representation.

For example, 341 is sparse since it is 101010101 in binary.

342 is not sparse since it is 101010110 in binary.

For a given input K, find the smallest sparse number that is greater than or equal to K.

Try to do this in faster than O(N log N).

We’ll send a detailed solution with test cases 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 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

CryptoKitties Team raises $18 million in Crypto Token Sale

In the crypto space, one area that’s been growing exponentially is the NFT industry. NFT stands for non-fungible token and sales per week have soared to more than $1 million dollars.

A non-fungible token is a special type of token which represents something unique (hence “non-fungible”) and is therefore not mutually interchangeable. This is different from bitcoin, where one bitcoin is the same as any other value-wise. These NFTs are used to create verifiable digital scarcity and digital ownership. They’re being used in applications that require unique digital items like crypto art (rare art) and crypto gaming. The fantasy soccer game Sorare lets players collect “limited edition digital collectibles” while managing a team and uses NFTs to implement this.

News of NFTs went mainstream when CrptoKitties went viral. CryptoKitties is a blockchain game on Ethereum that lets players purchase, collect, breed and sell virtual cats. The game’s massive popularity in December 2017 congested the Ethereum network, causing it to reach an all-time high in transactions and slowing the network down significantly.

Now, the team behind CryptoKitties, Dapper Labs, is back and they’ve raised $18 million dollars in a Flow Crypto Token sale from nearly 13,000 participants. What Dapper Labs is trying to do is to replace Ethereum entirely for the NFT market with their own blockchain, Flow. Slow transaction speeds and high speeds have encumbered the NFT market on Ethereum and especially hurt projects trying to sell cheaper NFT items, such as in-game microtransactions. Dapper Labs is trying to solve this with Flow.

McAfee will IPO

McAfee, the cybersecurity company, will be going public next week and could raise as much as $814 million dollars. That would be the top end of the price target, and would value the company at $9.5 billion dollars.

McAfee offers a large suite of products, although they’re best known for incredibly annoying pop-ups telling you to download their anti-virus software. They also develop cloud software for Enterprise customers and some other stuff where the names sound like a concoction of random buzzwords.

This is the second time the company is going public, as it was taken private in 2011 by Intel in a $7.68 billion dollar deal. In 2017, Private Equity firm TPG Capital bought a 51% stake in the company in a deal valued at $4.2 billion dollars. McAfee also began operating as a stand-alone company at that point.

The company had been unprofitable until this year, when it reported $31 million dollars in net income on a revenue of $1.4 billion dollars for the six months ending in June. McAfee is also “highly levered” (meaning they have tons of debt), so a portion of the proceeds from the IPO will go down to paying down debt. The company has more than $4 billion dollars in long-term debt.

Previous Solution

As a refresher, here’s the previous question

Given an integer K, construct all possible binary search trees with K nodes.

Solution

Whenever you see a problem relating to binary trees, your first thought should be of recursion.

Our recursive function will be make_trees. make_trees will take in a low and high value as parameters, with low being the smallest value in the BST and high being the largest value in the BST. make_trees will return an array of all the possible BSTs with values from low to high.

In make_trees, we’ll iterate through every possible root node (which is every number from low to high inclusive) and set that as the root. Then, we’ll call make_trees again for all the values from (low, root - 1) and get all the possible left subtrees. Then, we’ll call make_trees for all the values from (root + 1, high) and get all the possible right subtrees.

Then, we can iterate through the left subtree array and the right subtree array and get every possible valid BST and add it to our array. Then, we just return our array.

We can then create a wrapper function called build_trees which will take in the integer K. It will return the result of calling make_trees(1, K).

The time and space complexity is O(N * 2^N) since make_trees takes O(N) time and space to build each tree and there are an exponential number of trees.

Here’s the Python 3 code with testcases.