☕ Google flexes hard

Good Morning Planet Earth!

Hope you’re all having an awesome day!

Here’s your interview problem and industry news.

Interview Problem

You are given a linked list as input. Determine if it has a cycle in it.

Can you do this using O(1) extra space?

We’ll send out the solution (with working code & 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

• LinkedIn Redesign - LinkedIn is the professional networking site that now boasts more than 700 million registered users. They’ve recently unveiled a brand new redesign of their desktop and mobile apps, the first in four years. LinkedIn is unveiling several new things

  • Stories - ephemeral video and photo narratives that were originally started by Snapchat and have since become popular on Instagram and Facebook.

  • Integration with Zoom, BlueJeans, Teams - LinkedIn is bringing Video Chat into it’s Messaging Service.

  • Edit, Delete Messages in LinkedIn Messaging Service.

  • Better LinkedIn Search - LinkedIn’s Search Feature will now also include jobs, courses, events and other content in addition to people and companies.

• Google will no longer allow apps to circumvent Play Store’s Payment System - Google has a policy of taking a 30 percent cut of payments made within apps offered by the Google Play store, but many developers (including Netflix and Spotify) bypassed the requirement by prompting users for a credit card to pay them directly. The developers would then rely on a different payment infrastructure provider (like Stripe) to process payments instead of going with Google. This let them avoid Google’s 30% tax on all payments, and they instead had to pay 2.9% (standard credit card processing fees). Google has announced a new policy change where apps are no longer allowed to do this. They must use the Google Play Store’s payment system, which means they must pay the 30% tax.Many developers are obviously unhappy with the 30% tax demanded by Google (and Apple for the iOS App Store) and argue that they have no choice but to pay these fees due to Google and Apple’s duopoly over the smartphone ecosystem. Epic Games (creators of Unreal Engine and Fortnite) are one of the most vocal about this, and Epic is currently involved in legal action against both Google and Apple.

Previous Solution

As a refresher, here’s the previous question

You’re given a sorted array of integers as input (sorted in ascending order).

Convert the array to a height balanced BST.

Solution

When you’re looking to solve a tree related question, your first thought should be around recursion. Is there a way that recursion can help you here?

We want to create a height-balanced BST, so if we start with the first item in the list and create a node, and continue down… we’ll end up with a tree that looks like a linked list. Searching for elements will take O(n).

Instead, we should start with the middle of the list. Then, we have an (approximately) equal number of elements that will go on the right and the left.

We create a new node where the value is equal to the middle node. This will be our root node.

Then, we recursively call our createBST function to create BSTs for the items that are to the left of the middle node and another BST for the items that are to the right of the middle node.

Then, we set the root’s left pointer to the left BST and the right pointer to the right BST.

Then, we can just return the root.

The base case is if the given list is empty. Then we can just return None.

Since slicing a list takes O(s) time (where s is the length of the slice), we’ll be doing this process by just keeping track of low and high indices. This way, we don’t have to keep taking slices of the list.

You can view the Python code with test cases here.