Notion Mobile Engineer Coding Questions

Notion frequently accesses its API for user data and document retrieval. To enhance performance and reduce redundant API calls, we need to create an LRU Cache to store the most recently accessed items.
Your task is to design and implement a class that manages the cache, including methods to retrieve an item and add a new item, adhering to the LRU caching mechanism.

• get(key: int) -> int: Retrieve the value of the key if the key exists in the cache, otherwise return -1.


• put(key: int, value: int) -> None: Update the value of the key if it exists, or add the key-value pair if it does not exist. When the cache reaches its capacity, it should invalidate the least recently used item before inserting a new item.

Example 1:
Input: cache = LRUCache(2), cache.put(1, 1), cache.put(2, 2), cache.get(1), cache.put(3, 3), cache.get(2),
Output: 1
-1
Explanation: Cache returns 1 for the key 1 and -1 for the key 2 after it has been evicted.Constraints:

• capacity of the cache will be at most 3000.


• All keys and values are non-negative integers.

In Notion, multiple users can edit the same document simultaneously. We need to efficiently track the changes made by each user without overwhelming the system with data updates.
Given a string s representing the current content of a document and a list of users where each user makes a change denoted by their name followed by their intended edit, return the final state of the document after all changes are applied.

• Input: s: str, users: List[str]


• Output: str - final state of the document.

Example 1:
Input: `s =