☕ Latency and Throughput
A Microsoft Interview Question. We talk about Latency and Throughput in the context of System Design Interviews.
Hey,
Hope you had an amazing weekend!
We’re going to be changing it up today. Rather than having industry news, I’m going to go over a topic in System Design Interviews - Latency vs. Throughput.
Please reply to this email letting me know if you like the switch up!
We’ll go back to industry news tomorrow.
Interview Problem
Write a function that checks whether an integer is a palindrome.
For example, 191 is a palindrome, as well as 111. 123 is not a palindrome.
Do not convert the integer into a string!
We’ll send a detailed solution with test cases 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”
System Design Concepts
Latency vs. Throughput
Latency and Throughput are two incredibly important concepts in Systems Design. They’re ways to measure the performance of your System.
Latency is how long it takes for data to traverse your system.
An example would be the latency of a network request. How long does it take for your network request to go from the client (which is you) to the server (google’s servers for example) and back to the client (you).
An estimate for how long it takes to send 1 IP Packet as a Network Request from California, to the Netherlands, and back to California is 150,000 microseconds. That is the latency.
If you’d like to decrease latency, you need to invest in hardware that runs faster. Buying a more powerful server that can process requests at a faster speed will reduce latency.
Many times, however, you’re going to be bounded by the speed of light. At that point, you’ll be better off asking a physicist for help rather than a computer engineer.
Throughput is how much work a machine can perform in a given amount of time.
An example is how much data can be transferred from one point of your system to another point in your system. This might be measured in Mbps (Megabits Per Second) or Gbps (Gigabits Per Second).
Your internet download speed might be 50 Mbps, meaning your ISP can transfer 50 Megabits of content a second to you over your network.
Another example is how many requests your server can process in a second, or HTTP requests per second.
Increasing your throughput can be done by vertical scaling (upgrading your servers so they can requests more quickly) or by horizontal scaling (adding more servers to your system so you can process more requests simultaneously).
Or, in the case of your internet download speeds, you can increase it by leeching off your neighbor’s gigabit internet. Thanks Jack!
Previous Solution
As a refresher, here’s the previous question
A number is sparse if there are no adjacent ones in it’s binary representation.
For example, 341 is sparse since it is 101010101 in binary.
342 is not sparse since it is 101010110 in binary.
For a given input K, find the smallest sparse number that is greater than or equal to K.
Try to do this in faster than O(N log N).
Solution
The obvious solution is to just keep incrementing K until we get a number that is sparse.
The farthest we’ll have to search is K numbers away and checking whether a number is sparse takes O(log K) since K will have log(K) digits.
This means the naive solution will take O(K log K), which doesn’t beat our O(N log N) time constraint.
Instead, we can solve this question by manipulating the bits in K.
Any non-sparse number must contain the sequence 011 somewhere in the binary representation of the number (you may have to add a leading 0 to the binary representation).
Therefore, we can increment this sequence by 1 to 100 and make all the trailing digits after that sequence 0s.
This creates the next-largest number without that 011 sequence.
However, we may have accidentally created another 011 sequence when switching the 011 to 100. In order to check for that, we have to continue scanning “up” the binary representation (from right to left) to make sure there aren’t any 011 sequences.
If there are, then we repeat the same process of switching the 011 to 100 and making all the trailing digits 0s.
The time complexity is log(k).