FastPrepMinimum Service Cold Starts

Minimum Service Cold Starts

InMobi logoInMobi● HardNEW GRADOA
Learn

Problem statement

A platform contains services numbered from 1 through serviceCount. Each dependency pair [service, dependency] means that starting dependency automatically starts service. Automatic starts continue transitively.

You may cold-start any service directly. Return the minimum number of cold starts required to start every service.

Function

minimumColdStarts(serviceCount: int, dependencies: int[][]) → int

Examples

Example 1

serviceCount = 5dependencies = [[2,1],[3,2],[5,4]]return = 2

Cold-start services 1 and 4; they transitively start 2, 3, and 5.

Example 2

serviceCount = 3dependencies = [[2,1],[3,2],[1,3]]return = 1

Every service lies in one dependency cycle, so starting any one starts all three.

Constraints

  • 1 <= serviceCount <= 100000
  • 0 <= dependencies.length <= 200000
  • Each pair contains two valid service numbers.
  • Duplicate dependency pairs may appear and do not change the answer.

Source note: Interview prompt excerpt preserved as source evidence.

More InMobi problems

See InMobi hiring insights
public int minimumColdStarts(int serviceCount, int[][] dependencies) {
    // Write your code here.
}
serviceCount5
dependencies[[2,1],[3,2],[5,4]]
expected2
Checking account…