Frontend School

Oyo Key Property Collection

DSA
hard

Oyo Key Property Collection

Hard
Graph
Dijkstra
State Space Search
Bitmask
Shortest Path

Overview

Oyo is undergoing a critical audit of its property portfolio. A specialized audit team needs to visit a specific set of "key properties" across a city to collect unique audit artifacts. These artifacts are crucial for compliance. Some properties, however, have restricted access and can only be audited if a particular prerequisite artifact has already been collected. The audit team starts at a central depot and must efficiently collect all required artifacts, then return to the depot, minimizing total travel time.

What you need to do / Task

You are tasked with implementing a function findMinAuditTime that calculates the minimum total travel time required for the audit team to:

  1. Start at the designated startNodeId (depot).
  2. Visit every keyProperty to collect its unique keyId.
  3. Adhere to all prerequisite rules, meaning a property requiring keyX cannot be entered until keyX has been collected.
  4. Return to the startNodeId after all keys have been collected.

If it's impossible to collect all keys and return, the function should return -1.

Input & Output

The function signature is: function findMinAuditTime(n: number, roads: number[][], startNodeId: number, keyProperties: number[][], prerequisites: number[][]): number

  • n: An integer representing the total number of locations in the city, indexed from 0 to n-1.
  • roads: A 2D array of integers, where roads[i] = [u, v, time] indicates a one-way road from location u to location v that takes time minutes to travel.
  • startNodeId: An integer representing the starting and ending location (the depot).
  • keyProperties: A 2D array of integers, where keyProperties[i] = [nodeId, keyId] indicates that location nodeId provides the unique artifact keyId. keyIds are 0-indexed and unique.
  • prerequisites: A 2D array of integers, where prerequisites[i] = [nodeId, requiredKeyId] indicates that nodeId can only be entered if requiredKeyId has already been collected.
  • Returns: An integer, the minimum total travel time to complete the audit, or -1 if it's impossible.

Clarifications

  • All keyIds are distinct and range from 0 to K-1, where K is the total number of unique keys (i.e., keyProperties.length).
  • Collecting a key at a keyProperty is instantaneous (does not add to travel time).
  • A property that provides a key might also have a prerequisite for entry. This prerequisite must be satisfied before entering the property.
  • If startNodeId itself has a prerequisite, it must be satisfied before starting the audit, which is impossible. Assume startNodeId never has a prerequisite.

Examples

1

Example 1

Input:

n = 3, roads = [[0,1,10], [1,2,5], [2,0,12]], startNodeId = 0, keyProperties = [[1,0], [2,1]], prerequisites = []

Output:

27

Note:

Start at 0. Path: 0 -> 1 (cost 10, collect key 0). State: (node 1, keys {0}). Then 1 -> 2 (cost 5, collect key 1). State: (node 2, keys {0,1}). Then 2 -> 0 (cost 12, return to depot). Total cost: 10 + 5 + 12 = 27.

2

Example 2

Input:

n = 4, roads = [[0,1,10], [1,2,5], [0,3,1], [3,2,1], [2,0,12]], startNodeId = 0, keyProperties = [[1,0], [2,1]], prerequisites = [[2,0]]

Output:

27

Note:

Start at 0. Node 2 requires key 0. Fastest path to collect key 0 is 0 -> 1 (cost 10). Now at node 1 with key 0. Then 1 -> 2 (cost 5). At node 2, collect key 1. All keys collected. Then 2 -> 0 (cost 12). Total: 10 + 5 + 12 = 27. Path 0->3->2 is not valid for node 2 as key 0 is not yet collected.

3

Example 3

Input:

n = 3, roads = [[0,1,10], [1,0,10]], startNodeId = 0, keyProperties = [[1,0], [2,1]], prerequisites = []

Output:

-1

Note:

Node 2 is unreachable from any other node. It's impossible to collect key 1.

Constraints

Constraints & assumptions

  • 1 <= n <= 50
  • 0 <= roads.length <= 500
  • 0 <= u, v < n, u != v
  • 1 <= time <= 1000
  • 0 <= startNodeId < n
  • 0 <= keyProperties.length <= 10 (let K = keyProperties.length)
  • 0 <= keyId < K
  • Each keyId in keyProperties is unique.
  • 0 <= prerequisites.length <= K
  • 0 <= requiredKeyId < K
  • No self-loops in roads. Duplicate roads [u, v, time] are possible; consider the minimum time if multiple paths exist directly between u and v.
  • All travel times are positive integers.

What interviewers evaluate

  • Correctness and Robustness: The solution correctly handles all edge cases, including unreachable targets, empty inputs, and various dependency structures.
  • Algorithm Design: Demonstrates a clear understanding of graph algorithms (e.g., Dijkstra, Floyd-Warshall) and how to apply them to a state-space search problem.
  • Time and Space Complexity: Optimal solution for the given constraints, with clear justification for chosen data structures and algorithms.
  • Code Quality: Clean, readable, well-structured code with appropriate variable names and comments where necessary.

Loading editor...