How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Google.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Google during technical interviews.

Implement Employee Management and Expression Evaluation

Quick Overview

This question evaluates competency in designing and maintaining hierarchical data structures and in parsing and evaluating nested function-style arithmetic expressions, emphasizing tree manipulation, invariant maintenance, recursion, tokenization, and parsing skills.

Implement Employee Management and Expression Evaluation

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

You are asked to solve two independent coding tasks. ## Task 1: Employee management hierarchy Implement an `EmployeeDirectory` class that maintains a company reporting hierarchy. ### Required operations 1. `addEmployee(employeeId, managerId)` - Adds a new employee with a unique ID. - `managerId` is the ID of the employee's direct manager. - You may assume a manager is added before any employee who reports to them. 2. `removeEmployee(employeeId)` - Removes the employee with the given ID from the organization. ### Edge cases to handle - Removing a regular employee. - Removing a manager who has direct or indirect reports. - Removing the CEO or root employee. - Detecting or preventing cyclic reporting relationships. - Maintaining a valid reporting hierarchy after deletion. ### Follow-up Each employee also has: - A seniority level or rank. - An insertion order representing when the employee joined the directory. When deleting a manager, choose a replacement manager from that manager's group: 1. Prefer the employee with the highest seniority level. 2. If multiple employees have the same seniority level, choose the one who joined earliest. Update the reporting structure accordingly. ## Task 2: Expression evaluator Implement an evaluator for nested function-style arithmetic expressions such as: ```text add(2, mul(3, pow(4, 5))) ``` The evaluator should support the following operators: - Addition - Subtraction - Multiplication - Division - Exponentiation Expressions may be nested arbitrarily. You should parse the input string and return the computed numeric result. ### Follow-up Support variable-length argument lists, for example: ```text add(1, 2, 3, mul(4, 5, 6)) ``` A reasonable approach is to implement a tokenizer and a recursive-descent parser.

Quick Answer: This question evaluates competency in designing and maintaining hierarchical data structures and in parsing and evaluating nested function-style arithmetic expressions, emphasizing tree manipulation, invariant maintenance, recursion, tokenization, and parsing skills.

Part 1: EmployeeDirectory with addEmployee and removeEmployee

Implement a simplified EmployeeDirectory simulator. Employees form a single rooted reporting tree. You will process add and remove operations, ignoring invalid operations. When removing a non-root manager, that manager's direct reports are reassigned to the removed manager's manager. When removing the root, if it has direct reports, the earliest-added direct report becomes the new root and the other direct reports become direct reports of the new root. Indirect reports keep their relative structure unless their direct manager is explicitly reassigned.

Constraints

0 <= len(operations) <= 100000
1 <= employeeId <= 10^9
managerId is -1 or a positive integer
At most one root may exist at a time
A valid add must use a unique employeeId and an existing managerId, unless adding the root
Only add/remove operations are used, so cycles are prevented by rejecting duplicate/self/unknown-manager additions

Examples

Input: ([],)

Expected Output: []

Explanation: No operations leaves the directory empty.

Input: ([[1, 1, -1], [1, 2, 1], [1, 3, 1], [2, 3]],)

Expected Output: [[1, -1], [2, 1]]

Explanation: Employee 3 is a leaf and is simply removed.

Input: ([[1, 1, -1], [1, 2, 1], [1, 3, 2], [1, 4, 2], [2, 2]],)

Expected Output: [[1, -1], [3, 1], [4, 1]]

Explanation: Manager 2 is removed, so direct reports 3 and 4 now report to 1.

Input: ([[1, 1, -1], [1, 2, 1], [1, 3, 1], [1, 4, 2], [2, 1]],)

Expected Output: [[2, -1], [3, 2], [4, 2]]

Explanation: Root 1 is removed. Employee 2 was the earliest-added direct report, so 2 becomes root and 3 reports to 2. Employee 4 already reported to 2.

Input: ([[1, 1, -1], [1, 1, 1], [1, 2, 99], [1, 3, 3], [1, 4, -1], [2, 99]],)

Expected Output: [[1, -1]]

