注册一亩三分地论坛,查看更多干货!
您需要 登录 才可以下载或查看附件。没有帐号?注册账号 
x
本帖最后由 tomzhawang 于 2022-12-13 16:02 编辑
**Phone screen**- We want to protect an API endpoint with an in-memory rate limiter.
- The rate limiter should be initialized with a value that represents the maximum requests
- per second we want to allow. When a request hits the endpoint, the rate limiter is
- asked whether it has capacity to process this request and will reject or accept the request appropriately.
- Assume:
- _ Time is measured in millisecond resolution
- - API requests come in sequentially
- Design the interface and implement the logic for the rate limiter.
- Example at a max of 2 requests/sec:
- 12:00:01.100 PASS
- 12:00:01.200 PASS
- 12:00:01.300 FAIL
- 12:00:02.100 PASS
- 12:00:02.150 FAIL
- 12:00:02.200 PASS
复制代码- from collections import deque as queue
- class Bucket:
- def __init__(self, window_size_ms, max_requests_per_window):
- self.window_size_ms = window_size_ms
- self.max_requests_per_window = max_requests_per_window
- self.current_num_requests_in_window = 0
- self.queue = queue([])
- def submit_request(self, timestamp_ms):
- if self.queue:
- last_time_stamp = self.queue[0]
- time_diff = timestamp_ms - last_time_stamp
- if time_diff >= self.window_size_ms:
- self.current_num_requests_in_window -= 1
- self.queue.popleft()
- if self.current_num_requests_in_window < self.max_requests_per_window:
- self.queue.append(timestamp_ms)
- self.current_num_requests_in_window += 1
- return True
- return False
- def test():
- bucket = Bucket(1000, 2)
- for timestamp in (1100, 1200, 1300, 2100, 2150, 2200):
- print(timestamp, bucket.submit_request(timestamp))
- # Follow ups:
- # 1. What if you have lots of users with different user ids? How do you handle their limits?
- ## Map<userId, bucket>
- # 2. What if you want to weight the requests, what do you do?
- ## Change the weight in submitRequest
- # 3. What if you have a distributed system? How do you manage the rate limiter?
- ## Use a cache like Redis, potentially backed by a DB. Use SQL for consistency, NOSQL
- ## if consistency isn't a must.
复制代码 **Question 2**
- We want to create a function that mimics the cd command.
- def cd(current, new):
- current = current.strip("/")
- path_so_far = [] if (current == "") else current.split("/")
- parts = new.split("/")
- for part in parts:
- if not part:
- continue
- if part == "..":
- if path_so_far:
- path_so_far.pop()
- elif part == ".":
- continue
- else:
- path_so_far.append(part)
- result = "/".join(path_so_far)
- return "/" + result
- # Test cases:
- current = "/"
- new = "a"
- output = "/a"
- current = "/b"
- new = "c"
- output = "/b/c"
- current = "/d"
- new = "/e"
- output = "/e"
- current = "/foo/bar"
- new = ".."
- output = "/foo"
- current = "/r/s"
- new = "../p/q"
- output = "/r/p/q"
- current = "/x/y"
- new = "p/./q"
- output = "/x/y/p/q"
复制代码 Onsite
You're building a shopping cart pricer app for
your local grocery store. They sell many types of
items and accept coupons. One type of coupon
discounts an item's price by a percentage (e.g.
10% off). Another tybe of coupon gives the
shopper a dollar amount discount if a minimum
count of the item is purchased (e.g. $5 off if you
buy 2 or more). A shopper may only use one coupon on a type of item.
The app should compute the price given a shopping cart and
a set of coupons applied.
o retrieve content from creators with many followers. proactively discuss notification feed cache failure, caching recent posts, using a CDN, notification spam, failure, recovery)
The back-of-the-envelope calculations are not important. Make sure to state whether it's read-heavy or write-heavy.
Talk about rate limiting the notifications.
Draw the box diagram first. |