Compute Load Factors in a Service Dependency DAG
Company: Robinhood
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
# Compute Load Factors in a Service Dependency DAG
For this portable practice version, implement `computeLoadFactors(services, dependencies, entry)` using the explicit interface and output convention below.
The service relationships form a directed acyclic graph. Each dependency is a pair `[caller, dependency]`. When a service handles one unit of load, it sends one unit of load to every direct dependency. The `entry` service receives one unit of external load, and load arriving through different upstream paths accumulates.
Return one `[service, load]` pair for every service, sorted by service name in ascending lexicographic order. Each `load` is an exact nonnegative base-10 integer string. A service that is unreachable from `entry` has load `"0"`.
## Constraints
- `1 <= services.length <= 100,000`
- Every service name is unique and contains 1 to 100 lowercase English letters, digits, or underscores.
- `0 <= dependencies.length <= 200,000`
- Every dependency contains two names from `services`, and directed edges are unique.
- `entry` is present in `services`.
- The complete dependency graph is a DAG.
- Loads may exceed the exact integer range of some languages, so return them as decimal strings.
## Example 1
```text
Input:
services = ["gateway", "search", "profile", "ranking", "logging", "unused"]
dependencies = [
["gateway", "search"],
["gateway", "profile"],
["search", "ranking"],
["profile", "ranking"],
["ranking", "logging"],
["unused", "logging"]
]
entry = "gateway"
Output: [
["gateway", "1"],
["logging", "2"],
["profile", "1"],
["ranking", "2"],
["search", "1"],
["unused", "0"]
]
```
The edge from `unused` contributes no load because `unused` cannot be reached from `gateway`.
## Example 2
```text
Input:
services = ["api", "a", "b", "db"]
dependencies = [
["api", "a"],
["api", "b"],
["a", "db"],
["b", "db"]
]
entry = "api"
Output: [
["a", "1"],
["api", "1"],
["b", "1"],
["db", "2"]
]
```
Service `db` receives one unit through `a` and one through `b`, so its load factor is `2`.
Overview: Compute exact service load factors as one entry request propagates through a dependency DAG and converging paths accumulate. The question defines unreachable services, lexical output order, arbitrary-size decimal results, and a portable interface for large service graphs.
Read the full Robinhood Software Engineer interview experience this question came from
Given unique service names, unique directed dependency edges [caller, dependency] forming a DAG, and an entry service, propagate one unit of external load from entry. Each unit handled by a service sends one unit to every direct dependency, so load arriving along different directed paths accumulates. Return one [service, load] pair for every service in ascending lexicographic service-name order. Serialize each exact nonnegative load as a base-10 string, including 0 for services unreachable from entry.
Constraints
- 1 <= services.length <= 100,000
- Every service name is unique and contains 1 to 100 lowercase English letters, digits, or underscores.
- 0 <= dependencies.length <= 200,000
- Every dependency names two services, directed edges are unique, and the complete graph is a DAG.
- entry is present in services.
- Loads can exceed fixed-width and JavaScript safe-integer ranges and must be returned as exact decimal strings.
Examples
Input: (['solo'], [], 'solo')
Expected Output: [['solo', '1']]
Explanation: The entry is the only service and receives the one external unit.
Input: (['gateway', 'search', 'profile', 'ranking', 'logging', 'unused'], [['gateway', 'search'], ['gateway', 'profile'], ['search', 'ranking'], ['profile', 'ranking'], ['ranking', 'logging'], ['unused', 'logging']], 'gateway')
Expected Output: [['gateway', '1'], ['logging', '2'], ['profile', '1'], ['ranking', '2'], ['search', '1'], ['unused', '0']]
Explanation: The first source example accumulates two entry paths at ranking and logging while unused contributes zero.
Hints
- The load of a reachable service equals the number of directed paths from entry to it.
- A topological order lets every predecessor finish contributing before a service propagates its load.