Notion Interview Questions

Design a class structure that simulates a collaborative posting system similar to a Twitter feed in Notion. Users should be able to post messages, follow each other, and retrieve feeds from followed users in the correct order.Class Signature:
- class TwitterFeed:
- def __init__(self): Initializes the Twitter feed object.
- def post(self, userId: int, tweetId: int) -> None: Posts a tweet for a user.
- def follow(self, followerId: int, followeeId: int) -> None: Allows follower to follow a followee.
- def unfollow(self, followerId: int, followeeId: int) -> None: Allows follower to unfollow a followee.
- def getFeed(self, userId: int) -> List[int]: Retrieves the 10 most recent tweet IDs in the order they were posted.Example 1:
Input: twitter = TwitterFeed() and twitter.post(1, 5) and twitter.follow(1, 2) and twitter.getFeed(1)
Output: [5]
Explanation: User 1 posts a tweet and follows user 2.Example 2:
Input: twitter.post(2, 6)
Output: [6, 5]
Explanation: User 2 posts a tweet, and user 1 gets the feed with both tweets in the right order.

Constraints:**
- 1 <= userId, followerId, followeeId <= 10^4
- 0 <= tweetId <= 10^4
- The operations' total number does not exceed 1000.

In Notion, caching is critical for performance, especially for frequent API requests. Implement an LRU (Least Recently Used) Cache to store API responses and efficiently handle eviction of the least recently accessed items.Class Signature:
- class LRUCache:
- def __init__(self, capacity: int): Initializes the LRU Cache with a capacity.
- def get(self, key: int) -> int: Fetches the value from the cache.
- def put(self, key: int, value: int) -> None: Updates the cache with a new key-value pair or updates the value if the key exists.Example 1:
Input: cache = LRUCache(2) and cache.put(1, 1) and cache.put(2, 2) and cache.get(1)
Output: 1
Explanation: Cache contains {1=1, 2=2} and fetching key 1 returns 1.Example 2:
Input: cache.put(3, 3)
Output: None
Explanation: Previously added key 2 will be evicted due to LRU policy.Constraints:
- 1 <= capacity <= 3000
- 0 <= key, value <= 10^4

Notion allows users to create various types of blocks that can include textual content, images, and to-do lists. We want to generate all possible Markdown representations from given block types.
The task is to implement a function to produce all combinations of Markdown representations for these blocks using backtracking.Function Signature:
- def generateMarkdown(blocks: List[str]) -> List[str]:
where blocks contains strings representing different block types like 'text', 'image', 'todo'.Example 1:
Input: blocks = ['text', 'image']
Output: ['text', 'image', 'text
image', 'image
text']
Explanation: Each block can occupy a position individually or combined in a sequence.Example 2:
Input: blocks = ['text', 'todo']
Output: ['text', 'todo', 'text
todo', 'todo
text']Constraints:
- 1 <= blocks.length <= 10
- blocks[i] consists of unique types only.

In Notion, when many users are editing a shared document, we need to maintain a view of their changes in real time. Using the sliding window technique can help us efficiently track the changes.
The problem is to implement a function that can track the number of changes made within a specific viewing window of time.Function Signature:
- def countChanges(changes: List[Tuple[int, int]], window: int) -> int: where changes is a list of tuples representing changes with start and end times.Example 1:
Input: changes = [(1, 4), (2, 5), (5, 7)], window = 3
Output: 3
Explanation: Changes are made at times 1, 2, 4, 5, 6, 7; within the window [1, 4], there are 3 changes.Example 2:
Input: changes = [(1, 2), (2, 6), (5, 10)], window = 5
Output: 3
Explanation: All changes occur within the single 5 unit time frame.Constraints:
- 1 <= changes.length <= 10^5
- 1 <= changes[i][0], changes[i][1] <= 10^9