☕ Life in the Facebook Universe

Interview Question

You are given the root node of a Binary Search Tree and a L and R value.

Return the sum of values of all the nodes with a value between L and R inclusive.

The Binary Search Tree will have unique values.

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

We’re going to do something a bit different today. There’s been a ton of releases yesterday from Facebook around VR, so we’re going to spend today just covering that stuff. Back to the usual coverage tomorrow!

• Facebook previews the new Oculus Quest 2 - The Quest 2 was released by Facebook and is looking to be the new default in VR. The price comes in at $299, $100 cheaper than the previous version of the Quest (making the Quest 2 one of the lowest-priced headsets on the market). The base model has 64 GB of storage and features 6 GB of memory. It uses the Snapdragon XR2 chipset, allowing it to take advantage of XR2-specific optimization for things like tracking cameras and VR screen resolution. Battery life is between 2 and 2.5 hours for a gaming session.

• Facebook discontinuing the Oculus Rift S - Facebook is ending sales of the higher end Oculus Rift S next spring. The “link” feature (that allows you to tether your headset to your PC and play GPU-intensive games) is now available in the Quest 2, making the Rift somewhat obsolete.

• Infinite Office and its effect on WFH - Infinite Office is a new virtual office experience for the work-from-home crowd. It allows you to be transported to a virtual office space that you can make as big as you want. You can add multiple “monitors” and can see your background projected around you through Oculus’s cameras. Or, you can change your background completely and pretend you’re in a tropical paradise.

The main downside of all this is that Facebook has recently announced that they will require Oculus users to use a Facebook Account to sign on. This is despite Facebook’s previous promises that they wouldn’t enforce this. Many Oculus users still feel slighted by the company at this and plan to switch over to another VR headset.

Previous Solution

As a refresher, here’s the previous question

Write a function to delete a node in a singly-linked list.

You will NOT be given access to the head of the list, instead you’ll be given access to the node to be deleted directly.

The node you must delete will NOT be a tail node in the linked list.

Solution

So, the traditional way of deleting a node from a singly linked list is to have access to the node right in front of the node you want to delete. Then, you set cur.next equal to cur.next.next and you can call it a day.

However, with this question, we only have access to the node that needs to be deleted.

Since this is a singly-linked list, there is no way to get the prev node.

So how can we delete this node?

We can utilize a little “hack”. We can copy over the value of the next node to the current node, and then we can just delete the next node.

You can view a REPL with the solution here.

It runs in constant time and space complexity.