Solve hierarchy distance and digit-square convergence
Problem Description
This take-home project consists of two independent algorithmic tasks designed to assess your problem-solving skills, algorithmic knowledge, and ability to analyze complexity.
A) Organization Hierarchy Distance
Given a list of (employee, manager) pairs that collectively form a complete organizational hierarchy (a single connected tree structure), and a query consisting of two employee names, compute the number of reporting levels (edges) between these two employees.
- If the two employees are the same person, the distance is 0.
- The two individuals may reside in different branches of the hierarchy, meaning there may not be a direct managerial line between them.
- The input format specifies that the first line contains the two employee names to compare, followed by subsequent lines, each containing a space-separated
employee managerpair that covers the entire company's hierarchy. - Your function should output a single integer representing the number of edges on the shortest path between the two employees in the hierarchy graph.
Deliverables:
- Describe your chosen approach (e.g., building an undirected graph and running BFS, or computing depths and utilizing a Lowest Common Ancestor (LCA) algorithm).
- Analyze the time and space complexity of your solution.
B) Digit-Square Convergence Check
Define a function f(n) as the sum of the squares of the decimal digits of a positive integer n. For example, f(123) = 1^2 + 2^2 + 3^2 = 1 + 4 + 9 = 14.
You are to repeatedly apply this function f starting from an initial positive integer n. Implement a function that determines whether this sequence of numbers eventually reaches 1 or if it instead enters a cycle that does not include 1.
- Return
trueif the sequence converges to 1. - Return
falseif the sequence falls into a cycle that does not contain 1.
Deliverables:
- Provide two distinct solutions:
- One solution that utilizes extra memory (e.g., a set or hash table to store seen values).
- One solution that uses O(1) extra space for cycle detection (e.g., employing Floyd’s Tortoise and Hare algorithm).
- For both solutions, clearly state their respective time and space complexities.
AI interview prep
Core dilemma
The core dilemma is demonstrating a broad and deep understanding of fundamental graph algorithms (tree traversal, LCA) and number theory/cycle detection, while also managing time/space complexity trade-offs for each independent problem. It's a test of algorithmic versatility and analytical rigor across distinct domains.
2 tradeoffs and 2 stress tests locked
Interview prep
Unlock the interviewer X-Ray rubric, tradeoff matrix, stress tests, clarifying questions, and key concepts.
Solve hierarchy distance and digit-square convergence
Problem Description
This take-home project consists of two independent algorithmic tasks designed to assess your problem-solving skills, algorithmic knowledge, and ability to analyze complexity.
A) Organization Hierarchy Distance
Given a list of (employee, manager) pairs that collectively form a complete organizational hierarchy (a single connected tree structure), and a query consisting of two employee names, compute the number of reporting levels (edges) between these two employees.
- If the two employees are the same person, the distance is 0.
- The two individuals may reside in different branches of the hierarchy, meaning there may not be a direct managerial line between them.
- The input format specifies that the first line contains the two employee names to compare, followed by subsequent lines, each containing a space-separated
employee managerpair that covers the entire company's hierarchy. - Your function should output a single integer representing the number of edges on the shortest path between the two employees in the hierarchy graph.
Deliverables:
- Describe your chosen approach (e.g., building an undirected graph and running BFS, or computing depths and utilizing a Lowest Common Ancestor (LCA) algorithm).
- Analyze the time and space complexity of your solution.
B) Digit-Square Convergence Check
Define a function f(n) as the sum of the squares of the decimal digits of a positive integer n. For example, f(123) = 1^2 + 2^2 + 3^2 = 1 + 4 + 9 = 14.
You are to repeatedly apply this function f starting from an initial positive integer n. Implement a function that determines whether this sequence of numbers eventually reaches 1 or if it instead enters a cycle that does not include 1.
- Return
trueif the sequence converges to 1. - Return
falseif the sequence falls into a cycle that does not contain 1.
Deliverables:
- Provide two distinct solutions:
- One solution that utilizes extra memory (e.g., a set or hash table to store seen values).
- One solution that uses O(1) extra space for cycle detection (e.g., employing Floyd’s Tortoise and Hare algorithm).
- For both solutions, clearly state their respective time and space complexities.