TikTok Interview Questions

Background: With the growth of user-generated content, TikTok needs to identify and analyze influencer groups to improve marketing strategies. Understanding how users are connected through likes and follows can help in targeted advertising and trend forecasting.
Problem statement: Given a directed graph represented by an adjacency list, where each node represents a user and a directed edge from user A to user B means that user A follows user B, write a function to find all strongly connected components (SCCs) in the graph. An SCC is a subgraph where every vertex can be reached from every other vertex. Implement the function find_scc(graph: List[List[int]]) -> List[List[int]] that returns a list of lists, where each inner list is a component.
Function/class signature:

• def find_scc(graph: List[List[int]]) -> List[List[int]]:

Example 1:

• Input: graph = [[1], [2], [0], [4], [5], [4]]


• Output: [[0, 1, 2], [4, 5]]


• Explanation: The nodes 0, 1, 2 form one SCC and nodes 4, 5 form another since 4 follows 5.

Example 2:

• Input: graph = [[1], [], [3], [2]]


• Output: [[0, 1], [2, 3]]


• Explanation: Node 0 connects to 1, forming an SCC. Nodes 2 and 3 form another because each can reach the other.

Constraints:

• 1 <= graph.length <= 1000


• 0 <= graph[i].length <= graph.length


• Each node identifier is within the range of the list index.

Background: TikTok relies on understanding user preferences to suggest relevant content. This problem is related to the algorithm used to find complementary videos for recommendations.
Problem statement: Given an array of n integers representing the duration of videos, your task is to find if there exists a pair of videos such that their duration sums up to a target value targetDuration. Return the indices of these two videos in an array.
Function/class signature:

• def find_video_pair(videos: List[int], targetDuration: int) -> List[int]:

Example 1:
Input: videos = [20, 15, 30, 10, 25], targetDuration = 35
Output: [0, 2]
Explanation: The videos with durations 20 and 15 sum up to 35.Example 2:
Input: videos = [10, 5, 7, 8], targetDuration = 17
Output: [1, 3]
Explanation: The videos with durations 5 and 12 sum up to 17.Constraints:

• 2 <= n <= 10^4


• 1 <= videos[i] <= 10^3


• 1 <= targetDuration <= 2 * 10^3

Background: In TikTok, users often browse content that requires a recommendation algorithm to ensure efficient and personalized video feeds. The algorithm should minimize the cost of obtaining trending videos while reaching a specific target threshold of views.
Problem statement: You are given an integer array cost where cost[i] is the cost to obtain a video at index i. You also have a target integer targetViews, which is the number of total views you want to achieve. Your task is to determine the minimum cost to obtain videos from the cost array such that the total number of views reaches or exceeds targetViews. Return the minimum cost. If it is impossible to achieve the target, return -1.
Function signature:

• def minCost(cost: List[int], targetViews: int) -> int:

Example 1:
Input: cost = [1,2,3,4,5], targetViews = 5
Output: 5
Explanation: You can obtain the video at index 4 for 5 cost, achieving exactly 5 views.
Example 2:
Input: cost = [1,2,3], targetViews = 6
Output: -1
Explanation: The total views obtainable from the videos are less than 6.
Constraints:

• 1 <= len(cost) <= 100


• 1 <= cost[i] <= 1000


• 0 <= targetViews <= 1000


• The sum of all elements in cost is guaranteed to be greater than or equal to targetViews if possible.

Background: In TikTok, understanding user engagement is critical. Analyzing the most watched videos can help in content recommendation and improving user satisfaction.
Problem statement: Given an array of videoIds representing the videos that users watched and a corresponding array of viewCounts that represents how many times each video was watched, you need to write a function that finds the k most watched videos. The function should return a list of video IDs in descending order of views.
Function/class signature:

• def most_watched_videos(videoIds: List[str], viewCounts: List[int], k: int) -> List[str]:

Example 1:

• Input: videoIds = ['v1', 'v2', 'v3', 'v4'], viewCounts = [100, 250, 150, 250], k = 2


• Output: ['v2', 'v4']


• Explanation: Videos v2 and v4 have the highest views (250).

Example 2:

• Input: videoIds = ['a', 'b', 'c', 'd'], viewCounts = [20, 10, 30, 30], k = 3


• Output: ['c', 'd', 'a']


• Explanation: Videos c and d both have 30 views, and a has 20 views.

Constraints:

• 1 <= len(videoIds), len(viewCounts) <= 10^5


• 1 <= viewCounts[i] <= 10^6


• 1 <= k <= len(videoIds)

Background: TikTok needs to efficiently handle a large volume of video metadata requests while minimizing server load. An effective caching mechanism can greatly improve response times for users when accessing popular videos.
Problem statement: Implement a class VideoMetadataCache that can store and retrieve video metadata based on video IDs. The cache should automatically evict the least recently used (LRU) entry when it reaches a maximum capacity. You need to implement two methods: get(video_id: str) -> Optional[dict] to retrieve metadata and put(video_id: str, metadata: dict) -> None to store metadata.
Function/class signature:

• def get(video_id: str) -> Optional[dict]:


• def put(video_id: str, metadata: dict) -> None:

Example 1:
Input: put('v1', {'title': 'Video 1', 'views': 1000})
Output: None
Input: get('v1')
Output: {'title': 'Video 1', 'views': 1000}
Explanation: The metadata for video ID 'v1' is successfully retrieved.
Example 2:
Input: put('v2', {'title': 'Video 2', 'views': 2000})
Input: put('v3', {'title': 'Video 3', 'views': 3000})
Input: put('v4', {'title': 'Video 4', 'views': 4000})
Input: get('v1')
Output: None
Explanation: 'v1' was evicted when adding 'v4' as it was the least recently used.
Constraints:

• Maximum cache size: 1000 entries


• Video ID will always be a non-empty string


• Metadata is a dictionary containing 'title' as a string and 'views' as an integer.

Background: TikTok needs to optimize video recommendations to enhance user engagement. A graph can efficiently represent the relationships between videos based on user interactions, such as likes and shares.
Problem statement: You are tasked with implementing a function that finds the shortest path (in terms of user views) in a graph of videos. Each video is represented as a node, and user interactions can be depicted as edges connecting these nodes. Your function should return the shortest path from a start video to a target video.
Function/class signature:

• def shortest_path_videos(graph: Dict[str, List[str]], start: str, target: str) -> List[str]:

Example 1:

• Input: graph = {"A": ["B", "C"], "B": ["C", "D"], "C": ["D"], "D": []}; start = "A"; target = "D"


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


• Explanation: The path from A to D is A -> B -> D, which has the fewest edges.

Example 2:

• Input: graph = {"A": ["B", "C"], "B": ["E"], "C": ["D", "E"], "D": [], "E": []}; start = "A"; target = "E"


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


• Explanation: The path from A to E is A -> B -> E, one of the shortest paths available.

Constraints:

• 1 <= |graph| <= 1000


• Each video name is unique.


• The path must be valid, if a path does not exist, return an empty list.