Notion Backend Engineer Coding Questions

Notion's performance hinges on efficiently loading pages, which may contain multiple blocks. To enhance user experience, a caching mechanism must be implemented that caches recently accessed pages to reduce load times.
Write a class Cache that implements the following methods:
- __init__(self, capacity: int) -> None - Initializes an empty cache with the given capacity.
- get(self, pageId: int) -> int - Returns the page content if found, or -1 if not.
- put(self, pageId: int, content: int) -> None - Adds a new page or updates the content of the existing page. If the capacity is full, it evicts the least recently used page.
- Example 1:
Input: cache = Cache(2)
cache.put(1, 1)
cache.put(2, 2)
cache.get(1)
Output: 1
Explanation: the value was found in the cache.
- Constraints:
- capacity will be at least 1 and at most 1000.
- Page IDs and contents are integers within the range of [-10^4, 10^4].

To keep users informed about updates and changes in their workspace, Notion needs a robust notification system that efficiently traverses user relationships. This ensures that notifications are delivered to the relevant users based on their projects and collaboration patterns.
Implement a function notifyUsers(graph: List[List[int]], userId: int) -> List[int] that returns a list of user IDs that will receive notifications starting from the given userId. The graph represents user relationships as an adjacency list.
- Example 1:
Input: graph = [[1,2], [0,3], [0], [1]], userId = 1
Output: [0, 2, 3]
Explanation: User 1 directly relates to user 0 (who relates to users 1 and 2) and user 3 in the graph.
- Constraints:
- 1 <= graph.length <= 10^4
- 0 <= userId < graph.length
- Each graph[i] is a list of integers representing direct relationships.