InstaByte
Posts
🧠 Must-know algorithm for interviews

🧠 Must-know algorithm for interviews

ALSO: How to design WhatsApp

InstaByte
May 01, 2024

Welcome back, Interview Masters!

Today's coding challenge uses an algorithm that every programmer must know.

In today’s newsletter, we’ll cover:

Find Minimum in Rotated Sorted Array
How to design WhatsApp?

Read time: under 5 minutes

`CODING CHALLENGE`

Find Minimum in Rotated Sorted Array

Medium Goldman Sachs Microsoft Google eBay

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:

[4,5,6,7,0,1,2] if it was rotated 4 times.

[0,1,2,4,5,6,7] if it was rotated 7 times.

Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Given the sorted rotated array nums of unique elements, return the minimum element of this array.

You must write an algorithm that runs in O(log n) time.

Example 1:

Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.

Example 2:

Input: nums = [4,5,6,7,0,1,2]
Output: 0
Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.

Example 3:

Input: nums = [11,13,15,17]
Output: 11
Explanation: The original array was [11,13,15,17] and it was rotated 4 times.

Solve the problem here before reading the solution.

`SOLUTION`

We can use Binary Search to solve this problem.

Compare the middle element of the array with the last element. If the middle element is greater than the last element, it means the minimum element lies in the right half of the array. Otherwise, it lies in the left half.

Since we are using Binary Search, the time complexity of this solution is O(log n).

`SYSTEM DESIGN EXPLAINED`

How to design WhatsApp?

Image credit: Beata Zawrzel

We can use microservice architecture to divide tasks like user management and chat functionality into independent, scalable services.

To ensure messages are delivered quickly, we’ll use real-time bi-directional connections with WebSockets. For offline users, messages are queued and then delivered via push notifications.

To implement the last seen functionality, we can use a heartbeat mechanism, where the client can periodically ping the servers indicating its liveness.

Scalable object storage will handle media files, while a Content Delivery Network ensures fast loading of static content. You can read the full article here.

`NEWS`

This week in the tech world

Image credit: Timmy Loen

Google restructures, cuts jobs: Google lays off 200 employees, mostly engineers, in a restructuring. Some positions are being moved to India and Mexico.

Tesla cuts Supercharger team: Tesla lays off 500 employees to cut costs and slow down Supercharger network expansion. Stock price dropped after the news.

AI competition heats up: Amazon-backed Anthropic launches AI app to compete with OpenAI’s ChatGPT. Their large language model is now available on iPhone and for businesses

Bitcoin falls below $57,000: Bitcoin’s price fell to its lowest level since February after the Federal Reserve left interest rates unchanged. Investors are concerned about rising interest rates and inflation.

Amazon profit margin at record high: Amazon’s profit margin has increased to double digits for the first time, driven by cost cuts and a focus on higher-margin businesses. Revenue growth has slowed, but operating income tripled in the first quarter.

EU probes Meta over disinformation: Meta is being investigated by the EU over concerns that it is not doing enough to combat disinformation before the EU Parliament elections. The EU suspects Meta is violating the Digital Services Act by not tackling deceptive ads and inauthentic behavior.

Healthcare data breach: Millions potentially affected by Change Healthcare hack. UnitedHealth paid hackers $22 million ransom and is offering identity protection.

`POLL`

Results from last week

This one’s for you

How do you practice for interviews?

`BONUS`

Just for laughs 😏

Source: CHEEZburger

`NEXT IN CODING CHALLENGE`

3Sum

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Join us next week to find out the solution!