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 Amplitude.

What role is this question designed for?

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

Implement Employee Validation and Snake | Amplitude Coding Question

Implement Employee Validation and Snake

Company: Amplitude

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

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.

Quick Answer: This question evaluates recursion, graph traversal and cycle-detection concepts for hierarchical employee validation alongside state management, event-driven input handling and collision detection for a grid-based Snake game.

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

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

Expected Output: True

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

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

Expected Output: False

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

Input: ([1, 2, 2], ['A', 'B', 'C'], [10, 9, 8], [[1, 2], [], []], [0])

Expected Output: False

Explanation: Employee ids must be unique, but id 2 appears twice.

Input: ([1, 2], ['A', 'B'], [10, 9], [[], []], [0])

Expected Output: False

Explanation: Employee 1 is never reached from the listed roots, so the full collection was not recursively validated.

Input: ([], [], [], [], [])

Expected Output: True

Explanation: The empty employee collection is valid.

Hints

Use a depth-first traversal from each root and keep a visited set of employee indices.
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

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

Expected Output: True

Explanation: The structure is a valid acyclic reporting forest.

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

Expected Output: False

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

Input: ([1], ['Solo'], [100], [[0]])

Expected Output: False

Explanation: A single employee cannot be their own direct report.

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

Expected Output: False

Explanation: Employee 2 is listed as a direct report by two different managers.

Input: ([], [], [], [])

Expected Output: True

Explanation: The empty reporting graph has no invalid employees and no cycles.

Hints

Cycle detection can be done with DFS colors, or with topological sorting using incoming-edge counts.
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

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

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

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

Input: (2, 2, 'RR', [])

Expected 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.

Input: (1, 1, '', [])

Expected Output: [1, 0, 1, 0, 0]

Explanation: With no moves, the snake remains alive at the starting cell.

Input: (2, 2, 'RLR', [[0, 1]])

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

Explanation: The apple at [0, 1] is consumed only the first time the snake enters that cell.

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

Expected Output: [1, 2, 3, 2, 0]

Explanation: The snake eats an apple on each downward move and grows from length 1 to length 3.

Hints

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

Quick Overview

This question evaluates recursion, graph traversal and cycle-detection concepts for hierarchical employee validation alongside state management, event-driven input handling and collision detection for a grid-based Snake game.