☕ tres comas anyone?

Interview Question

Given a reference to a node in a connected, undirected graph… return a deep copy of the graph.

You can assume that each node in the graph will contain a value (int) and a list (a list of nodes) of its neighbors.

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

• Oracle wins bid for TikTok in the U.S. - ByteDance has reached a preliminary “technical partnership” agreement with Oracle for TikTok’s US operations. Oracle will address the national security concerns of the TikTok app although the structure of the deal is currently unknown. What is known is that the company will be introducing an Enterprise version of the app catering to Fortune 500 companies that want TikTok integrated into their Oracle Cloud Application Suite. Just kidding.

• Nvidia acquires ARM for $40 Billion Dollars - Nvidia will buy ARM Ltd. for $40 billion dollars, in what is perhaps the most important semiconductor acquisition ever. ARM Ltd. is based in England and they develop the ARM processor architecture. They license out the design to companies like Apple, Qualcomm and Samsung (among many others). Nvidia CEO Jensen Huang commented on the deal, saying “We're about to enter a phase where we're going to create an internet that is thousands of times bigger than the internet that we enjoy today. A lot of people don't realize this. And so, so we would like to create a computing company for this age of AI”.

• Amazon plans to buy a $20 billion dollar stake in Reliance Industries - Earlier this year, Facebook purchased a 10% stake in Reliance Jio for $5.7 billion dollars. Google announced plans to roll out a low-cost Android phone with Jio and invested $4.5 billion dollars. Now, Amazon looks to be taking an interest in the Ambani Empire with rumors of a $20 billion dollar stake in Reliance’s retail business. India is becoming an increasingly important market to these Silicon Valley companies as it’s a massive market that’s still largely untapped (by Silicon Valley’s Big Tech companies).

Previous Solution

As a reminder, here’s the last question

You are given two sorted arrays and a positive integer k.

Write a function that computes the k-th smallest element of an array that consists of the elements of the initial two arrays arranged in sorted order. Remember, you’re only given the two initial sorted arrays.

There may be duplicate elements within and across the input arrays.

Can you do better than the obvious linear time solution?

Solution

So, there’s the obvious linear time solution. You merge the two sorted arrays into a third (sorted) array and then return the answer.

One optimization would be to end the “merge” function once the combined array has k elements (then you’ve found the kth element). This results in an O(k) time complexity.

But, can we do better?

We can! Using Binary Search!

Remember, whenever you see “sorted array”s anywhere, your mind should immediately drift to binary search, and try and see if it will come in handy.

Let’s call the first sorted input array A and the second sorted input array B.

What we need is some form of binary search that takes advantage of the sortedness of A and B. What if we focus on finding the indices in A and B that correspond to the first k elements? All the elements before those 2 indices combine to form the first k elements of our combined array.

To be more specific, let’s say that the first k elements of the union of A and B consist of the first x elements of A and the first k - x elements of B. We can determine what x is by using Binary Search.

We will maintain an interval [b, t] that contains x. The iteration continues as long as b < t, with b, t corresponding to the traditional low, high.

At each iteration, we will consider the midpoint -> (b + (t - b) // 2) to be x.

If A[x] < B[(k - x) - 1], then A[x] must be in the first k - 1 elements of the union, so we can update b to x + 1 and continue.

Similarly, if A[x - 1] > B[k - x], then A[x - 1] cannot be in the first k elements, so we can update t to x - 1.

Otherwise, we must have B[(k - x) - 1] <= A[x] and A[x - 1] <= B[k - x], in which case the result is the larger of A[x - 1] and B[(k - x) - 1], since the first x elements of A and the first k - x elements of B when sorted end in A[x - 1] or B[(k - x) - 1].

If the iteration ends without returning, then it must be that b = t. In that scenario, x = b = t and we can just return the larger of A[x - 1] and B[( k - x) - 1].

Here’s a REPL with the Python 3 code.

The time complexity is O(log k).

Credits to Elements of Programming Interviews.