Skip to main content
All Questions

Optimize Manager Employee Lookup

Easy
Unlock detailed company stats for this questionUpgrade

You'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.

Starter code and solution
Python 3.11+ (standard library)
Download code

What's in the codebase

  • file.py. The code under review. p_m_e_rel takes 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 import p_m_e_rel by 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 --sizes to 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.

Related courses

Course

AI Engineering Interview Prep

Ace the AI engineering interview at top companies like Google, Anthropic, Meta, and OpenAI. Learn from detailed frameworks, example questions, and mock interviews with senior engineers. Practice system design, AI/ML concepts, AI-assisted coding, and behavioral rounds.

Course

Generative AI Interviews

Ace your interviews at AI-first and AI-powered companies. Learn to explain how Gen AI really works, where it fails, and how to use it responsibly. Understand how top tech companies build and deploy AI products and how generative AI works in production, from LLMs and RAG systems to real-world deployment.