OpenAI logo

OpenAI Software Engineer Interview Questions

61 practice questions for OpenAI Software Engineer interviews

OpenAI software engineer interviews cover algorithms, data structures, system design, and coding problems drawn from real interview rounds.

Software Engineer Backend Engineer Frontend Engineer Full Stack Engineer Mobile Engineer Data Engineer Data Scientist ML Engineer DevOps Engineer DevOps Engineer Product Manager SRE Security Engineer Engineering Manager Data Analyst UX/UI Designer QA Engineer
17
Coding
1
System Design
coding Hard Verified Question #1

1. Count Machines In A Tree


Category: Tree coding problem
You are given a tree-structured network of machines where each node represents a machine. Machines can only communicate with their parent and...
Input: String
Output: Computed result
Want to practise this one?
Create a free account to open the full question and practise OpenAI questions with AI.
Sign up free
coding Medium Verified Question #2

2. Implement cd Command


Category: Algorithm coding problem
Implement a simplified version of the Unix cd command. Given a current directory path and a relative destination path, return the final absolute...
Input: Given input
Output: Computed result
coding Medium Verified Question #3

3. Largest Subgrid


Category: Grid/matrix coding problem
You are given a 2D grid of non-negative integers and a maximum sum constraint. Find the largest size of a square sub-grid such that all...
Input: 2D grid
Output: Integer
coding Hard Verified Question #4

4. Memory Allocator


Category: Linked list coding problem

Memory Allocator Design a memory allocator that manages a contiguous block of memory. Implement malloc and free operations with efficient...

Input: Linked list
Output: Computed result
coding Hard Verified Question #5

5. Toy Language Type Inference


Category: String coding problem
Implement a type system for a toy programming language that supports primitives, tuples, and generics. Your task is to represent types and infer...
Input: List
Output: Computed result
coding Medium Verified Question #6

6. Virus Spread


Category: Grid/matrix coding problem
Simulate the spread of a virus through a grid. Each cell can be in one of three states: healthy, infected, or immune. *This is similar to a leetcode...
Input: 2D grid
Output: Integer
coding Medium Verified Question #7

7. Bot-Enabled Messaging System


Category: String coding problem
You are building a chat system that supports human users and automated bots. Messages are added to a channel log and may trigger bot responses. The...
Input: List
Output: Computed result
coding Hard Verified Question #8

8. Connection Tracker


Category: Algorithm coding problem
Design a social network system that tracks follow relationships between users and preserves a full history through snapshots. The system allows...
Input: List
Output: Computed result
coding Medium Verified Question #9

9. GPU Credit Ledger


Category: String coding problem
You are designing a system to manage GPU credits. Each credit grant is valid during a specific time window. Events may arrive out of chronological...
Input: String
Output: Computed result
coding Medium Verified Question #10

10. GPU Credit Manager


Category: String coding problem
You are designing a system to manage GPU credits. Each credit grant is valid during a specific time window. Events may arrive out of chronological...
Input: String
Output: Computed result
coding Hard Verified Question #11

11. In-Memory SQL Engine


Category: String coding problem
Design an in-memory SQL database that supports creating tables, inserting rows with automatic type inference, and querying with filtering and sorting.
Input: List
Output: Computed result
coding Hard Verified Question #12

12. Persistent Key-Value Store


