# ☕ 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 `0`

s.

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

s.

The time complexity is `log(k)`

.

## Create your profile

## Only paid subscribers can comment on this post

Log in## Check your email

For your security, we need to re-authenticate you.

Click the link we sent to , or click here to log in.