Notion Backend Engineer Interview Questions

In Notion's collaborative environment, allowing users to comment on different blocks adds significant value. A messaging system must be designed to enable users to create, retrieve, and delete comments efficiently.
Create a class CommentSystem with the following methods:
- __init__(self) -> None - Initializes an empty commenting system.
- add_comment(self, blockId: int, userId: int, content: str) -> None - Allows a user to add a new comment to a specific block.
- get_comments(self, blockId: int) -> List[Tuple[int, str]] - Retrieves all comments made on a specific block.
- delete_comment(self, blockId: int, commentId: int) -> bool - Deletes a specific comment from a block if it exists, returning a status of success.
- Example 1:
Input: cs = CommentSystem(); cs.add_comment(1, 1, 'Great work!'); cs.get_comments(1)
Output: [(1, 'Great work!')]
Explanation: The comment added successfully appears in the retrieval.
- Constraints:
- Block IDs and User IDs are non-negative integers; Comment contents are strings up to 500 characters.

Notion helps users manage documents and notes collaboratively, necessitating a robust version control mechanism to facilitate tracking changes made to any page. This functionality must accommodate concurrent modifications from multiple users.
Create a class VersionControl with the following methods:
- __init__(self) -> None - Initializes a new version control system.
- save(self, pageId: int, content: str) -> None - Saves the content for a given pageId. Each save increments the version number for that page.
- get_version(self, pageId: int, version: int) -> str - Returns the content saved at the specified version for the given pageId or empty string if not found.
- Example 1:
Input: vc = VersionControl(); vc.save(1, 'Initial content'); vc.save(1, 'Updated content'); vc.get_version(1, 1)
Output: 'Initial content'
Explanation: The first saved version for page 1 is retrieved successfully.
- Constraints:
- Page IDs are non-negative integers and contents are strings with length up to 1000.

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.