Optimize Manager Employee Lookup
EasyYou're in a live coding round. The interviewer shares a small Python codebase with a function that prints every employee in a company next to the name of their manager. The output is correct. On a few thousand employees it starts to crawl, and on a real company directory it would crawl for much longer.
Your job is to find out why, explain it, and rebuild the lookup so the work grows linearly with the size of the organization, without changing a single line of output.
What's in the codebase
file.py. The code under review.p_m_e_reltakes a list of employee dictionaries and prints one line per employee. The names are cryptic on purpose. This is the only file you change.test_runner.py. Six correctness tests: a flat organization, a chain of four, a single CEO, an invalid manager ID, an empty list, and two top-level executives. They importp_m_e_relby name.scenarios.py. The timing harness. It builds organizations of 500, 1,000, and 2,000 employees with each manager placed after their reports, times the printer on each, and shows how much slower each size is than the last. Pass--sizesto choose your own.instructions.md. Restates what the printer does and the run commands.
Out of the box, all six tests pass and each doubling of the organization roughly quadruples the runtime. That's the starting state.
Your task
The interviewer's prompt is to refactor the printer from O(n²) to O(n) and leave it readable and maintainable.
Each employee is a dictionary with three keys: 'i' for the ID, 'n' for the name, and 'm' for the manager's ID, where None means no manager. The printer outputs one line per employee, in input order:
Employee: {name} (ID: {id}) -> Manager: {manager}
If an employee has no manager, or their manager ID matches no one in the list, the manager prints as None (Top Level). The tests check every line exactly, including that fallback.
Trace the starter out loud and explain why it's quadratic before you change anything. You're done when all six tests still pass and doubling the organization roughly doubles the runtime instead of quadrupling it. At the default sizes your version may finish too fast to measure, so rerun with python3 scenarios.py --sizes 25000 50000 100000. Timings at this scale are noisy, so run it two or three times and ignore a one-off spike.
The org-chart follow-up
Once your refactor passes, the interviewer changes the output: instead of flat lines, print the whole hierarchy as an indented tree, with each manager above their reports.
Talk through how your design changes before you write code. Then consider what happens to your tree if two employees list each other as manager.
Using AI on this problem
Interviewers usually run this round at the research-only or limited-context level. Use AI to check dictionary syntax or to trace what a loop does, for example "Explain what this inner loop searches for on each iteration." Don't simply ask it to refactor the file for you. Finding the repeated scan, choosing the data structure, and handling the edge cases is the evidence the interviewer is there to collect.
Why the starter is quadratic
For every employee, the inner loop scans the list from the start to find the manager. scenarios.py places each manager after their reports, so that scan walks most of the list every time: about n²/2 comparisons for n employees. Doubling n quadruples the work, which is what the timing column shows. The break doesn't help, because the match is near the end.
Approach
- Build a dictionary from employee ID to name in one pass.
- In a second pass, look up each manager's name in constant time. A missing or
Nonemanager ID falls back toNone (Top Level). - Rename everything so it says what it holds. Keep
p_m_e_relas an alias, because the tests import it by that name.
PythonTOP_LEVEL = "None (Top Level)"
def print_manager_relationships(employees):
name_by_id = {}
for employee in employees:
name_by_id.setdefault(employee["i"], employee["n"])
for employee in employees:
manager_name = name_by_id.get(employee["m"], TOP_LEVEL)
print(f"Employee: {employee['n']} (ID: {employee['i']}) -> Manager: {manager_name}")
p_m_e_rel = print_manager_relationships # the tests import the original name
This runs in O(n) time and uses O(n) extra space for the dictionary. That trade, memory for time, is the sentence the interviewer is listening for.
Two details keep the output identical to the starter. setdefault keeps the first employee with a given ID, which matches the starter's break on the first match if the data ever contains duplicate IDs. A plain dictionary comprehension would keep the last one instead. And dict.get with a default handles the CEO and an invalid manager ID in one line, so neither needs a special case.
All six tests pass unchanged. Run python3 scenarios.py --sizes 25000 50000 100000 to confirm the scaling: each doubling should roughly double the time. Timings at this scale are noisy, so run it two or three times and ignore a one-off spike.
What to focus on
- Clarify the data model first. State the input and output formats before you touch the code. Most wrong turns in this problem start with a fuzzy picture of the data.
- Find the repeated scan. For every lookup, ask how many times the search runs and how far it walks. A loop inside a loop over the same list is the signature of O(n²).
- Price the optimization. Say explicitly that you're spending O(n) memory to get O(n) time.
- Design for the edge cases. The CEO, an invalid manager ID, multiple top-level executives, and an empty list should fall out of the design, not get patched in after a test fails.
The org-chart follow-up
The flat version asks one question per employee: who is my manager? A tree also needs the opposite direction: who reports to me? Build a map from each manager ID to their reports, treat every employee without a valid manager as a root, and walk depth-first from each root.
Pythonfrom collections import defaultdict
def print_org_tree(employees):
ids = {e["i"] for e in employees}
reports = defaultdict(list)
roots = []
for e in employees:
if e["m"] in ids and e["m"] != e["i"]:
reports[e["m"]].append(e)
else:
roots.append(e)
printed = set()
def walk(employee, depth):
if employee["i"] in printed:
return
printed.add(employee["i"])
print(" " * depth + employee["n"])
for report in reports[employee["i"]]:
walk(report, depth + 1)
for root in roots:
walk(root, 0)
stranded = [e["n"] for e in employees if e["i"] not in printed]
if stranded:
print("Unreachable (reporting cycle):", ", ".join(stranded))
Dirty data is where this gets interesting. If two employees list each other as manager, neither is a root, so a walk from the roots never reaches them and they silently disappear from the chart. The final check reports anyone left over instead of dropping them, and the printed set stops the walk from visiting the same ID twice. On a deep org chart, Python's default recursion limit of 1,000 also becomes a real constraint, so a strong answer switches to an explicit stack.
Leveling signals
Related courses

