System Design Interview: How Would You Implement an API Rate Limiter in a Distributed Environment?

Rate limiting is one of those topics that sounds deceptively simple.