Hi Everyone!

Hope you’re all having a great day!

Here’s your Interview Problem, Yesterday’s Solution and Tech Snippets for the day!

Tech Snippets

• An awesome article that goes through race conditions in NodeJS

  • A race condition happens when multiple processes or threads are accessing the same shared resource, and at least one of them is trying to modify that resource.

  • Race conditions result in inconsistent behavior.

  • NodeJS has a single-threaded event loop, but race conditions are still possible.

• Wingcopter raises $22 million for delivery drone production

  • Wingcopter is a Germany-based drone manufacturer. Their drones are used for drone delivery and mapping/inspection (data collection).

  • The commercial drone market is rapidly accelerating, with reports that the industry will grow more than fivefold by 2026.

  • Wingcopter was founded in 2017 and focuses on the delivery of medical goods, packages and foods.

  • They are currently building a drone delivery network in Malawi (country in southeastern Africa).

  • Their drones can reach speeds of 150 miles per hour and carry payloads weighing up to 13 pounds. They have a range of up to 75 miles.

Interview Question

Design a Skiplist data structure without using any built-in libraries.

A Skiplist is a data structure that takes O(log n) for insertion, deletion and search.

Here’s a great article on Skiplists.

The data structure behind a Skiplist is a linked list.

Here’s the question in LeetCode

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 previous question

You are given an array of integers containing n + 1 integers.

All the integers in the array are in the range [1,n]

There is only one repeated number in the array.

Return this repeated number in the most efficient way possible.

Here’s the question in LeetCode.

Solution

We can solve this question in linear time with constant space (we cannot modify the input array).

The insight necessary is to realize that this question is an exact parallel of finding the start of a cycle in a linked list.

You can view that question on LeetCode here.

You can reframe the array as a linked list where each number in the array indicates the next pointer. The current index points to the index at the number in the slot.

Here’s an example…

The array [1, 2, 3, 4, 2] represents the linked list

Our goal is to find the start of the linked list’s cycle, which represents the repeated integer in the array.

We can solve this with Floyd’s Cycle Detection algorithm.

We have a slow and fast pointer and iterate both of them through our array (with the fast pointer going twice as fast as the slow pointer).

When they intersect, we’ve found our cycle.

Then, we start the slow pointer at the start of our list and continue iterating both pointers through the array (although this time, the fast pointer goes at the same speed as the slow pointer).

When they intersect, that element is our repeated number!

Here’s the Python 3 Code

Best,

Arpan