OpenAI Hard Interview Questions

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.

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