Reddit Software Engineer Coding 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