Solve hierarchy distance and digit-square convergence
Company: BlackRock
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Take-home Project
You have two independent tasks:
A) Organization hierarchy distance
Given a list of (employee, manager) pairs that form a complete hierarchy (a single connected tree), and a query with two employee names, compute the number of reporting levels between the two employees. If the employees are the same person, return 0. The two people may be in different branches (no direct managerial line). Input format: first line contains the two names to compare; subsequent lines contain space-separated employee manager pairs covering the entire company. Output a single integer equal to the number of edges on the shortest path between the two employees in the hierarchy. Describe your approach (e.g., build an undirected graph and run BFS, or compute depths and use LCA), and analyze time and space complexity.
B) Digit-square convergence check
Define f(n) as the sum of the squares of the decimal digits of n. Repeatedly apply f starting from a positive integer n. Implement a function that returns true if the sequence reaches 1, and false if it falls into a cycle that does not include 1. Provide two solutions: one using extra memory (e.g., a set of seen values) and one using O(
1) space via cycle detection (e.g., Floyd’s tortoise–hare). State the time and space complexities.
Quick Answer: This question evaluates understanding of tree and graph modeling, shortest-path reasoning, iterative function behavior and cycle detection, along with time and space complexity analysis within the Coding & Algorithms domain.
Organization Hierarchy Distance
Given employee-manager pairs, return the number of reporting edges on the shortest path between two employees.
Constraints
- Pairs form a connected hierarchy for valid employees
Examples
Input: ((('A', 'M1'), ('B', 'M1'), ('M1', 'CEO'), ('C', 'CEO')), 'A', 'C')
Expected Output: 3
Explanation: Path A-M1-CEO-C.
Input: ((('A', 'M'),), 'A', 'A')
Expected Output: 0
Explanation: Same employee.
Input: ((('A', 'M'),), 'A', 'Z')
Expected Output: -1
Explanation: Missing employee.
Hints
- Treat manager relationships as undirected edges and BFS.
Digit-Square Convergence
Return whether repeatedly replacing n by the sum of squared digits eventually reaches 1.
Examples
Input: (19,)
Expected Output: True
Explanation: Happy number.
Input: (2,)
Expected Output: False
Explanation: Falls into a non-1 cycle.
Input: (1,)
Expected Output: True
Explanation: Already converged.
Input: (7,)
Expected Output: True
Explanation: Another happy number.
Hints
- Floyd cycle detection avoids storing seen values.