Meta Medium Interview Questions

Background: In Meta's various applications, understanding how to manage hierarchical data structures effectively is crucial. Binary Search Trees (BSTs) often support dynamic data management, as seen in features that require efficient querying and storage.
Problem statement: Given an integer n, return the number of unique Binary Search Trees (BST) that can be formed using n distinct integers from 1 to n. A Binary Search Tree is defined as a tree in which all nodes follow the left < current < right property.
Function/class signature:

• def numTrees(n: int) -> int:

Example 1:
Input: n = 3
Output: 5
Explanation: The possible unique BSTs are:
1. 1 2 3
\ / \ /
2 1 1 2 2
\ \ \
3 3 1Example 2:
Input: n = 1
Output: 1
Explanation: With only 1 node, there's only 1 unique BST possible.Constraints:

• 1 <= n <= 19

Background: In Facebook's backend services, managing user connections and interactions can be complicated, especially when handling data structures like trees. This problem directly relates to how user data can be organized and transferred over the network.
Problem statement: You need to implement two methods to serialize and deserialize a binary tree. The serialize function should convert the tree into a string form, so it can be easily saved or transmitted. The deserialize function should take this string and reconstruct the binary tree. Use pre-order traversal for serialization and handle null values appropriately.
Function/class signature:

• def serialize(root: Optional[TreeNode]) -> str:


• def deserialize(data: str) -> Optional[TreeNode]:

Example 1:

• Input: root = [1,2,3,null,null,4,5]


• Output: "1,2,#,#,3,4,#,#,5,#,#"


• Explanation: The binary tree can be represented as a serialized string.

Example 2:

• Input: data = "1,2,#,#,3,4,#,#,5,#,#"


• Output: root = [1,2,3,null,null,4,5]


• Explanation: It accurately reconstructs the original binary tree from the serialized string.

Constraints:

• The number of nodes in the tree is in the range [0, 10^4].


• Each node's value is a string representing an integer in the range [-10^4, 10^4].

Background: As Meta develops features for its events platform, optimizing the number of events a user can attend without overlap is crucial for enhancing user experience.
Problem statement: You are given an array of events, where each event is represented as a pair of integers [start, end]. An individual can attend an event if they can arrive at the event's start time or after the event has started. Each event must be completed to move to the next one. Your task is to return the maximum number of events that can be attended.
Function/class signature:

• def max_events(events: List[List[int]]) -> int:

Example 1:

• Input: events = [[1,2],[2,3],[3,4]]


• Output: 3


• Explanation: All the events do not overlap, so the user can attend all three.

Example 2:

• Input: events = [[1,4],[4,6],[6,8],[3,5]]


• Output: 4


• Explanation: The user can attend all events as they fall into a sequence without overlaps.

Constraints:

• 1 <= len(events) <= 10^4


• 1 <= start <= end <= 10^5

Background: Meta's platforms involve vast amounts of user data, where identifying unique patterns can help in creating better user experiences and targeted advertisements. The 3Sum problem is integral to analyzing interactions.Problem statement: Given an integer array nums of size n, return all the unique triplets [nums[i], nums[j], nums[k]] such that i, j, and k are different indices, and their sum equals to zero. The result must not include duplicate triplets, hence the order of results does not matter.Function/class signature:

• def three_sum(nums: List[int]) -> List[List[int]]:

Example 1:
Input: nums = [-1, 0, 1, 2, -1, -4]
Output: [[-1, -1, 2], [-1, 0, 1]]
Explanation: The above combinations sum up to zero and are unique.Example 2:
Input: nums = []
Output: []
Explanation: No triplets can be formed from an empty list.Constraints:

• 0 <= n <= 3000


• -10^5 <= nums[i] <= 10^5

Background: In the context of Meta's messaging platform, ensuring efficient data presentation is crucial. Users want to see their messages organized in a specific order for improved readability and usability.
Problem statement: Given a binary tree representing the messages, where nodes contain the message sender and timestamp, implement a function that performs a level order traversal of the tree, but with each level sorted by the timestamp of the messages. Return the list of messages in the required order. Note: If there are multiple messages with the same timestamp, maintain their relative order from the original tree.
Function/class signature:

• def level_order_sorted_messages(root: Optional[TreeNode]) -> List[Tuple[str, int]]:

Example 1:

• Input: root - a tree with nodes representing messages sent by different users at various timestamps


• Output: [("Alice", 1), ("Bob", 2), ("Charlie", 3)]


• Explanation: Messages are shown in order based on their timestamps.

Example 2:

• Input: A different tree where timestamps are not in sequential order.


• Output: [("David", 4), ("Eve", 5), ("Frank", 7)]

Constraints:

• The binary tree will contain at most 10^4 nodes.


• Timestamps are non-negative integers.


• Each message is a string up to 100 characters long.

1. Background: At Meta, user experience is crucial, particularly when leveraging social graphs. Understanding user connections through complementary pairs can optimize recommendations in platforms like Facebook.
2. Problem statement: Given an array of user_ids and a target_sum, return the indices of the two user IDs such that their corresponding values add up to the target_sum. You may assume that each input would have exactly one solution, and you may not use the same element twice.
3. Function/class signature:
- def find_complementary_pair(user_ids: List[int], target_sum: int) -> List[int]:
4. Example 1:
Input: user_ids = [3, 5, 2, 8, 6], target_sum = 10
Output: [0, 3]
Explanation: User IDs 3 and 8 add up to 10.
5. Example 2:
Input: user_ids = [1, 4, 5, 6, 7], target_sum = 11
Output: [2, 3]
Explanation: User IDs 5 and 6 add up to 11.
6. Constraints:
- 2 <= len(user_ids) <= 10^4
- -10^9 <= user_ids[i] <= 10^9
- 2 <= target_sum <= 2 * 10^9