Explanation: Duplicate employees, unknown managers, self-manager additions, second roots, and missing removals are ignored.

Hints

Maintain both a parent map and a children set for each employee.
Deletion only needs to rewire the removed employee's direct reports; root deletion is the special case.

Part 2: EmployeeDirectory with Seniority-Based Replacement

Extend the EmployeeDirectory simulator so each employee also has a seniority level. Employees still form a single rooted reporting tree. When deleting a manager who has any direct or indirect reports, choose one employee from the deleted manager's entire subtree as the replacement. The replacement is the descendant with the highest seniority; ties are broken by earliest insertion order. The replacement takes the deleted manager's position, and every other descendant in that deleted manager's subtree becomes a direct report of the replacement. This flattening rule guarantees a valid hierarchy with no cycles.

Constraints

0 <= len(operations) <= 100000
1 <= employeeId <= 10^9
0 <= seniority <= 10^9
At most one root may exist at a time
A valid add must use a unique employeeId and an existing managerId, unless adding the root
If a removed employee has no descendants, it is simply deleted

Examples

Input: ([],)

Expected Output: []

Explanation: No employees are added.

Input: ([[1, 1, -1, 5], [1, 2, 1, 2], [2, 2]],)

Expected Output: [[1, -1, 5]]

Explanation: Employee 2 is a leaf, so it is removed with no replacement.

Input: ([[1, 1, -1, 1], [1, 2, 1, 3], [1, 3, 2, 10], [1, 4, 2, 5], [1, 5, 3, 8], [2, 2]],)

Expected Output: [[1, -1, 1], [3, 1, 10], [4, 3, 5], [5, 3, 8]]

Explanation: Deleting 2 considers descendants 3, 4, and 5. Employee 3 has the highest seniority, so 3 replaces 2 and 4 and 5 report to 3.

Input: ([[1, 1, -1, 1], [1, 2, 1, 4], [1, 3, 2, 7], [1, 4, 2, 7], [1, 5, 4, 5], [2, 2]],)

Expected Output: [[1, -1, 1], [3, 1, 7], [4, 3, 7], [5, 3, 5]]

Explanation: Employees 3 and 4 tie in seniority, but 3 joined earlier, so 3 replaces 2.

Input: ([[1, 1, -1, 0], [1, 2, 1, 5], [1, 3, 1, 9], [1, 4, 2, 10], [2, 1]],)

Expected Output: [[2, 4, 5], [3, 4, 9], [4, -1, 10]]

Explanation: Deleting the root considers the whole remaining company. Employee 4 has the highest seniority, so 4 becomes the new root.

Hints

Before rewiring anything, collect all descendants of the employee being removed.
The replacement can be found with key (seniority, -join_order), then the subtree can be flattened under that replacement.

Part 3: Nested Function-Style Arithmetic Expression Evaluator

Implement an evaluator for nested arithmetic expressions written in function-call style. The supported binary operators are add, sub, mul, div, and pow. Each operator in this part has exactly two arguments. Numeric literals may be integers or decimals, may be negative, and arbitrary whitespace may appear between tokens.

Constraints

1 <= len(expression) <= 10000
The expression is syntactically valid
Operators are one of add, sub, mul, div, pow
Each operator has exactly two arguments
Division by zero will not occur
Nesting depth is small enough for Python recursion

Examples

Input: ("add(2, mul(3, pow(4, 2)))",)

Expected Output: 50.0

Explanation: pow(4, 2) = 16, mul(3, 16) = 48, add(2, 48) = 50.

Input: ("sub(10, div(9, 3))",)

Expected Output: 7.0

Explanation: div(9, 3) = 3, then 10 - 3 = 7.

Input: ("mul(add(-2, 5), sub(10, 4))",)

Expected Output: 18.0

Explanation: Negative numeric literals are supported.

Input: ("42",)

Expected Output: 42.0

Explanation: A single numeric literal is a valid expression.

Input: (" div(5, 2) ",)

Expected Output: 2.5

Explanation: Whitespace is ignored and division returns a floating-point value.

Hints

