The coding question
Our employee directory arranges groups in a hierarchy, and each employee belongs to one group. Given a set of employees, return the closest group that all of them share.
Ask a few questions first
| Ask | What we'll assume |
|---|---|
| How is the hierarchy given? | A map from each group to its parent group. The top group's parent is None. |
| Is it a tree, with one top group? | Yes. Every group has one parent, and there are no loops. |
| Does a group count as sharing itself? | Yes. If everyone's in Frontend, the answer is Frontend. |
| What if the list is empty, or a name isn't in the directory? | Raise an error. An empty list has no answer. |
| How big can it get? | Thousands of groups, and the hierarchy is usually not very deep. |
A couple of examples
| Input | Output |
|---|---|
| Company > Engineering > Frontend > Design, Engineering > Backend, Company > Sales. Ana in Design, Ben in Frontend: [Ana, Ben] | Frontend |
| Same directory, Cy in Backend: [Ana, Ben, Cy] | Engineering |
| Same directory, Dee in Sales: [Ana, Dee] | Company |
Start with brute force
For each employee, walk up from their group to the top and collect the path. Then go through the first person's path from the bottom, and return the first group that's in every other person's path.
Cost: with k employees and a hierarchy h levels deep, building the paths is O(k × h). Checking each group against every path as a list is O(h × k × h). Using sets gets it down to O(k × h), which is already fine.
A better way
This is the lowest common ancestor problem: the deepest group that sits above everyone. The usual version is for two nodes. With more people, you can fold it: the shared group of A, B and C is the shared group of (A and B's shared group) and C.
For two groups, bring the deeper one up until both are at the same depth. Then step both up together until they meet. That uses no extra memory beyond the depths.
- Look up the first employee's group. That's the answer so far.
- For each other employee, find the shared group of their group and the answer so far.
- To do that, work out each group's depth by counting steps to the top.
- Move the deeper group up until both are at the same depth.
- Move both up one step at a time until they're the same group. That's the new answer.
The code
def closest_shared_group(parent, employee_group, employees):
if not employees:
raise ValueError("need at least one employee")
def depth(group):
d = 0
while parent[group] is not None:
group = parent[group]
d += 1
return d
def lca(a, b):
da, db = depth(a), depth(b)
while da > db:
a = parent[a]
da -= 1
while db > da:
b = parent[b]
db -= 1
while a != b:
a = parent[a]
b = parent[b]
return a
answer = employee_group[employees[0]]
for person in employees[1:]:
answer = lca(answer, employee_group[person])
return answer| Cost | Why | |
|---|---|---|
| Time | O(k × h) | Each of the k employees does a couple of walks up at most h levels |
| Space | O(1) extra | Only a few variables, no paths stored |
Test it
Walk through one of the examples out loud, then check the cases that tend to break things:
- One employee: return their own group.
- Two people in the same group: return that group.
- One person's group is above another's, like Ana in Design and Ben in Frontend: the answer is the higher group, Frontend.
- People in completely different branches: the answer is the top group.
- An unknown employee: the dictionary lookup raises a KeyError. Say that's what you'd want, or check first and raise something clearer.
Common mistakes
- Not moving the deeper group up first. Without that, the two walks pass each other and never meet.
- Forgetting a group can be its own answer. If one person's group is above the others, it's the answer, not its parent.
- Comparing groups by name when two groups share a name in different places. Use unique IDs if names can repeat.
- Recomputing depth from scratch in a loop that's already deep. Here it's fine, but cache depths if you'll ask many times.
Follow-up questions
What if you'll answer thousands of these queries?
Work out every group's depth once and store it, and keep jump tables so you can go up many levels at a time. Each query then costs about log of the depth per person.
What if an employee can be in more than one group?
Then it's not a single path up anymore. Walk up from all of a person's groups to get the set of groups above them, intersect those sets across people, and pick the deepest one.
What if the hierarchy changes often?
The fold above uses no precomputed tables, so it handles changes for free. Stored depths or jump tables would need updating after every move.
How the time adds up
| Minutes | What you're doing |
|---|---|
| 0–5 | Ask questions and agree on the input format |
| 5–10 | Brute force: collect paths and compare |
| 10–20 | Spot it's lowest common ancestor, and fold over people |
| 20–35 | Write the code |
| 35–40 | Test with the examples and edge cases |
| 40–45 | Follow-up questions |
Key concepts used here
- Trees and recursionSolve tree problems by deciding what each node returns.
- Graph traversal and shortest pathsBFS, DFS and Dijkstra, and when to use each.
- Hash maps and sliding windowsSwap nested loops for a single pass.
We wrote this sample solution ourselves. Practice Loop is independent and isn't affiliated with or endorsed by Atlassian.