Patreon - Senior Software Engineer

**Phone screen**

1. We want to protect an API endpoint with an in-memory rate limiter.
   
2. The rate limiter should be initialized with a value that represents the maximum requests
   
3. per second we want to allow. When a request hits the endpoint, the rate limiter is
   
4. asked whether it has capacity to process this request and will reject or accept the request appropriately.
   
5. 
   
6. Assume:
   
7. _ Time is measured in millisecond resolution
   
8. - API requests come in sequentially
   
9. 
   
10. Design the interface and implement the logic for the rate limiter.
    
11. 
    
12. Example at a max of 2 requests/sec:
    
13. 12:00:01.100 PASS
    
14. 12:00:01.200 PASS
    
15. 12:00:01.300 FAIL
    
16. 12:00:02.100 PASS
    
17. 12:00:02.150 FAIL
    
18. 12:00:02.200 PASS

复制代码

1. from collections import deque as queue
   
2. class Bucket:
   
3.     def __init__(self, window_size_ms, max_requests_per_window):
   
4.         self.window_size_ms = window_size_ms
   
5.         self.max_requests_per_window = max_requests_per_window
   
6.         self.current_num_requests_in_window = 0
   
7.         self.queue = queue([])
   
8. 
   
9.     def submit_request(self, timestamp_ms):
   
10.         if self.queue:
    
11.             last_time_stamp = self.queue[0]
    
12.             time_diff = timestamp_ms - last_time_stamp
    
13. 
    
14.             if time_diff >= self.window_size_ms:
    
15.                 self.current_num_requests_in_window -= 1
    
16.                 self.queue.popleft()
    
17. 
    
18.         if self.current_num_requests_in_window < self.max_requests_per_window:
    
19.             self.queue.append(timestamp_ms)
    
20.             self.current_num_requests_in_window += 1
    
21.             return True
    
22.         return False
    
23. 
    
24. def test():
    
25.     bucket = Bucket(1000, 2)
    
26.     for timestamp in (1100, 1200, 1300, 2100, 2150, 2200):
    
27.         print(timestamp, bucket.submit_request(timestamp))
    
28. 
    
29. # Follow ups:
    
30. # 1. What if you have lots of users with different user ids? How do you handle their limits?
    
31. ## Map<userId, bucket>
    
32. # 2. What if you want to weight the requests, what do you do?
    
33. ## Change the weight in submitRequest
    
34. # 3. What if you have a distributed system? How do you manage the rate limiter?
    
35. ## Use a cache like Redis, potentially backed by a DB. Use SQL for consistency, NOSQL
    
36. ## if consistency isn't a must.

复制代码

**Question 2**

1. 
   
2. We want to create a function that mimics the cd command.
   
3. 
   
4. def cd(current, new):
   
5.     current = current.strip("/")
   
6.     path_so_far = [] if (current == "") else current.split("/")
   
7.     parts = new.split("/")
   
8.     for part in parts:
   
9.         if not part:
   
10.             continue
    
11.         if part == "..":
    
12.             if path_so_far:
    
13.                 path_so_far.pop()
    
14.         elif part == ".":
    
15.             continue
    
16.         else:
    
17.             path_so_far.append(part)
    
18.     result = "/".join(path_so_far)
    
19.     return "/" + result
    
20. 
    
21. # Test cases:
    
22. current = "/"
    
23. new = "a"
    
24. output = "/a"
    
25. 
    
26. current = "/b"
    
27. new = "c"
    
28. output = "/b/c"
    
29. 
    
30. current = "/d"
    
31. new = "/e"
    
32. output = "/e"
    
33. 
    
34. current = "/foo/bar"
    
35. new = ".."
    
36. output = "/foo"
    
37. 
    
38. current = "/r/s"
    
39. new = "../p/q"
    
40. output = "/r/p/q"
    
41. 
    
42. current = "/x/y"
    
43. new = "p/./q"
    
44. 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.

Keep in mind the grocery store is planning to
accept new types of c

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

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.

楼主， 请问这个是后端是吧