🚗 Can you crack this Uber problem?

Welcome back, Interview Masters!

Today’s coding challenge will be a true test of your skills.

In today’s newsletter, we’ll cover:

• Maximum Product Subarray

• How Yelp moderates inappropriate video content

Read time: under 5 minutes

CODING CHALLENGE

Maximum Product Subarray

Given an integer array nums, find a subarray that has the largest product, and return the product.

Example 1:

Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

Example 2:

Input: nums = [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

Solve the problem here before reading the solution.

SOLUTION

To solve this problem, we will use Dynamic Programming. 

We'll maintain two variables: one for tracking the maximum product ending at the current index and another for tracking the minimum product ending at the current index. 

The maximum product can be obtained by multiplying a positive number with the maximum product or multiplying a negative number with the minimum product. That’s why we are keeping track of both.

At each index, we update these two variables based on whether the current number is positive or negative. 

The maximum product can either be:

1. The current number itself,

2. Or the current number multiplied by the maximum product ending at the previous index,

3. Or the current number multiplied by the minimum product ending at the previous index. 

Similarly, the minimum product can be:

1. The current number itself,

2. Or the current number multiplied by the maximum product ending at the previous index,

3. Or the current number multiplied by the minimum product ending at the previous index.

We also keep track of the overall maximum product seen so far and update it at each index.

The time complexity of this algorithm is O(n), where n is the number of elements in the nums array. 

PRESENTED BY 1440

Get the facts, not opinions. 1440 delivers.

Overwhelmed by biased news? Cut through the clutter and get straight facts with your daily 1440 digest. From politics to sports, join millions who start their day informed.

SYSTEM DESIGN EXPLAINED

Moderating inappropriate video content at Yelp

Yelp allows users to upload videos alongside reviews. To protect users from inappropriate content, Yelp uses a combination of AI and human moderators.

An AI model analyzes uploaded videos and assigns a score. Videos exceeding a certain threshold are flagged for human review.

The system prioritizes minimizing incorrect removals ("false positives"). Human reviewers assess flagged videos and restore any mistakes.

Processing videos takes time, so Yelp uses techniques to reduce the load on the AI model. These include blocking repeat offenders and strategically selecting frames for analysis.

Yelp leverages its existing photo moderation model to streamline video processing. You can read the full article here.

NEWS

This week in the tech world

Google Fires After Protests: Google has fired over 50 employees following a series of protests across multiple offices. The fired employees were protesting against the cloud-computing contract with the Israeli government.

TikTok Ban in the US: U.S. Senate passed a legislation giving TikTok's Chinese owner, ByteDance, about nine months to divest the U.S. assets. Once Biden signs the bill, a 270-day clock starts during which ByteDance must sell TikTok.

Bitcoin Miners Brace for Halving: The recent halving of Bitcoin, which cuts the issuance of new bitcoins in half, is expected to decrease miner revenue. As a result, miners are upgrading their facilities to become more efficient, or finding new revenue streams. Bitcoin price has historically risen after halving events, but the impact of this halving is uncertain.

Microsoft's Tiny AI Model: Microsoft launches Phi-3, its smallest AI model yet. Phi-3 Mini measures 3.8 billion parameters, making it smaller and cheaper to run than other models. It is still capable of performing complex tasks, like GPT-3.5. Microsoft plans to release two larger versions of Phi-3: Phi-3 Small (7B parameters) and Phi-3 Medium (14B parameters).

Apple Bets Big on India: Apple is looking to diversify its manufacturing base and is increasing its presence in India. The company is now making 14% of its iPhones in India, and its CEO visited the country in 2023.

Meta's Stock Falls 16%: Meta’s Q1 2024 earnings per share beat expectations by 9%, yet the stock price plunged 16%. Strong revenue and net income growth were overshadowed by a disappointing Q2 revenue forecast. Investors are also concerned about profitability in Meta's AI and Metaverse ventures.

Salesforce Acquisition Falls Through: Salesforce's attempt to acquire Informatica for $10 billion was unsuccessful due to disagreements on terms and resistance from both Informatica's shareholders and Salesforce's investors.

POLL

Results from last week

This one’s for you

OPEN SOURCE

If you’re interested in open source software, check out Neosync. NeoSync is an open source platform that anonymizes sensitive production data. It also generates synthetic data to make it safe for use in non-critical systems. This helps companies stay in compliance with local data privacy regulations and data security best practices.

Star NeoSync’s Github repo now to show some love for open source 💙

BONUS

Just for laughs 😏

NEXT IN CODING CHALLENGE

Find Minimum in Rotated Sorted Array

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.

Join us next week to find out the solution!

REFER FOR THE WIN

👋 Hey! Share your referral link with friends to unlock Hidden Treasures:

📌 Your referral link: https://www.interviewmaster.io/subscribe?ref=PLACEHOLDER

Share your referral link on LinkedIn or with your friends to unlock the treasures quicker.

YOUR FEEDBACK

Reviews of the week

Until next time, take care!

Cheers,

Sahil + Sarra