Implement Employee Validation and Snake

This interview covered two coding tasks:

1. Employee validation

   • Implement a function that validates a collection of employees against a set of business rules.
   • Each employee can have direct reports, so validation must recursively process all descendants.
   • Follow-up: extend the validation so it detects cycles in the reporting structure, for example when employee A indirectly reports back to employee A.

2. Snake game

   • Implement a simplified Snake game on a 2D grid.
   • The game should handle keyboard input for up, down, left, and right movement.
   • It should detect wall collisions.
   • When the snake eats an apple, its length should increase by 1.

Part 1: Recursive Employee Collection Validation

You are given a collection of employees encoded as parallel arrays. Employee i has id ids[i], name names[i], salary salaries[i], and direct reports reports[i], where each report is another employee index. The collection may have multiple top-level employees listed in roots. Validate the entire employee collection by recursively walking from every root through all descendants. A valid collection must satisfy all business rules: every id is a positive unique integer, every name is non-empty after trimming whitespace, every salary is non-negative, every report/root index is in range, and every employee is reachable exactly once from the roots.

Constraints

• 0 <= n <= 1000, where n is the number of employees.
• ids, names, salaries, and reports must all have length n; otherwise the collection is invalid.
• A valid employee id must be a positive integer and must be unique.
• A valid employee name must be a non-empty string after trimming whitespace.
• A valid salary must be a non-negative integer.
• A valid collection forms a forest rooted at roots: every employee is reached exactly once by recursive traversal from the roots.

Examples

Example 1

Input: ([1, 2, 3, 4], ['CEO', 'Engineering Manager', 'Sales Manager', 'Developer'], [200000, 150000, 145000, 120000], [[1, 2], [3], [], []], [0])
Output: True

Explanation: All employees have valid fields and all four employees are reached exactly once from root 0.

Example 2

Input: ([1, 2, 3, 4], ['CEO', 'Engineering Manager', 'Sales Manager', '   '], [200000, 150000, 145000, 120000], [[1, 2], [3], [], []], [0])
Output: False

Explanation: Employee 3 is a descendant of employee 1 and has a blank name, so recursive validation must fail.

Hints

1. Use a depth-first traversal from each root and keep a visited set of employee indices.
2. Validate the employee fields before traversing, then validate index reachability during traversal.

Part 2: Employee Validation with Cycle Detection

You are given employees encoded as parallel arrays. Employee i has id ids[i], name names[i], salary salaries[i], and direct reports reports[i], where each report is another employee index. Extend employee validation to detect invalid reporting cycles, such as employee A eventually reporting back to employee A. A valid reporting structure must satisfy the basic employee rules, every report index must exist, no manager may list the same direct report twice, each employee may have at most one direct manager, and the directed reporting graph must be acyclic.

Constraints

• 0 <= n <= 100000, where n is the number of employees.
• 0 <= total number of report entries <= 200000.
• ids, names, salaries, and reports must all have length n; otherwise the collection is invalid.
• A valid employee id is positive and unique, a valid name is non-empty after trimming whitespace, and a valid salary is non-negative.
• Every report index must be between 0 and n - 1.
• Each employee can have at most one direct manager.
• The reporting graph must contain no directed cycles.

Examples

Example 1

Input: ([1, 2, 3, 4], ['CEO', 'Engineering', 'Sales', 'Developer'], [200000, 150000, 145000, 120000], [[1, 2], [3], [], []])
Output: True

Explanation: The structure is a valid acyclic reporting forest.

Example 2

Input: ([1, 2, 3], ['A', 'B', 'C'], [100, 90, 80], [[1], [2], [0]])
Output: False

Explanation: There is an indirect cycle: 0 reports to 1, 1 reports to 2, and 2 reports back to 0.

Hints

1. Cycle detection can be done with DFS colors, or with topological sorting using incoming-edge counts.
2. A cycle exists if you cannot process all employees after repeatedly removing employees with no manager.

Part 3: Simplified Snake Game Simulation

Implement a simplified Snake game on a rows by cols grid. The snake starts at cell row 0, column 0 with length 1. You are given a string of moves, where U, D, L, and R move the snake up, down, left, and right by one cell. You are also given apple positions. If the snake moves into a wall, the game stops immediately. If the snake moves onto an uneaten apple, the apple is consumed, the score increases by 1, and the snake grows by 1 by not removing its tail on that move. If the snake moves onto a normal cell, its head advances and its tail is removed, so its length stays the same. Self-collision is ignored in this simplified version.

Constraints

• 1 <= rows, cols <= 10000.
• 0 <= len(moves) <= 100000.
• moves contains only the characters U, D, L, and R.
• 0 <= len(apples) <= 100000.
• Apple positions are unique, inside the grid, and not at the starting cell [0, 0].
• Only wall collisions are considered; self-collision is ignored.

Examples

Example 1

Input: (3, 3, 'RDR', [[0, 1], [1, 2]])
Output: [1, 2, 3, 1, 2]

Explanation: The snake eats apples at [0, 1] and [1, 2], grows to length 3, and remains alive.

Example 2

Input: (2, 2, 'RR', [])
Output: [0, 0, 1, 0, 2]

Explanation: The second R attempts to move from [0, 1] to [0, 2], which is outside a 2-column grid.

Hints

1. Represent the snake body with a queue or deque: append the new head, and remove the tail unless an apple was eaten.
2. Store apple positions in a set so checking whether the new head is on an apple is O(1).