ByteDance Interview Questions

1. Background: ByteDance's applications often rely on search functionalities to provide users with relevant content promptly. Hence, finding the optimal substring within a string that contains all required characters is crucial for a better user experience.
2. Problem statement: Given a string s and a string t, return the smallest substring of s that contains all the characters of t. If no such substring exists, return an empty string.
3. Function/class signature:
- def min_window(s: str, t: str) -> str:
4. Example 1:
- Input: s = "ADOBECODEBANC", t = "ABC"
- Output: "BANC"
- Explanation: The smallest substring that contains all characters of t is "BANC".
5. Example 2:
- Input: s = "A", t = "AA"
- Output: ""
- Explanation: There is no substring that contains all characters of t, hence the return is an empty string.
6. Constraints:
- 1 <= len(s) <= 10^5
- 1 <= len(t) <= 10^5
- Strings s and t consist of only printable ASCII characters.

Background: In ByteDance's recommendation algorithms, traversing tree-like structures efficiently is crucial for tasks such as configuring user feeds based on hierarchical data. Understanding tree traversal is fundamental for this purpose.
Problem statement: Given a binary tree, implement an in-order traversal that returns the values of the nodes in the order they are visited. The method should utilize a stack to achieve this functionality iteratively. Use TreeNode to represent each node in the binary tree.
Function/class signature:

• def inorder_traversal(root: Optional[TreeNode]) -> List[int]:

Example 1:

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


• Output: [1, 3, 2]


• Explanation: The in-order traversal of the tree visits nodes in the sequence: left child, root, right child. Here, node 1 has no left child, then visits node 2's left child (3) and finally node 2 itself.

Example 2:

• Input: root = [3, 1, 4]


• Output: [1, 3, 4]


• Explanation: The traversal visits node 1 (left child), then node 3 (root), followed by node 4 (right child).

Constraints:

• The number of nodes in the tree is between 0 and 1000.


• Node values are integers between -1000 and 1000.

Background: ByteDance often deals with large datasets, requiring efficient storage and retrieval operations. A Binary Search Tree is a fundamental data structure that allows for efficient querying of ordered data, making it ideal for applications involving user preferences or content ranking.
Problem statement: Implement a class BinarySearchTree that supports basic operations such as insert, find, and delete while maintaining the BST properties. Ensure these operations have an average time complexity of O(log n).
Function/class signature:

• class BinarySearchTree:


• def insert(self, value: int) -> None:


• def find(self, value: int) -> bool:


• def delete(self, value: int) -> None:

Example 1:

• Input: bst = BinarySearchTree()


• Operation: bst.insert(10)


• Operation: bst.insert(5)


• Operation: bst.find(10)


• Output: True


• Explanation: The number 10 was inserted successfully and exists in the tree.

Example 2:

• Input: bst = BinarySearchTree()


• Operation: bst.insert(20)


• Operation: bst.insert(15)


• Operation: bst.delete(20)


• Operation: bst.find(20)


• Output: False


• Explanation: After deleting 20, it no longer exists in the tree.

Constraints:

• Values to be inserted are integers between -10^5 and 10^5.


• Up to 10^4 insertions and deletions can be performed.

Background: ByteDance manages large social networks where users interact and follow each other. Finding the shortest path between users can be critical for recommending new connections.
Problem statement: Given a directed graph where each node represents a user and directed edges represent the following relationship, implement a function to find the shortest path between two users. If no path exists, return an empty list.
Function/class signature:

• def shortest_path(graph: Dict[str, List[str]], start: str, end: str) -> List[str]:

Example 1:

• Input: graph = {'A': ['B', 'C'], 'B': ['D'], 'C': ['D'], 'D': []}


• Output: ['A', 'B', 'D']


• Explanation: The shortest path from user 'A' to 'D' is through 'B'.

Example 2:

• Input: graph = {'A': ['B'], 'B': ['C'], 'C': ['D'], 'D': []}


• Output: ['A', 'B', 'C', 'D']


• Explanation: The path from 'A' to 'D' is sequential through 'B' and 'C'.

Constraints:

• 1 <= |graph| <= 10^4


• Each node has at most 10 outgoing edges


