Shortest Path Avoiding Compromise | Dataford Interview Questions

Given a network topology represented as a graph, find the shortest path between two nodes that avoids a set of compromised servers at Intuit.

Treat the graph as directed and weighted, with nonnegative edge latencies. Return the node sequence for the minimum-latency safe path, or [] if no such path exists. The path must also be empty when start or end is compromised.

Input: graph is a dictionary mapping each node to [neighbor, latency] pairs; start, end, and compromised are strings and a list of strings. Output: return a list of node names.

Example: graph = {"gateway": [["backup", 5]], "backup": [["payroll", 1]], "payroll": []}, start = "gateway", end = "payroll", compromised = [] returns ["gateway", "backup", "payroll"].

Constraints: Up to 10^4 nodes and 10^5 directed edges; latencies are nonnegative integers.

Constraints

The graph contains at most 10^4 nodes and 10^5 directed edges
Each adjacency entry is a pair of a node name and a nonnegative integer latency
Node names are unique strings
The graph may omit nodes with no outgoing edges
The returned path must contain no compromised node

Function Signature

def shortest_safe_path(graph, start, end, compromised):

Your question is Shortest Path Avoiding Compromise. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem