House Building: Schedule Construction Tasks Respecting Dependencies

Question

## Round 1 - Coding

## Problem

A house is built in stages. Each stage has a name, a duration in days, and a list of prerequisite stages that must be completed first. Return the minimum number of days to complete the entire house, and the order stages should be executed.

```python
def build_schedule(stages: list[dict]) -> dict:
    # stages: [{"name": str, "days": int, "deps": list[str]}]
    # returns: {"total_days": int, "order": list[str]}
    ...
```

## Example

```
stages = [
  {"name": "foundation", "days": 5,  "deps": []},
  {"name": "framing",    "days": 10, "deps": ["foundation"]},
  {"name": "roofing",    "days": 7,  "deps": ["framing"]},
  {"name": "plumbing",   "days": 4,  "deps": ["framing"]},
  {"name": "electrical", "days": 3,  "deps": ["framing"]},
  {"name": "finishing",  "days": 6,  "deps": ["roofing","plumbing","electrical"]},
]
build_schedule(stages)
# -> {"total_days": 28, "order": ["foundation","framing","plumbing","electrical","roofing","finishing"]}
# Critical path: foundation(5)+framing(10)+roofing(7)+finishing(6)=28
```

## Follow-ups

1. How do you detect a cycle in the dependency graph?
2. If multiple workers are available in parallel, how does that change the minimum duration calculation?
3. How would you identify the critical path — the sequence of stages that directly determines the total time?
4. What data structure makes topological sort most efficient here?

House Building: Schedule Construction Tasks Respecting Dependencies

Question Details

Full Details

About This Question

Topics

More Glean Interview Questions