Notion Frontend Engineer Interview Questions

Notion allows multiple users to edit a page simultaneously. In order to keep track of the changes made by users, you are tasked with implementing a system that records revisions based on timestamps. Use a heap to maintain the last n changes made on the page with the given timestamps.

Problem Statement:

You are given an array of revision records where each record consists of a string user, a string change, and an integer timestamp. Implement a ChangeLog class, which maintains the n most recent changes in their chronological order. The class should support the following methods:

• addChange(user: str, change: str, timestamp: int): Adds a new change to the log.


• getRecent(n: int) -> List[str]: Returns a list of the last n changes in chronological order of their timestamps.

Example 1:

Input:

log = ChangeLog(3)
log.addChange("Alice", "Added a new section", 1)
log.addChange("Bob", "Fixed a typo", 2)
log.addChange("Alice", "Updated the header", 3)
log.getRecent(2)

Output: ['Fixed a typo', 'Updated the header']

Example 2:

Input:

log.addChange("Charlie", "Removed a line", 4)
log.getRecent(3)

Output: ['Added a new section', 'Fixed a typo', 'Updated the header']

Constraints:

• 1 <= n <= 1000


• 1 <= timestamp <= 10^6

Notion's collaborative interface demands efficient rendering of content for real-time updates and smooth interactions. Implement a function to calculate the maximum number of unique words that can be displayed within a sliding window of a given size.

Problem Statement:

You are given a string text which represents a Notion page's content, and an integer k representing the size of the sliding window. Your task is to find the maximum number of unique words present in any contiguous substring of text with length k. You need to return this maximum count.

Example 1:

Input: text = "This is a sample Notion page, Notion pages are great!", k = 20
Output: 8
Explanation: "a sample Notion page, Notion pages are" contains 8 unique words.

Example 2:

Input: text = "Test Test Test!", k = 10
Output: 2
Explanation: The unique words in the substring of length 10 are "Test Test" which contains 2 unique words.

Constraints:

• 1 <= k <= text.length


• text.length <= 10^5

Notion's API requires efficient handling of frequent requests to improve performance and response times. Implement an LRU (Least Recently Used) Cache to store recent results of API calls, allowing quick retrieval of data with minimal latency.

Problem Statement:

You need to design an LRUCache class with the following methods:

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


• put(key: int, value: int): Updates or inserts the value by the key. 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

Example 2:

Input:

cache.put(4, 4)
cache.get(1)
cache.get(3)
cache.get(4)

Output: -1
3
4

Constraints:

• 1 <= capacity <= 3000


• 1 <= key, value <= 10^4

Notion’s user-friendly interface requires an intuitive Rich Text Editor that supports various text formats and rich content such as images or links. You need to design a class that represents this editor, allowing users to perform operations such as adding text, changing the format, and retrieving the current content.

Problem Statement:

Implement a RichTextEditor class that supports the following operations:

• addText(text: str): Adds plain text to the document.


• formatText(start: int, end: int, format: str): Applies the specified format (like bold, italic, underline) from start to end indices.


• getContent() -> str: Returns the current content of the editor as a string, preserving formatting information.

Example 1:

Input:

editor = RichTextEditor()
editor.addText("Hello")
editor.addText(" World")
editor.formatText(0, 5, "bold")
editor.getContent()

Output: '<b>Hello</b> World'

Example 2:

Input:

editor.formatText(6, 11, "italic")
editor.getContent()

Output: '<b>Hello</b> <i>World</i>'

Constraints:

• 1 <= text.length <= 1000