OpenAI Hard Interview Questions

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)

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

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.

OpenAI needs an efficient caching system to store previously computed model predictions, optimizing resource usage and response time.

Class Definition

Class LRUCache should implement the following methods:

• get(key: int) -> int: Returns the value of the key if the key exists, otherwise returns -1.


• put(key: int, value: int) -> None: Updates the value of the key if the key exists existing and moves the key to the front of the cache. Otherwise, it adds the key/value pair to the cache.

Example 1:

Input: cache = LRUCache(2); cache.put(1, 1); cache.put(2, 2); cache.get(1)
Output: 1
Explanation: Returns 1

Example 2:

Input: cache.put(3, 3); cache.get(2)
Output: -1
Explanation: Returns -1 since the cache reached its capacity; LRU (key = 2) was evicted.

Constraints:

• The capacity of the cache will be between 1 and 1000.


• All keys will be unique.