6. Adding Connections
In a TikTok-like social media platform, users are either verified or unverified. Unverified users cannot interact with each other in any way — neither directly nor indirectly. This means that even if there is a chain of interactions connecting unverified users through verified users, such connections must be avoided.
You are given a graphical representation of the platform. There are a total of user_nodes number of users, and their existing interactions are given in the form of two arrays, user_from and user_to, both of size m. This signifies that there is a connection between the users user_from[j] and user_to[j] for all 1 ≤ j ≤ m.
You are also given an array of unverified users, unverified.
Find out the max number of new connections that can be added while ensuring that unverified users remain isolated from each other.
Note:
- The connections are bidirectional. i.e., If user A has a connection to user B, user B also has a connection to user A.
- A user cannot have a connection to itself.
- There can be at most one connection between a given pair of users.
Example
Suppose user_nodes = 4, unverified = [1, 3], user_from = [1], user_to = [2]
The optimal solution is to connect user 4 to users 1 and 2. This adds a total of 2 new connections. No more connections can be added as users 1 and 3 cannot have a path between them.
Function Description
Complete the function maxNewConnections
Function Signature
def maxNewConnections(user_nodes: int, user_from: List[int], user_to: List[int], unverified: List[int]) -> int:
Parameters
- int user_nodes: the number of users
- int user_from[m]: the users at one end of each connection
- int user_to[m]: the users at the other end of each connection
- int unverified[k]: the users that are unverified
Returns
- int: the maximum number of edges that can be added to the graph
Constraints
- 1 ≤ user_nodes ≤ 10⁵
- 0 ≤ m ≤ 10⁵
- 0 ≤ k ≤ 10⁵
- 1 ≤ user_from[j], user_to[j], unverified[j] ≤ n
- It is guaranteed that the graph does not have any two-path connecting unverified users directly or indirectly.
Sample Case 0
Input:
6 4
1 2
1 3
2 3
3 5
2
2
4
Output:
3
Explanation:
3 new connections can be made. User 6 can be connected to Users 1, 2, and 3.
Sample Case 1
Input:
6 3
1 2
1 3
4 6
2
1
5
Output:
6
Explanation:
The initial network is:
- User 1 connected to Users 2 and 3
- User 4 connected to User 6
The optimal solution connects more verified users to User 5, ensuring unverified users remain isolated.
7. TikTok Video Marathon
The backend team at TikTok is optimizing a feature that tracks the maximum number of videos a user can watch continuously in a session without exceeding the time limit t. Each video has a fixed watch time, represented as an integer array watchTimes.
The user can start watching a video from any index and continue sequentially to the next videos but must stop if the total watch time exceeds the limit t. Importantly, if the user does not have enough time to complete a video, they will skip watching it entirely. The function should return the maximum number of videos the user can watch in a single session without exceeding the time limit.
However, the current function maxVideosWatched is inefficient, leading to delays in providing accurate watch recommendations. The task is to debug and optimize this function.
Implementation Description
Fix and optimize the function maxVideosWatched in the editor below.
Function Signature:
def maxVideosWatched(watchTimes: List[int], t: int) -> int:
Parameters:
- int watchTimes[n]: A list of integers representing the view count of each video.
- int t: The maximum total time a user can watch videos.
Returns:
- int: The maximum number of consecutive videos the user can watch without exceeding the time limit.
Constraints
- 1 ≤ n ≤ 2 × 10⁵
- 1 ≤ t ≤ 10⁹
- 1 ≤ watchTimes[i] ≤ 10³
Sample Case 0
Input:
3
2 2 3
3
Output:
1
Explanation:
The user can only watch one video within the 3-minute time limit.
Sample Case 1
Input:
4
3 1 2 1
5
Output:
3
我们长期稳定承接各大科技公司如TikTok、Google、Amazon等的OA笔试代写服务，确保满分通过。如有需求，请随时联系我们。
We consistently provide professional online assessment services for major tech companies like TikTok, Google, and Amazon, guaranteeing perfect scores. Feel free to contact us if you're interested.
