OpenAI Backend Engineer Interview Questions

To ensure reliable messaging between OpenAI's services and asynchronous job processing, design a class MessageQueue that manages message sending and receiving among services.
Class Signature:
class MessageQueue:
- send_message(service: str, message: str) -> None: Queues a message for the given service.
- receive_message(service: str) -> Optional[str]: Retrieves the next message for the specified service, if available.
Example 1:
Input: mq = MessageQueue() followed by mq.send_message("service1", "Hello World!") and mq.receive_message("service1")
Output: "Hello World!"
Explanation: The message successfully sent can be retrieved immediately.
Example 2:
Input: mq.send_message("service2", "Goodbye!") and then mq.receive_message("service1")
Output: None
Explanation: Since no messages were sent to service1, it returns None.
Constraints:
- Each service will send up to 10^4 messages per process.
- The total number of messages can be up to 10^5.

To streamline task executions across various AI models at OpenAI, we need a JobScheduler that manages scheduling and execution of jobs. Your implementation should handle job queuing and executing based on a predefined delay.
Class Signature:
class JobScheduler:
- add_job(name: str, delay: int) -> None: Adds a job with a name and a delay before execution.
- execute_jobs(current_time: int) -> List[str]: Returns a list of job names that are executed at a given current time.
Example 1:
Input: scheduler = JobScheduler() followed by scheduler.add_job("Task1", 5) and scheduler.execute_jobs(5)
Output: ['Task1']
Explanation: The task 'Task1' is executed exactly at time 5.
Example 2:
Input: scheduler.add_job("Task2", 2) and then scheduler.execute_jobs(3)
Output: ['Task2']
Explanation: The task 'Task2' is executed at time 2, even though we checked at time 3.
Constraints:
- The total number of jobs will not exceed 10^6.
- The maximum delay for any job will not exceed 10^9.

In order to improve rate limiting for OpenAI's API, we want to implement a system that optimally combines multiple requests into the fewest batch requests. Given an array of integers representing the request sizes and a maximum batch size, find the minimum number of batches needed to accommodate all requests.
Example 1:
Input: sizes = [2, 3, 4, 5], max_size = 6
Output: 3
Explanation: The optimal batches would be [2, 3], [4], [5]. Hence 3 batches are needed.
Example 2:
Input: sizes = [1, 2, 3, 4, 5], max_size = 5
Output: 3
Explanation: The total could be combined as [1, 2], [3, 4], [5] resulting in 3 batches.
Constraints:
- 1 <= sizes.length <= 1000
- 1 <= sizes[i] <= 1000
- 1 <= max_size <= 1000.

OpenAI aims to enhance user experience by suggesting models based on past usage. Your goal is to develop a function that selects model recommendations based on user interaction history represented as a directed graph.
Given a Graph object representing user interactions with models, implement a function that returns a list of recommended model IDs the user may like, based on depth-first search (DFS).
Example 1:
Input: Graph: {1: [2, 3], 2: [4], 3: [4], 4: []}, user_id: 1
Output: [4, 3, 2]
Explanation: The user has interacted with model 1, thus traversing through interactions leads to recommendations 4, 3, and 2.
Example 2:
Input: Graph: {5: [6], 6: [7], 7: [], 8: [7]}, user_id: 5
Output: [7, 6]
Explanation: The interactions lead to the models 7 and 6 based on the user’s initial interaction with model 5.
Constraints:
- The number of models n will be in the range 1 <= n <= 10^4.
- The number of interactions will be in the range 0 <= interactions <= 10^4.