Coinbase Backend Engineer Coding Questions

Coinbase requires a rate limiter to prevent excessive requests to its APIs, ensuring fair usage across users.
Design a RateLimiter class that limits the number of calls to a specified maxRequests over a time period of timeWindow. If the limit is exceeded, new requests should receive an error response.
Method signature:
- def is_request_allowed(user_id: str, timestamp: int) -> bool: Returns True if the request is allowed, False if it exceeds the limit.
Example 1:
Input: user_id = 'user1', timestamp = 1
Output: True
Explanation: 1 request is within limit.Example 2:
Input: user_id = 'user1', timestamp = 6
Output: False
Explanation: On timestamp 6, user has exceeded the max requests within the specified time window.
Constraints:
- 1 <= maxRequests <= 100
- 1 <= timeWindow <= 1000

Coinbase needs a system to detect fraudulent transactions by visualizing relationships in a transaction graph.
Implement a method that returns all fraudulent transaction paths in a directed graph where nodes represent accounts and edges represent transactions. You must return all paths having a maximum depth of k.
Method signature:
- def find_fraudulent_paths(graph: Dict[str, List[str]], max_depth: int) -> List[List[str]]: Returns a list of lists containing all possible paths that are at most of length max_depth.
Example 1:
Input: graph = {'A': ['B', 'C'], 'B': ['D'], 'C': ['D'], 'D': []}, max_depth = 2
Output: [['A', 'B'], ['A', 'C'], ['A', 'B', 'D'], ['A', 'C', 'D']]
Explanation: Transactions are depicted as paths based on the graph's depth constraints.Example 2:
Input: graph = {'A': ['B'], 'B': ['C'], 'C': []}, max_depth = 1
Output: [['A', 'B'], ['A']]
Explanation: Only paths staying within the given maximum depth are represented.
Constraints:
- 1 <= len(graph) <= 100
- 1 <= max_depth <= 10