A recursive parser works naturally: an expression is either a number or name '(' expression ',' expression ')'.
Avoid splitting on commas globally because commas inside nested calls should not split the current call.

Part 4: Variadic Nested Function-Style Arithmetic Expression Evaluator

Extend the function-style arithmetic evaluator so operators can accept variable-length argument lists. The supported operators are add, sub, mul, div, and pow. Semantics: add returns the sum of all arguments and add() is 0; mul returns the product of all arguments and mul() is 1; sub(a, b, c) computes a - b - c and requires at least one argument; div(a, b, c) computes a / b / c and requires at least one argument; pow(a, b, c) computes (a ** b) ** c from left to right and requires at least one argument. Numeric literals may be integers or decimals, may be negative, and whitespace is ignored.

Constraints

1 <= len(expression) <= 10000
The expression is syntactically valid
Operators are one of add, sub, mul, div, pow
add and mul may have zero or more arguments
sub, div, and pow have at least one argument
Division by zero will not occur
Nesting depth is small enough for Python recursion

Examples

Input: ("add(1, 2, 3, mul(4, 5, 6))",)

Expected Output: 126.0

Explanation: mul(4, 5, 6) = 120, then add(1, 2, 3, 120) = 126.

Input: ("sub(20, div(9, 3), 4, 5)",)

Expected Output: 8.0

Explanation: div(9, 3) = 3, so the result is 20 - 3 - 4 - 5 = 8.

Input: ("mul()",)

Expected Output: 1.0

Explanation: The empty product is defined as 1.

Input: ("add()",)

Expected Output: 0.0

Explanation: The empty sum is defined as 0.

Input: ("pow(2, 3, 2)",)

Expected Output: 64.0

Explanation: Exponentiation is evaluated left to right: (2 ** 3) ** 2 = 64.

Hints

After parsing an operator and opening parenthesis, repeatedly parse expressions separated by commas until the matching closing parenthesis.
Track parentheses through recursion rather than using a simple string split on commas.

Quick Overview

Implement Employee Management and Expression Evaluation

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Part 1: EmployeeDirectory with addEmployee and removeEmployee

Constraints

0 <= len(operations) <= 100000
1 <= employeeId <= 10^9
managerId is -1 or a positive integer
At most one root may exist at a time
A valid add must use a unique employeeId and an existing managerId, unless adding the root
Only add/remove operations are used, so cycles are prevented by rejecting duplicate/self/unknown-manager additions

Examples

Input: ([],)

Expected Output: []

Explanation: No operations leaves the directory empty.

Input: ([[1, 1, -1], [1, 2, 1], [1, 3, 1], [2, 3]],)

Expected Output: [[1, -1], [2, 1]]

Explanation: Employee 3 is a leaf and is simply removed.

Input: ([[1, 1, -1], [1, 2, 1], [1, 3, 2], [1, 4, 2], [2, 2]],)

Expected Output: [[1, -1], [3, 1], [4, 1]]

Explanation: Manager 2 is removed, so direct reports 3 and 4 now report to 1.

Input: ([[1, 1, -1], [1, 2, 1], [1, 3, 1], [1, 4, 2], [2, 1]],)

Expected Output: [[2, -1], [3, 2], [4, 2]]

Explanation: Root 1 is removed. Employee 2 was the earliest-added direct report, so 2 becomes root and 3 reports to 2. Employee 4 already reported to 2.

Input: ([[1, 1, -1], [1, 1, 1], [1, 2, 99], [1, 3, 3], [1, 4, -1], [2, 99]],)

Expected Output: [[1, -1]]

Explanation: Duplicate employees, unknown managers, self-manager additions, second roots, and missing removals are ignored.

Hints

Maintain both a parent map and a children set for each employee.
Deletion only needs to rewire the removed employee's direct reports; root deletion is the special case.

Part 2: EmployeeDirectory with Seniority-Based Replacement

Constraints

0 <= len(operations) <= 100000
1 <= employeeId <= 10^9
0 <= seniority <= 10^9
At most one root may exist at a time
A valid add must use a unique employeeId and an existing managerId, unless adding the root
If a removed employee has no descendants, it is simply deleted