Interview Question

What is Rate Limiting in the context of System Design?

Why might it be necessary?

How can you implement it in your system?

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

• Uber and Lyft win big in California with Proposition 22California voters voted yesterday on Proposition 22, a ballot measure that would exempt drivers for app-based transportation and delivery companies from being classified as employees. In case you haven’t been following the action, here’s the series of events…Now, Proposition 22 has been voted in by California voters, thus exempting ride-share and food-delivery companies from the law. Based off polling data, the vast majority of ride-share/food-delivery drivers heavily support Prop 22 and are against AB5.

  • In January 2020, a California law called AB5 went into effect. That law requires most workers that do jobs that are part of a company’s normal operations to be classified as employees rather than independent contractors. This gives them benefits like minimum wage, unemployment insurance and other legal protections.

  • Many companies (not in the ride-sharing business) had issues with this. Media organizations threatened to lay off thousands of journalists in California who previously worked as independent contractors. Many private practices in the medical space also employed doctors and dentists as independent contractors, so this would threaten them as well. Many exemptions were then added to the AB5 law in response.

  • Seeing this, Uber, Lyft and Doordash file Proposition 22, a measure that exempts delivery and ride hail companies from AB5.

• Onfleet raises $14 million dollars to provide last-mile delivery tools to third partiesOn the “food delivery” trend, Onfleet is an incredibly interesting company that tries to give companies a way to compete against Doordash/Instacart in the delivery space.Onfleet has built a routing and dispatch platform to manage the delivery process between a store, restaurant and customer. A grocery chain, for example, can use Onfleet’s software to manage their last-mile grocery delivery service. Or, companies can use it higher up the chain and have Onfleet coordinate warehouse shipments to stores.One feature Onfleet provides is an “auto-dispatch” engine, which can assign delivery jobs to drivers based on their availability and proximity. It will then calculate delivery routes based on traffic conditions, time and location. Dispatchers can also communicate directly with their drivers through Onfleet’s app, negating the need for third-party chat apps. Onfleet has now raised a $14 million dollar series A round with Kennet Partners. The raise comes as demand for e-commerce and delivery services has gone through the roof.

Previous Solution

As a reminder, here’s the previous question

You are given a string with parentheses and lowercase English characters.

You must remove the minimum amount of “(“ or “)” in any position so that the resulting parenthesis string is valid and return any valid string.

A parentheses string is valid if and only if

• It is the empty string or only contains lowercase characters

• It can be written as AB where A and B are valid strings

• It can be written as (A) where A is a valid string.

Here’s a link to the question on Leetcode.

Solution

1. Strings are immutable in Python, so we have to convert the string to a list.

2. Create an empty stack and then iterate through the list

   1. If we come across an open parenthesis, we’ll add the current index to the stack

   2. If we come across a closed parenthesis, then we’ll pop an item from the stack. If the stack is empty, then we’ll just set the current item in the list to the empty string.

3. Go through all the remaining indices in the stack. All these indices don’t have a closing parenthesis, so we set them all to the empty string in the original list.

4. Concatenate the original list to form your new string

Here’s the Python 3 code.