Hey Guys,

Here’s your Industry News and Interview Problem for the day!

Industry News

US Supreme Court rules in favor of Google for API use

After a decade long battle with Oracle over the copyright status of Java APIs, the United States Supreme Court has sided with Google on the issue.

The case was based on Google’s implementation of the Java API for the Android platform.

Google first approached Sun about licensing the Java libraries for use in Android, but those talks fell apart because Sun had requested shared control of Android.

Google then independently implemented the Java API, but while doing so they copied Java’s method names and argument types (so you don’t have to learn an entirely separate API).

Google’s cleanroom version of Java SE became the engine behind Android’s Dalvik virtual machine, a core part of the system.

Oracle later acquired Sun and then sued Google, arguing that Google has infringed Sun’s copyright by copying the Java API’s structure.

The questions being considered were

1. Whether Google’s use of the Java API constituted fair use

2. Can Oracle copyright an API’s method names and structure

The Supreme Court has ruled that Google’s use constituted fair use, but they didn’t provide clear guidance on whether Oracle could copyright an API in the manner they wanted to.

Waymo CEO John Krafcik steps down

Waymo is a self-driving car company that is a part of Alphabet (the parent company of Google).

The company has been going through a rough patch as it’s failing to meet the high expectations set in prior years.

Waymo previously expected their self driving taxi service to have been a big business by now, with the company predicting that they would have 82,000 vehicles on the road by now. Currently, they have around 600 vehicles in operation.

Krafcik will be succeeded by Dmitri Dolgov and Takendra Mawakana, pair of Waymo executives who will serve as co-CEOs.

Dmitri Dolgov was previously Waymo’s CTO and he’s been part of Google’s self-driving car project since 2009.

Takedra Mawakana was Waymo’s Chief Operating Officer and joined the company in 2017.

Interview Question

You are given a function rand5(), which generates a random number between 0 and 4 inclusive (each number is equally likely to be generated).

Use that function to write a rand7() function, that generates a random number between 0 and 6.

Each of the numbers must have an equal probability of being generated.

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

Given two arrays of integers, compute the pair of values (one value in each array) with the smallest (non-negative) difference.

Return the difference.

Example

Input - [1, 3, 15, 11, 2], [23, 127, 235, 18, 9]

Output - 2

Explanation - The difference between 11, 9

Solution

The brute force way of solving this is to iterate through our first array.

Then, for each element of our first array we iterate through the second array and keep track of the smallest, non-negative difference we’ve seen.

The time complexity is O(n*m) where n is the length of the first array and m is the length of the second array.

Can we do better?

A faster solution would be to sort both lists.

That will take O(n log n + m log m) time.

Now, we can use the two pointer method to find the smallest non-negative difference.

We create two pointers (p1 and p2) where p1 points to the first element in the first array and p2 points to the first element in the second array.

We take the absolute value of the difference between p1 and p2 and store that as our minimum non-negative difference.

Now, we compare the value at p1 vs. the value at p2.

If the value at p1 is larger than the value at p2, then moving p1 to the next larger position doesn’t make sense since the value at p1 + 1 will be larger than the value at p1 (and will only increase our difference).

Therefore, we’ll move our p2 pointer forward by one.

On the other hand, if the value at p1 is less than or equal to the value at p2, then we’ll move the p1 pointer forward by 1.

After moving one of the pointers, we’ll recalculate the absolute value of the difference and see if it’s less than our current minimum difference.

Once we reach the end of one of the arrays, we’ll be finished!

Here’s the Python 3 code.

The time complexity is O(n log n + m log m) because we’re sorting both arrays.