In a microservice architecture, you have a set of services where each service can depend on several others. The dependency relationships form a directed acyclic graph. One service is designated as the entry point: it receives requests from users and forwards them to its dependencies, which in turn call their own dependencies, and so forth.
For a service, its load factor is the total amount of work it must process when the entry point receives exactly one unit of request load, assuming that every upstream service calls all of its dependencies concurrently. Because load can arrive from multiple upstream paths, the load factors add up along all incoming edges.
You are given a list of strings services that defines each service and its immediate dependencies in the format "<service>=<dep1>,<dep2>,...". A service may have no dependencies (e.g., "auth="). Any dependency that is not itself defined in the list is simply ignored. Every service name appears only once in the list.
You also receive a string entrypoint naming the service that acts as the entry point (it is guaranteed to be present in the list). Your task is to compute the worst‑case load factor for every service reachable from the entry point, including the entry point itself. The result must be an array of strings, each formatted as "<service>*<load_factor>", sorted in lexicographical order by the service name. Only services that are reachable from the entry point should appear in the output.
Implement the function compute_load_factors(services, entrypoint) that returns the expected array of strings.
Example 1:
Input: serviceList = ["logging=", "user=logging", "orders=user,foobar", "recommendations=user,orders", "dashboard=user,orders,recommendations"], entryPoint = "dashboard"
Output: ["dashboard*1", "logging*4", "orders*2", "recommendations*1", "user*4"]
Explanation: The dependency graph is constructed as follows:
<img src="https://res.cloudinary.com/algro/image/upload/v1744249068/production/post/67cf7c4eaca6a2fa74a72d1c/ail6yt5ihl7rqkjmuiei.png" alt="" height="400" width="550" />
Starting from dashboard (load factor = 1):
Thus, the final sorted output is ["dashboard*1", "logging*4", "orders*2", "recommendations*1", "user*4"].
Example 2:
Input: serviceList = ["A=B","B=C","C="], entryPoint = "A"
Output: ["A*1", "B*1", "C*1"]
Example 3:
Input: serviceList = ["auth=", "db=", "user=auth", "orders=user,db", "inventory=db", "shipping=orders,inventory", "reporting=shipping,user"], entryPoint = "reporting"
Output: ["auth*2", "db*2", "inventory*1", "orders*1", "reporting*1", "shipping*1", "user*2"]
Constraints: