4 ms·

Good stuff. A couple of comments to the post: Rate limiter: I would probably use a hash table of this structure -- called[yyyy-mm-dd][hh-mm] and then increment

Good stuff. A couple of comments to the post: Rate limiter: I would probably use a hash table of this structure -- called[yyyy-mm-dd][hh-mm] and then increment the hashtable for that minute, for example, called[2022-01-02][22-01]++ and drop any entries for the last day at the end of the day. Post doesn't mention this, but one other common pattern I've seen requires a tree data structure, and those interview questions can be solved with recursion. Basically once you have a tree data structure, you write a f(node) that will simply call f(left) & f(right) recursively -- or for-each(child in children) { f(child) } for non-binary trees.

bradleybuda 5y ago
I agree with your answer on the rate limiter, but I think it depends on whether the spec is for rolling or fixed one-minute windows. The question is ambiguous, but the sample answer implies that we want to track rolling windows. If that's the case, an improvement on the answer is to use a ring buffer instead of a linked list, which allocates a fixed set of memory up front (slower to initialize) but then is allocation-free on each invocation.
malisper 5y ago
> Rate limiter: I would probably use a hash table of this structure -- called[yyyy-mm-dd][hh-mm] and then increment the hashtable for that minute, for example, called[2022-01-02][22-01]++ and drop any entries for the last day at the end of the day. As Bradley said this implementation can be called more than 10 times within a 1 minute window. If it's called 9 times at the last second of one minute and 9 times at the start of the next minute, it will be called 18 times within a two second interval.
john_moscow 5y ago
>Rate limiter: I would probably use a hash table of this structure -- called[yyyy-mm-dd][hh-mm] and then increment the hashtable for that minute, for example, called[2022-01-02][22-01]++ and drop any entries for the last day at the end of the day. Why on Earth? Given that the timestamp cannot randomly jump backwards, you can achieve the same results by just storing the timestamp of the first call after a reset, and the number of calls sharing the same date/hour/minute, resetting it to 0 when the minute advances. That said, it won't be entirely what was asked, since it won't have the rolling behavior.

bradleybuda 5y ago

I agree with your answer on the rate limiter, but I think it depends on whether the spec is for rolling or fixed one-minute windows. The question is ambiguous, but the sample answer implies that we want to track rolling windows. If that's the case, an improvement on the answer is to use a ring buffer instead of a linked list, which allocates a fixed set of memory up front (slower to initialize) but then is allocation-free on each invocation.

malisper 5y ago

> Rate limiter: I would probably use a hash table of this structure -- called[yyyy-mm-dd][hh-mm] and then increment the hashtable for that minute, for example, called[2022-01-02][22-01]++ and drop any entries for the last day at the end of the day. As Bradley said this implementation can be called more than 10 times within a 1 minute window. If it's called 9 times at the last second of one minute and 9 times at the start of the next minute, it will be called 18 times within a two second interval.

john_moscow 5y ago

>Rate limiter: I would probably use a hash table of this structure -- called[yyyy-mm-dd][hh-mm] and then increment the hashtable for that minute, for example, called[2022-01-02][22-01]++ and drop any entries for the last day at the end of the day. Why on Earth? Given that the timestamp cannot randomly jump backwards, you can achieve the same results by just storing the timestamp of the first call after a reset, and the number of calls sharing the same date/hour/minute, resetting it to 0 when the minute advances. That said, it won't be entirely what was asked, since it won't have the rolling behavior.