Good Morning Planet Earth!

Hope you’re all having a fantastic day.

Here’s your Interview Question, Daily News and Previous Solution!

Interview Question

Given a positive integer n, build a square matrix that has elements from 1 to n^2 in spiral order.

Example

Input - 3

Output -

[

[ 1, 2, 3 ],

[ 8, 9, 4 ],

[ 7, 6, 5 ]

]

Here’s a link to the question in LeetCode.

Industry News

• Ethereum 2.0 Set to Launch on December 1rstVersion 1.0 of the Ethereum 2.0 specification has been released. If all goes according to plan, the blockchain upgrade will happen at the beginning of next month.This is huge because it will move Ethereum to a Proof of Stake consensus mechanism as opposed to the previous Proof of Work. Ethereum holders will stake their coins to help run the network, instead of mining blocks. As long as there are 16,384 validators on the Proof of Stake network, it will go live on December 1rst at 12 pm UTC. Each validator must stake 32 Ethereum, which is about $209 million US dollars.We’ll send out a tech dive on Ethereum next week, so be on the lookout for that!

• DJI releases the Mini 2We’ve talked a lot about drones and how there’s a huge amount of interest from venture capitalists in the space. B2B Drone companies are raising series As left and right. In the consumer drone industry, there’s one company that’s far and away the winner. That’s DJI. Da-Jing Innovations (DJI) is a Chinese technology company headquartered in Shenzhen, a city known as the “world’s factory”. As of March 2020, DJI accounted for 70% of the world’s consumer drone market. No other company accounted for more than 5%.DJI has now released the next version of their Mavic Mini, the Mini 2

  • Price - $449

  • Weight - 249 grams - this is important because it means you don’t have to register the drone with the FAA

  • Video Resolution - 4k at 30 frames per second

  • Battery life - 31 minutes

  • Top Speed - 35.8 miles per hour

• WhatsApp now lets you post ephemeral messages that disappear after 7 daysWhatsApp is massive. They’ve now passed 100 billion messages sent per day and have more than 2 billion users on the network.Facebook is now rolling out a new feature that allows you to set your messages (including photos or videos) to disappear after 7 days. For group messages, the group admin has to enable disappearing messages for it to work.Ephemerality has been one of the most radical and sticky features in messaging in years. Snapchat, arguably, has taken off mainly due to this one feature. It’s also a major focus in privacy focused messaging applications like Signal or Telegram.This indicates that Facebook will most likely try to roll out a similar feature in their other messaging products, such as FB Messenger.

Previous Solution

As a reminder, here’s the previous question

What is Rate Limiting in the context of System Design?

Why might it be necessary?

How can you implement it in your system?

Solution

Rate Limiting is limiting the amount of operations that a user can perform in a given amount of time. An example might be limiting the amount of requests the user can send to a server at 100 requests a minute. If a user sends more than 100 requests, the server will just return an error in response.

The purpose of rate limiting is to prevent the system from failing due to a Denial of Service attack. A DOS is when an actor floods a system with requests and brings it down. Most DOS attacks are not from malicious actors, instead they’re caused by an bug in the client. These are referred to as friendly-fire DOS attacks. However, they can still bring your system down!

There are various algorithms for implementing rate limiting. They come with their own set of tradeoffs…

• Leaky Bucket - This algorithm implements rate limiting through a Queue. As requests come in, they go into a Queue which processes the requests in FIFO order. If the Queue is full, then the server will just respond to any additional requests with an error message. As the requests at the top of the Queue are processed, the data structure will get more space. Then, the server will start accepting requests again.Leaky Bucket is very intuitive and simple to implement. The issue is that a burst of traffic will fill up the queue with old requests and starve new requests from being processed. There is also no guarantee that requests get processed in a fixed amount of time.

• Fixed Window - A window of n seconds is used to track the rate. Each incoming request increments the counter for the window. Once the counter exceeds a threshold for the window, new requests will be denied. New requests will be accepted again in the next window.This solves the problem with the Leaky Bucket approach where new requests can get starved. However, a single large burst of traffic that occurs near the boundary of a window can result in twice the rate of requests being processed, since half go into the first window and the other half go into the second window. This could be exploited by a malicious actor.

• Sliding Log - Rate limiting is implemented by tracking a timestamped log for each customer’s requests. When a new request comes in, we calculate the sum of the logs to determine the request rate. If the customer’s request rate exceeds a certain threshold, we send an error message in response to the request. After a certain time period, we’ll remove previous logs (for example, we remove requests from a customer’s log after 5 minutes, so the customer can start sending requests again if they had previously exceeded the threshold).This solves the boundary conditions of Fixed Window and you also don’t have the issue of blocking new requests from customers who aren’t sending excessive requests. It also does well to prevent DOS attacks, since you can specifically block the malicious actors. However, Sliding Window can become expensive as you must store request logs for every customer and compute the customer’s request rate at each request.

These are just a couple of ways of implementing rate limiting in your system. They each come with their own set of tradeoffs.

It’s a simple concept, but can get quite tricky to implement correctly.