Camping: Assign Campers to Sites Respecting Preferences and Capacity
Interview Experience
Problem
You have n camping sites, each with a maximum capacity. You have m groups of campers, each with a size and an ordered list of preferred site IDs. Assign each group to a site such that:
- The site's remaining capacity accommodates the group size.
- Each group gets the highest-ranked available preferred site.
Return a dict mapping group ID to assigned site ID. If a group cannot be placed, map it to null.
python
def assign_sites(sites: dict[int, int], groups: list[dict]) -> dict[int, int | None]:
# sites: {site_id: capacity}
# groups: [{"id": int, "size": int, "preferences": [site_id, ...]}]
pass
Example:
sites = {1: 4, 2: 2, 3: 6}
groups = [
{"id": 10, "size": 3, "preferences": [2, 1, 3]},
{"id": 11, "size": 2, "preferences": [1, 3]}
]
Group 10: pref site 2 (cap=2) cannot fit size 3 -> try site 1 (cap=4) -> fits. Assign 10->1.
Group 11: pref site 1 (remaining=1) cannot fit size 2 -> try site 3 (cap=6) -> fits. Assign 11->3.
**Output**: {10: 1, 11: 3}
Follow-ups
- How would you handle groups that must be placed together on the same site?
- If groups can be split across sites, how does the problem change?
- Model this as a stable matching / assignment problem. When is greedy suboptimal?
- How would you make assignments fair when multiple groups want the same top-ranked site?
Full Details
Problem
You have n camping sites, each with a maximum capacity. You have m groups of campers, each with a size and an ordered list of preferred site IDs. Assign each group to a site such that:
- The site's remaining capacity accommodates the group size.
- Each group gets the highest-ranked available preferred site.
Return a dict mapping group ID to assigned site ID. If a group cannot be placed, map it to null.
python
def assign_sites(sites: dict[int, int], groups: list[dict]) -> dict[int, int | None]:
# sites: {site_id: capacity}
# groups: [{"id": int, "size": int, "preferences": [site_id, ...]}]
pass
Example:
sites = {1: 4, 2: 2, 3: 6}
groups = [
{"id": 10, "size": 3, "preferences": [2, 1, 3]},
{"id": 11, "size": 2, "preferences": [1, 3]}
]
Group 10: pref site 2 (cap=2) cannot fit size 3 -> try site 1 (cap=4) -> fits. Assign 10->1.
Group 11: pref site 1 (remaining=1) cannot fit size 2 -> try site 3 (cap=6) -> fits. Assign 11->3.
**Output**: {10: 1, 11: 3}
Follow-ups
- How would you handle groups that must be placed together on the same site?
- If groups can be split across sites, how does the problem change?
- Model this as a stable matching / assignment problem. When is greedy suboptimal?
- How would you make assignments fair when multiple groups want the same top-ranked site?
About This Question
This is a candidate experience report from a karat interview.