Solve hierarchy distance and digit-square convergence
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(
- space via cycle detection (e.g., Floyd’s tortoise–hare). State the time and space complexities.