Reddit Interview Questions

Background: On Reddit, users often share content that can have overlapping themes and characters. It’s important to understand how to manage user input effectively, especially in features like comments or tags where uniqueness enhances the experience.
Problem statement: Given a string s, return the length of the longest substring without repeating characters. A substring is defined as a contiguous sequence of characters in s. You must implement an efficient solution to handle potentially large strings common in user-generated content.
Function/class signature:

• def length_of_longest_substring(s: str) -> int:

Example 1:

• Input: "abcabcbb"


• Output: 3


• Explanation: The answer is "abc", with the length of 3.

Example 2:

• Input: "bbbbb"


• Output: 1


• Explanation: The answer is "b", with the length of 1.

Constraints:

• 0 <= s.length <= 50,000


• s consists of English letters, digits, symbols and spaces.

Background: As Reddit continues to grow, it becomes crucial to manage API requests effectively to prevent abuse and ensure fair resource utilization. A rate limiter is essential for APIs to handle request quotas based on user status and type of action taken on the platform.
Problem statement: Implement a RateLimiter class that supports multiple APIs and handles different request quotas per user efficiently. Each user has a unique ID and can have different rate limits on different APIs. Your implementation should allow checking if a user can make a request to an API and register the request, updating the rate limit accordingly.
Function/class signature:

• class RateLimiter


• def can_request(self, user_id: str, api_name: str) -> bool:


• def register_request(self, user_id: str, api_name: str) -> None:

Example 1:

• Input:

rate_limiter = RateLimiter()
rate_limiter.register_request('user1', 'api1')
rate_limiter.can_request('user1', 'api1')

• Output:

True

• Explanation: User 'user1' can make a request to 'api1'.

Example 2:

• Input:

rate_limiter.register_request('user1', 'api1')
rate_limiter.register_request('user1', 'api1')
rate_limiter.can_request('user1', 'api1')

• Output:

False

• Explanation: User 'user1' reached the request limit for 'api1'.

Constraints:

• 1 <= user_id <= 1000 (string)


• 1 <= api_name <= 100 (string)


• The maximum number of requests a user can make in a period is modifiable when instantiating the RateLimiter class.

Background: Reddit manages a large volume of posts and comments daily. A priority queue can efficiently organize threads based on user engagement or moderator review. This is critical for ensuring that popular or important discussions remain visible.
Problem statement: Implement a PriorityQueue class that supports adding threads with a given priority and returning the thread with the highest priority. The class should implement the following operations:

• add(thread: str, priority: int) -> None: Inserts a new thread with the specified priority into the priority queue.


• poll() -> str: Removes and returns the thread with the highest priority. If two threads have the same priority, return the one that was added first.


• peek() -> str: Returns the thread with the highest priority without removing it from the queue.

Function/class signature:

• class PriorityQueue:

- def add(self, thread: str, priority: int) -> None:
- def poll(self) -> str:
- def peek(self) -> str: Example 1:

• Input:

pq = PriorityQueue()
pq.add("Post A", 2)
pq.add("Post B", 3)
pq.poll()

• Output:

"Post B"

• Explanation: "Post B" has a higher priority than "Post A" and is returned.

Example 2:

• Input:

pq = PriorityQueue()
pq.add("Post X", 1)
pq.add("Post Y", 1)
pq.poll()

• Output:

"Post X"

• Explanation: "Post X" was added first, so it is returned despite the same priority.

Constraints:

• Each thread will be a non-empty string of at most 100 characters.


• The priority will be an integer between 1 and 100.


• The number of operations will not exceed 10^4.

Background: Reddit has numerous subreddits with interconnected posts and comments that create a complex structure resembling a graph. Understanding these connections can enhance features like recommendation systems for users based on their interests.
Problem statement: Given a directed acyclic graph that represents posts in a subreddit as nodes and comments as directed edges, write a function to find the longest path from the root node (the original post) to any other node (a comment). The path length is defined by the number of edges traversed. You must implement the function longest_path(graph: Dict[int, List[int]], start: int) -> int where graph is a dictionary where each key represents a node and the value is the list of nodes it points to.
Function/class signature:

