FastPrep
Problem · Array

TikTok Server Optimization

Learn this problem
● MediumTiktokNEW GRADOA
See Tiktok hiring insights

Problem statement

TikTok is organizing a grand TikTok event and wants to optimize the content delivery routes for the users.

They have numServers servers numbered from 1 to numServers. The servers are arranged in the sequence [1, 2, 3, ..., numServers].

The company has a list of numDisconnectedPairs pairs of servers that are not directly connected. Any pair not present in this list is directly connected.

A subsegment starting at server start and ending at server end is [start, start + 1, ..., end]. It is called good when every pair of servers in that segment is directly connected.

Return the number of pairs (start, end), where 1 ≤ start ≤ end ≤ numServers, whose corresponding subsegment is good.

Note: Servers can be reused across different subsegments. Each subsegment is considered independently.

Function

optimizeTikTokRoutes(numServers: int, numDisconnectedPairs: int, disconnectedPairs: List<List<Integer>>) → long

Examples

Example 1

numServers = 4numDisconnectedPairs = 2disconnectedPairs = [[1, 2], [2, 3]]return = 5

Disconnected Pairs:

(1, 2) are not directly connected. (2, 3) are not directly connected.

The good subsegments are:

  • [1]: Only one server, so it’s automatically “good”.
  • [2]: Only one server, so it’s automatically “good”.
  • [3]: Only one server, so it’s automatically “good”.
  • [4]: Only one server, so it’s automatically “good”.
  • [3, 4]: Both servers 3 and 4 are directly connected.

Constraints

  • 2 ≤ numServers ≤ 10^5
  • 0 ≤ numDisconnectedPairs ≤ 10^5
  • disconnectedPairs.length = numDisconnectedPairs
  • Each entry in disconnectedPairs contains exactly two integers xi and yi.
  • 1 ≤ xi, yi ≤ numServers
  • xi ≠ yi

More Tiktok problems

drafts saved locally
public long optimizeTikTokRoutes(int numServers, int numDisconnectedPairs, List<List<Integer>> disconnectedPairs) {
  // write your code here
}
numServers4
numDisconnectedPairs2
disconnectedPairs[[1, 2], [2, 3]]
expected5
checking account