Category: Trie-based coding problem
You are designing a persistent key-value store that serializes its state to a binary storage medium. Native serialization (e.g., JSON, pickle,...
Input: Array
Output: Computed result
coding Hard Verified Question #13

13. Shard Rebalancer


Category: String coding problem
You are implementing a shard management system for a distributed key-value store. Each shard is identified by a string and covers a contiguous range...
Input: String
Output: Computed result
coding Hard Verified Question #14

14. IP Address Iterator


Category: String coding problem
Every device on the public internet is identified by an IPv4 address written in dotted-decimal notation as "A.B.C.D", where each octet is an...
Input: String
Output: Computed result
coding Medium Verified Question #15

15. Version Support Finder


Category: Binary search coding problem
A software company maintains a sorted list of version strings in ascending chronological order. A critical feature was introduced in one version, and...
Input: List
Output: Computed result
coding Medium Verified Question #16

16. Monster Battle Simulator


Category: String coding problem
Simulate a deterministic, turn-based battle between two ordered teams of monsters. Execute the fight step by step and produce a chronological battle...
Input: List
Output: Computed result
coding Medium Verified Question #17

17. Distributed Tree Messaging


Category: Tree coding problem
You are implementing a message-passing protocol for a distributed system organized as a rooted n-ary tree. Each node represents a machine and...
Input: List
Output: Printed output
system design Hard Verified Question #18

18. Top 5 Open AI System Design Questions


Category: Trie-based system design problem

System Design Questions - OpenAI A collection of commonly asked system design questions from OpenAI interviews.

Input: Given input
Output: Computed result
coding Hard heap #1

1. [AI Enabled Coding] Responses API Webhook Delivery Planner


Scenario


OpenAI API customers can receive webhook notifications when background responses complete or fail. Build an offline delivery planner that an operations team could use to replay a pending webhook backlog, applying retry policies and endpoint protections without making HTTP requests. This exercise adapts reported webhook-delivery interview questions; its scheduling rules are defined specifically for this problem, not presented as OpenAI production policy. You may use an AI assistant while implementing and testing your solution.

Part 1 — Retry eligibility and endpoint spacing


  • Each input record is a map of string keys to string values containing id, project, endpoint, event, timestamp, and attempts. timestamp is an integer number of seconds; attempts counts previous failed attempts.

  • Accept only response.completed and response.failed. Exclude any other event with reason FILTERED, even if its attempt count would also trigger the dead-letter rule.

  • Exclude an accepted event with attempts >= 3 with reason DEAD_LETTER.

  • An eligible delivery's readiness time is timestamp when attempts == 0; otherwise it is timestamp + 2^attempts. Thus one previous failure adds 2 seconds and two add 4 seconds.

  • Deliveries to the same endpoint must be separated by at least 2 seconds, enforced by the rule named endpoint_gap. Different endpoints may dispatch simultaneously.

  • Repeatedly choose the unscheduled delivery with the earliest feasible dispatch time given all already scheduled deliveries. Break ties by lexicographically smaller id. Record one dispatch per eligible record; do not simulate the result of that dispatch.

  • Return deliveries in dispatch order and excluded records in lexicographic ID order. Your return type is up to you; the examples use the JSON representation below.


Function signature:
def plan_deliveries(records: list[dict[str, str]]):
    ...

Example 1


Input:
{
  "records": [
    {"id":"a","project":"p","endpoint":"e1","event":"response.completed","timestamp":"0","attempts":"0"},
    {"id":"b","project":"p","endpoint":"e1","event":"response.failed","timestamp":"0","attempts":"0"},
    {"id":"c","project":"p","endpoint":"e2","event":"response.completed","timestamp":"1","attempts":"2"},
    {"id":"d","project":"p","endpoint":"e2","event":"response.completed","timestamp":"0","attempts":"3"},
    {"id":"e","project":"p","endpoint":"e3","event":"response.in_progress","timestamp":"0","attempts":"0"}
  ]
}

Output:
{
  "deliveries": [{"id":"a","at":0},{"id":"b","at":2},{"id":"c","at":5}],
  "excluded": [{"id":"d","reason":"DEAD_LETTER"},{"id":"e","reason":"FILTERED"}]
}

Explanation: a dispatches at 0. Although b is ready at 0, its endpoint cannot dispatch again until 0 + 2 = 2. Delivery c is ready at 1 + 2^2 = 5; its endpoint has no previous dispatch. The excluded records consume no scheduling capacity.

Part 2 — Caller-defined rolling-window quotas and explanations


Other platform teams now need to add project-level and endpoint-level protections. Extend the function with a second argument, quotas: list[dict[str, str]]. Before implementing this extension, discuss how the return type changes to represent multiple blocking rules. Your design must support future quota additions through configuration and new rule kinds through a common rule interface, without rewriting the core scheduling loop.
  • Every quota has string fields id, scope, key, limit, and window. scope is project or endpoint; key selects exactly one project or endpoint. limit and window are positive integers represented as strings.

  • A matching quota permits at most limit dispatches in the rolling interval (t - window, t], including the proposed dispatch at t. A dispatch exactly window seconds earlier does not count. Each dispatch consumes one unit in every matching quota.

  • All Part 1 rules remain active. A delivery must satisfy every applicable rule simultaneously. Quotas constrain the scheduling decision, not just the final report.

  • If at least limit matching dispatches have already been scheduled, let s be the timestamp of the limit-th most recent matching dispatch. This quota alone requires the new delivery to occur no earlier than s + window. Otherwise it imposes no additional lower bound.

  • When a delivery is selected, independently evaluate each applicable rule against the already scheduled deliveries and its original readiness time. Include a blocker for every rule whose resulting earliest time is strictly greater than that readiness time, even if another rule imposes a larger delay. Each blocker is {"rule": rule_id, "not_before": integer_time}; sort blockers by rule ID.

  • With a quotas argument, each delivery additionally contains blockers, including an empty array when no rule delays it. With no quotas argument, retain the Part 1 output. Excluded records are unchanged.


Example 2


Input:
{
  "records": [
    {"id":"a","project":"p","endpoint":"e1","event":"response.completed","timestamp":"0","attempts":"0"},
    {"id":"b","project":"p","endpoint":"e2","event":"response.completed","timestamp":"0","attempts":"0"},
    {"id":"c","project":"p","endpoint":"e1","event":"response.failed","timestamp":"0","attempts":"0"},
    {"id":"d","project":"p","endpoint":"e2","event":"response.completed","timestamp":"1","attempts":"1"}
  ],
  "quotas": [
    {"id":"project_budget","scope":"project","key":"p","limit":"2","window":"5"}
  ]
}

Output:
{
  "deliveries": [
    {"id":"a","at":0,"blockers":[]},
    {"id":"b","at":0,"blockers":[]},
    {"id":"c","at":5,"blockers":[{"rule":"endpoint_gap","not_before":2},{"rule":"project_budget","not_before":5}]},
    {"id":"d","at":5,"blockers":[{"rule":"project_budget","not_before":5}]}
  ],
  "excluded": []
}

Explanation: a and b use both project slots at time 0. Delivery c is ready at 0, but endpoint spacing requires 2 and the project quota requires 0 + 5 = 5. Delivery d is ready at 1 + 2^1 = 3; its endpoint bound is only 2, so that rule is not a blocker. Both c and d can dispatch at 5, with c first by ID. The two time-0 dispatches are outside (0, 5], and the two time-5 dispatches exactly fill the cap of 2.

Example 3


Input:
{
  "records": [
    {"id":"a","project":"p","endpoint":"e1","event":"response.completed","timestamp":"0","attempts":"0"},
    {"id":"b","project":"p","endpoint":"e1","event":"response.completed","timestamp":"0","attempts":"0"},
    {"id":"c","project":"p","endpoint":"e1","event":"response.failed","timestamp":"0","attempts":"0"},
    {"id":"d","project":"p","endpoint":"e1","event":"response.failed","timestamp":"0","attempts":"3"}
  ],
  "quotas": [
    {"id":"project_budget","scope":"project","key":"p","limit":"1","window":"5"},
    {"id":"endpoint_burst","scope":"endpoint","key":"e1","limit":"2","window":"12"}
  ]
}

Output:
{
  "deliveries": [
    {"id":"a","at":0,"blockers":[]},
    {"id":"b","at":5,"blockers":[{"rule":"endpoint_gap","not_before":2},{"rule":"project_budget","not_before":5}]},
    {"id":"c","at":12,"blockers":[{"rule":"endpoint_burst","not_before":12},{"rule":"endpoint_gap","not_before":7},{"rule":"project_budget","not_before":10}]}
  ],
  "excluded": [{"id":"d","reason":"DEAD_LETTER"}]
}

Explanation: After a dispatches at 0, b must wait until max(0 + 2, 0 + 5) = 5; the endpoint quota still has its second slot available. For c, three rules independently delay its readiness of 0: endpoint spacing requires 5 + 2 = 7, the project quota requires 5 + 5 = 10, and the endpoint quota requires 0 + 12 = 12. At time 12, the endpoint interval (0, 12] contains only b and c, totaling 2, while the project interval (7, 12] contains only c, totaling 1. Record d is excluded before scheduling.

Notes


  • There are at most 2,000 records and 20 quotas. IDs are unique, timestamps and attempts are nonnegative integers, and all supplied records and configurations are well-formed. Quota IDs are unique and cannot equal endpoint_gap.

  • Endpoint IDs are globally unique. Scheduling starts with empty history, uses unbounded integer seconds, and has no external dispatches or concurrent mutations.

  • Do not iterate through individual seconds. Explain your algorithm's worst-case complexity, including the cost of rescheduling candidates after shared quotas change.
Want to practise this one?
Create a free account to open the full question and practise OpenAI questions with AI.
Sign up free
coding Hard tree #2

2. [Augmented Search Tree] — Query timestamped values with overlapping expiration windows


Background
OpenAI's model-serving infrastructure needs to reason about timestamped state and expiration when selecting cached configuration snapshots. This exercise models a snapshot cache where an older snapshot can remain usable after a newer, short-lived snapshot expires; it adapts a community-reported OpenAI timestamped key-value-store question with expiry constraints.
Problem statement
Implement a TemporalSnapshotStore supporting writes and historical reads. Each write contains a key, a value, a timestamp, and a positive time-to-live (ttl). Its validity interval is [timestamp, timestamp + ttl).
For get(key, query_time), return the value of the valid write for that key having the greatest write timestamp. If no write is valid at query_time, return None. In particular, an expired newer write does not hide an older write that is still valid.
Writes may arrive out of timestamp order, and reads may query any historical time. A write to an existing (key, timestamp) replaces both its value and its ttl. Each read considers only writes processed before that read; replacement also affects subsequent historical reads.
Support operations online, without knowing future operations. Target expected O(log n) time per operation, where n is the number of distinct timestamps stored for the relevant key. Scanning expired versions or inserting into a sorted array does not meet this target.
Class signature
  • TemporalSnapshotStore() — initialize an empty store.

  • set(key: str, value: str, timestamp: int, ttl: int) -> None — insert or replace one version.

  • get(key: str, query_time: int) -> str | None — return the newest valid version, or None.


Example 1:
Input:
{
  "operations": [
    ["set", "routing", "stable", 10, 100],
    ["set", "routing", "canary", 20, 5],
    ["get", "routing", 24],
    ["get", "routing", 25],
    ["get", "routing", 110]
  ]
}

Output, including null for each set:
[null, null, "canary", "stable", null]

Explanation: canary is valid on [20, 25), while stable is valid on [10, 110). At time 25, the canary has expired, so the older stable snapshot is selected. At time 110, both have expired.
Example 2:
Input:
{
  "operations": [
    ["set", "model-config", "newer", 30, 10],
    ["set", "model-config", "older", 10, 50],
    ["set", "model-config", "replacement", 30, 3],
    ["get", "model-config", 32],
    ["get", "model-config", 33],
    ["get", "model-config", 9]
  ]
}

Output:
[null, null, null, "replacement", "older", null]

Explanation: Writes arrive out of order. Replacing timestamp 30 changes its validity interval to [30, 33). At time 33, the version at timestamp 10 is still valid until time 60. At time 9, neither version has started.
Constraints:
  • At most 200,000 total set and get calls.

  • Keys and values are strings of length 1 through 100.

  • 0 <= timestamp, query_time <= 10^12.

  • 1 <= ttl <= 10^12.

  • Operations are single-threaded. Historical versions cannot be discarded merely because they have expired relative to wall-clock time.


Follow-up:
How would you support concurrent readers and writers while ensuring that each read observes one consistent version of the store? Explain the tradeoffs between per-key locking and immutable, path-copied search trees.
coding Medium dynamic programming #3

3. Dynamic Programming — Maximize the AI Model Performance

Background: OpenAI continuously strives to improve the performance of its machine learning models based on provided data inputs. Efficient optimization algorithms are crucial for predicting outcomes accurately and ensuring models are trained effectively.
Problem statement: Given a list of integers representing the performance scores of an AI system on different datasets, you need to determine the maximum sum of non-adjacent scores possible. This means you cannot select scores that are consecutive.
Function/class signature:
  • def max_non_adjacent_score(scores: List[int]) -> int:

Example 1:
  • Input: [3, 2, 5, 10, 7]

  • Output: 15

  • Explanation: Choose scores 3, 10, and 2 to get 3 + 10 + 2 = 15, skipping the adjacent 2 and 5.

Example 2:
  • Input: [1, 2, 3, 1]

  • Output: 4

  • Explanation: Choose scores 1 and 3 to get 1 + 3 = 4, avoiding the adjacent scores.

Constraints:
  • 0 <= scores.length <= 1000

  • 0 <= scores[i] <= 1000
coding Medium dynamic programming #4

4. Dynamic Programming — Maximum Path Sum in a Grid

Background: OpenAI often deals with large data flows and needs efficient algorithms to compute aggregates over its underlying data. Applications in AI systems and optimization problems can utilize these algorithms effectively.
Problem statement: Given a m x n grid filled with non-negative integers, find a path from the top-left corner to the bottom-right corner, which minimizes the sum of the values along the path. You can only move down or right at any point in time.
Function/class signature:
  • def min_path_sum(grid: List[List[int]]) -> int:

Example 1:
  • Input: [[1,3,1],[1,5,1],[4,2,1]]

  • Output: 7

  • Explanation: The path 1 → 3 → 1 → 2 → 1 minimizes the sum to 7.

Example 2:
  • Input: [[1,2,3],[4,5,6]]

  • Output: 12

  • Explanation: The path 1 → 2 → 3 → 6 minimizes the sum to 12.

Constraints:
  • 1 <= m, n <= 100

  • 0 <= grid[i][j] <= 100
coding Medium dynamic programming #5

5. Dynamic Programming — Subset Sum Problem

Background: OpenAI often deals with optimization problems that can benefit from strategies like the subset-sum problem. It's essential for resource allocation in AI training workflows where budget constraints are significant.
Problem statement: Given a set of n integers and a target integer target, determine if there's a subset of the given integers that adds up to exactly the target value. You should implement a function that efficiently solves this problem using dynamic programming.
Function/class signature:
  • def subset_sum(nums: List[int], target: int) -> bool:

Example 1:
  • Input: nums = [3, 34, 4, 12, 5, 2], target = 9

  • Output: True

  • Explanation: The subset {4, 5} adds up to 9.

Example 2:
  • Input: nums = [1, 2, 3, 7], target = 6

  • Output: True

  • Explanation: The subset {1, 2, 3} adds up to 6.

Constraints:
  • 0 < n <= 20

  • -1000 <= nums[i] <= 1000

  • 0 <= target <= 1000
coding Medium graph #6

6. Graph — Shortest Path in a Multi-Source Scenario

Background: In designing efficient AI systems, OpenAI needs to optimize routes for data points that originate from multiple sources. This is crucial for minimizing response times in API services that rely on complex data paths.
Problem statement: You are given an undirected graph represented as a list of edges, and multiple source nodes. Your task is to find the shortest distance from any of the source nodes to all other nodes in the graph. The distance between two connected nodes is uniformly 1.
Function/class signature:
  • def multi_source_shortest_path(edges: List[Tuple[int, int]], sources: List[int]) -> Dict[int, int]:


Example 1:
Input: edges = [(0, 1), (1, 2), (0, 2), (2, 3)], sources = [0]
Output: {0: 0, 1: 1, 2: 1, 3: 2}
Explanation: The shortest paths from node 0 are as follows: to itself is 0, to 1 is 1, to 2 is 1, and to 3 is 2.
Example 2:
Input: edges = [(0, 1), (1, 2), (2, 3), (3, 4), (4, 1)], sources = [1, 3]
Output: {0: 2, 1: 0, 2: 1, 3: 0, 4: 1}
Explanation: The shortest distances are calculated from both sources 1 and 3.
Constraints:
  • The number of edges (|E|) is between 1 and 10^5.

  • The number of nodes (|V|) is between 1 and 10^5.

  • Each edge connects two different nodes.

  • Nodes are labeled with integers from 0 to V-1.


coding Medium graph #7

7. Graph Traversal — Scheduling Human Labeling Tasks


Background: OpenAI often relies on human labelers to accurately annotate data for machine learning models. It is critical to ensure that labeling tasks are efficiently distributed among available labelers to maintain productivity and prevent overload.
Problem statement: Given a set of labelers, a list of tasks with required time to complete, and models that need this data, create a function that returns a balanced assignment of tasks to each labeler. Every label should have an equitable workload within a specified limit.
Function/class signature:
  • def assign_tasks(labelers: List[str], tasks: List[int], max_load: int) -> Dict[str, List[int]]:


Example 1:
  • Input: labelers = ['Alice', 'Bob', 'Charlie'], tasks = [3, 1, 4, 2, 5], max_load = 5

  • Output: {'Alice': [3, 2], 'Bob': [1, 4], 'Charlie': [5]}

  • Explanation: Each labeler has a total load that does not exceed the max_load of 5.


Example 2:
  • Input: labelers = ['Dave', 'Eve'], tasks = [1, 2, 3], max_load = 3

  • Output: {'Dave': [1, 2], 'Eve': [3]}


Constraints:
  • 1 <= len(labelers) <= 10

  • 1 <= len(tasks) <= 100

  • 0 <= tasks[i] <= 10

  • max_load > 0
coding Medium dynamic programming #8

8. Dynamic Programming — Minimum Cost Path in a 2D Grid

Background: In many machine learning applications at OpenAI, including reinforcement learning and optimization problems, finding efficient pathways is crucial. This problem relates to ensuring optimal resource allocation in grid environments, possibly related to robotics or game simulations.
Problem statement: Given a 2D grid costs where each integer represents the cost to step on that cell, write a function to find the minimum cost to reach the bottom right corner of the grid from the top left corner. You can only move down or right at any point in time.
Function/class signature:
  • def min_cost_path(costs: List[List[int]]) -> int:

Example 1:
  • Input: [[1, 3, 1], [1, 5, 1], [4, 2, 1]]

  • Output: 7

  • Explanation: The path is 1 -> 3 -> 1 -> 1 -> 1, total cost = 7.

Example 2:
  • Input: [[10, 2], [1, 1]]

  • Output: 3

  • Explanation: The path is 10 -> 1 -> 1, total cost = 3.

Constraints:
  • 1 ≤ costs.length, costs[i].length ≤ 100

  • 0 ≤ costs[i][j] ≤ 100
coding Medium dynamic programming #9

9. Dynamic Programming — Longest Increasing Subsequence

Background: OpenAI frequently works with time series data and machine learning models that involve sequential predictions. Identifying patterns, such as trends in data, is crucial for optimizing model performance.
Problem statement: Given an integer array nums, return the length of the longest increasing subsequence. A subsequence is formed by removing elements from the array without changing the order of the remaining elements. This problem is essential for analyzing sequences in large datasets relevant to OpenAI's products.
Function/class signature:
  • def length_of_LIS(nums: List[int]) -> int:

Example 1:
Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
Example 2:
Input: nums = [0,1,0,3,2,3]
Output: 4
Explanation: The longest increasing subsequence is [0,1,2,3], therefore the length is 4.
Constraints:
  • 1 <= nums.length <= 2500

  • -10^4 <= nums[i] <= 10^4

coding Hard sliding window #10

10. [OA] Sliding Window — Optimize model inference response times

OpenAI's inference API must handle continuous input streams efficiently, ensuring optimal latency and throughput.
Given an array of integers, find the maximum sum of a subarray of size k.

Function Signature


  • def max_sum_subarray_of_k(arr: List[int], k: int) -> int: Returns the maximum sum of the subarray of size k.


Example 1:


Input: arr = [1, 2, 3, 4, 5], k = 3
Output: 12
Explanation: The maximum sum subarray of size 3 is [3, 4, 5] with a sum of 12.

Example 2:


Input: arr = [2, 3, 4, 1, 5], k = 2
Output: 7
Explanation: The maximum sum is from the subarray [4, 1].

Constraints:


  • 0 < len(arr) <= 1000

  • 1 <= k <= len(arr)
coding Hard dynamic programming #11

11. [OA] Dynamic Programming — Optimize OpenAI's text completion efficiency

OpenAI's text completion models require efficient algorithms to generate responses in real-time while minimizing computational cost.
Given an array of integers representing the tokens in a sequence, you need to calculate the maximum non-adjacent sum of tokens that can be chosen from this array.

Function Signature


  • def max_non_adjacent_sum(tokens: List[int]) -> int: Returns the maximum sum of non-adjacent integers.


Example 1:


Input: [3, 2, 5, 10, 7]
Output: 15
Explanation: The optimal choice is to take tokens 3, 10, and 2 which gives the maximum sum 15 without selecting adjacent values.

Example 2:


Input: [9, 1, 2, 8, 3]
Output: 17
Explanation: The optimal choice is to take tokens 9, 8, and 3.

Constraints:


  • 0 < len(tokens) <= 1000

  • 0 <= tokens[i] <= 1000
system design Hard data structure #12

12. [OA] MedianFinder — Implement a data structure for keeping OpenAI's result metrics

OpenAI often needs to compute the median of predicted metrics in real-time. This requires an efficient data structure to retrieve the median quickly while processing continuous streams of data.

Class Definition


Class MedianFinder should implement the following methods:
  • addNum(num: int) -> None: Adds a number to the data structure.

  • findMedian() -> float: Returns the median of all added numbers.


Example 1:


Input: medianFinder = MedianFinder(); medianFinder.addNum(1); medianFinder.addNum(2); medianFinder.findMedian()
Output: 1.5
Explanation: The median of [1,2] is 1.5

Example 2:


Input: medianFinder.addNum(3); medianFinder.findMedian()
Output: 2
Explanation: The median of [1,2,3] is 2.

Constraints:


  • -10^5 <= num <= 10^5

  • There will be at most 1,000,000 calls to addNum and findMedian.

Related OpenAI Software Engineer interview prep

Start practicing OpenAI questions

Sign up for free to access walkthroughs, AI-generated questions, and more.

Get Started Free