• def longest_path(graph: Dict[int, List[int]], start: int) -> int:

Example 1:

• Input: graph = {1: [2, 3], 2: [4], 3: [], 4: []}, start = 1


• Output: 3


• Explanation: The longest path from node 1 to any node is 1 → 2 → 4 or 1 → 3, both have 3 edges.

Example 2:

• Input: graph = {1: [2], 2: [3], 3: [4], 4: []}, start = 1


• Output: 4


• Explanation: The only path is 1 → 2 → 3 → 4 which has a length of 4.

Constraints:

• 1 ≤ number of nodes ≤ 1000


• number of edges between nodes ≤ 2000

Background: Reddit supports multiple APIs, each with different request quotas per user. To prevent abuse and ensure fair usage across various clients, a robust rate limiter is essential.Requirements:
1. Implement a method to add an API with its corresponding request quota.
2. Implement a method to check if a user can make a request to a specific API based on their current usage.
3. Implement a method to record a user's usage for a specific API.
4. Implement a method to reset a user's quota for a specific API after a designated time interval.
5. Ensure that the class is thread-safe to handle concurrent requests from multiple users.Class API:

• add_api(api_name: str, quota: int) -> None: Adds a new API with its request quota.


• can_request(user_id: str, api_name: str) -> bool: Checks if the user can make a request to the given API.


• record_request(user_id: str, api_name: str) -> None: Records a request made by the user to the given API.


• reset_user_quota(user_id: str, api_name: str) -> None: Resets the user's quota after a designated time interval.

Example 1:

• Input: add_api("getComments", 100) → Output: None → Explanation: A new API with a quota of 100 requests has been added.


• Input: can_request("user123", "getComments") → Output: True → Explanation: User can make a request as they haven't exceeded the quota.

Example 2:

• Input: record_request("user123", "getComments") → Output: None → Explanation: Request recorded.


• Input: can_request("user123", "getComments") → Output: True/False → Explanation: Depending on the number of recorded requests.

Constraints:

• Maximum APIs: 100


• Maximum requests per user per API: 1000


• Time reset limit: 1 hour


• Users are represented by unique strings.

Background: Reddit needs to ensure that users don’t exceed the allowed rate for various APIs to maintain service quality and prevent abuse. The RateLimiter class should handle different quotas for each user per API efficiently.
Requirements:
1. The class should allow setting up rate limits for different users and APIs.
2. The rate limiting needs to support different request quotas for various APIs.
3. Track the number of requests made by each user for each API.
4. Provide a method to check if a user can make an API request based on their current usage and the API's limit.
5. Implement a way to reset the counts after a period (e.g., daily reset).
Class API:

• def set_limit(user_id: str, api_name: str, limit: int, period: int) -> None: Sets the rate limit for a particular user on a specific API.


• def can_request(user_id: str, api_name: str) -> bool: Checks if a user can request an API call without exceeding the limit.


• def record_request(user_id: str, api_name: str) -> None: Records an API request for a user.


• def reset_usage(user_id: str, api_name: str) -> None: Resets the usage for a user on a specific API after the defined period.

Example 1:
Input sequence of method calls:
set_limit('user123', 'api1', 5, 60)
record_request('user123', 'api1')
can_request('user123', 'api1')
Output: True
Explanation: User 'user123' has set a limit of 5 requests on 'api1' and has made 1 request, so they can make more requests.
Example 2:
Input sequence of method calls:
set_limit('user123', 'api1', 2, 30)
record_request('user123', 'api1')
record_request('user123', 'api1')
can_request('user123', 'api1')
Output: False
Explanation: User 'user123' has made 2 requests against the limit of 2 on 'api1' and cannot make another request until reset.
Constraints:

• Max users: 10^4


• Max APIs: 10^3


• Max requests per user: 10^5