Daily Interview Problem / Uber, Lyft Shutting Down in California?

Hey,

Hope you’re enjoying your day! Here’s your interview problem and industry news for the day.

Daily Interview Problem

You’re given a singly linked list as input. Group all the odd nodes together followed by all the even nodes. By odd nodes we’re referring to the node number and not the value in the node!

Do this in-place with O(1) space complexity and O(n) time complexity.

Input: 1->2->3->4->5->None

Output: 1->3->5->2->4->None

Industry News

• Uber and Lyft may shut down operations in California, if forced to classify drivers as employees - Uber CEO Dara Khosrowshahi said on Wednesday that Uber may have to close up shop in California. “If the court doesn’t reconsider, then in California, it’s hard to believe we’ll be able to switch our model to full-time employment quickly,” he said on MSNBC. Lyft said it would do the same on an earnings call with investors. Read More

• TailwindCSS has cracked 10 million total installs - TailwindCSS is a CSS framework that relies on “utility classes” and avoids the traditional opinionated styles that you get with Bootstrap or MaterialUI. They’ve exploded in popularity and have now crossed 10 million total installs. Read More

• Microsoft builds it’s own Android Smartphone with the Surface Duo - Microsoft is launching it’s Surface Duo dual-screen Android phone. The phone is priced at $1,399. The device includes two separate 5.6-inch OLED displays (1800 x 1350) with a 4:3 aspect ratio that connect together to form a 8.1-inch overall workspace (2700 x 1800) with a 3:2 aspect ratio. Read More

Daily Interview Problem Solution

The way we solve this is by utilizing “dummy” nodes. We create a dummy node that represents the odd nodes and a dummy node that represents the even nodes. Then, we iterate through the linked list and put the odd nodes into the first linked list and the even nodes into the second linked list.

You can check the code out (and run it!) using this REPL.

The time complexity is linear and the space complexity is constant.