• Start and end nodes are guaranteed to be in the graph.

Background: ByteDance's products often deal with user engagement analytics, where identifying patterns in user activity can provide insights for enhancing user experience. An efficient algorithm to identify the longest sequence of consecutive active users can be crucial for product teams.
Problem statement: Given an unsorted array of integers representing user_ids, your task is to find the length of the longest consecutive sequence of user_ids. You must do this in linear time complexity, O(n).
Function/class signature:

• def longest_consecutive(user_ids: List[int]) -> int:

Example 1:

• Input: [100, 4, 200, 1, 3, 2]

- Output: 4
- Explanation: The longest consecutive sequence is [1, 2, 3, 4], which has length 4.
Example 2:

• Input: [0, 0, 1, 2, 2]

- Output: 3
- Explanation: The longest consecutive sequence is [0, 1, 2], which has length 3.
Constraints:

• 0 ≤ user_ids.length ≤ 10^4


• -10^9 ≤ user_ids[i] ≤ 10^9

1. Background: ByteDance operates a large-scale content platform that requires efficient user recommendations based on connections between users and content. Analyzing these connections can help improve algorithm performance and enhance user experience.
2. Problem statement: Given a graph represented as an adjacency list where each node is a user, and each edge is a connection with a cost, write a function that finds the minimum total cost to connect all users in the graph. The graph will be connected and guarantee no cycles.
3. Function/class signature:
- def min_connection_cost(graph: Dict[int, List[Tuple[int, int]]]) -> int:
4. Example 1:
- Input: graph = {0: [(1, 5), (2, 10)], 1: [(0, 5), (2, 2)], 2: [(0, 10), (1, 2)]}
- Output: 7
- Explanation: The minimum cost is obtained by connecting user 1 to user 2 (cost 2) and user 0 to user 1 (cost 5).
5. Example 2:
- Input: graph = {0: [(1, 1), (2, 4)], 1: [(0, 1), (2, 2)], 2: [(0, 4), (1, 2)]}
- Output: 3
- Explanation: The minimum cost is obtained by connecting user 0 to user 1 (cost 1) and user 1 to user 2 (cost 2).
6. Constraints:
- 1 <= len(graph) <= 1000
- The edges will be defined as List[Tuple[int, int]] where the second value is the cost, and all costs are positive integers.
- The graph is fully connected with no cycles.

Background: ByteDance applications often handle large data inputs and require optimized substring searches for algorithms that analyze user data patterns. The need for efficient text processing arises, especially in content recommendation systems.
Problem statement: Given a string s and a string t, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return an empty string. You must optimize for performance due to potentially large inputs.
Function/class signature:

• def min_window(s: str, t: str) -> str:

Example 1:

• Input: s = "ADOBECODEBANC", t = "ABC"


• Output: "BANC"


• Explanation: The minimum window substring is "BANC" which contains all characters of "ABC".

Example 2:

• Input: s = "AA", t = "AA"


• Output: "AA"


• Explanation: The whole string is the minimum window which contains all of t.

Constraints:

• 1 <= len(s), len(t) <= 1000


• s and t consist of English letters.

For efficient performance on ByteDance's content delivery platform, we need a system that caches frequently accessed user data and drops the least recently used data when the capacity is exceeded.
You are to implement an LRU (Least Recently Used) cache.Class Name: LRUCache

• Method Signature: def __init__(self, capacity: int):


• Initializes the LRU cache with positive size capacity.

• Method Signature: def get(self, key: int) -> int:


• Returns the value of the key if the key exists, otherwise returns -1.

• Method Signature: def put(self, key: int, value: int) -> None:


• Update or insert the value if the key is not already present. When the cache reaches its capacity, it should invalidate the least recently used item before inserting a new item.

Example 1:
Input: LRUCache(2);
cache.put(1, 1);
cache.put(2, 2);
cache.get(1);
Output: 1;Example 2:
Input: cache.put(3, 3); // LRU key was 2, evicts key 2
cache.get(2);
Output: -1;Constraints:

• capacity is a positive integer.


• All keys and values are in the range of 1 to 10000.


• The functions get and put are guaranteed to be called on existing keys.