Solve snake game, peak search, and task scheduling
Company: IXL Learning
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
1) Design a grid-based snake simulation that supports move(direction) operations on a W×H board. The snake grows when it consumes food at predetermined coordinates; return the score after each move or -1 if the snake hits a wall or itself. Specify the data structures to achieve O(
1) average time per move and explain how you detect collisions and advance the food pointer.
2) Given an integer array, find any index i such that nums[i] is strictly greater than its immediate neighbors (a local peak) in O(log n) time and O(
1) space. Describe the algorithm, prove correctness, and discuss adaptations when duplicates are allowed.
3) You are given tasks identified by characters and a non-negative cooldown n. Compute the minimum number of time slots to finish all tasks if each slot can execute one task or be idle, and outline how to construct one valid schedule. Extend your approach to handle distinct cooldowns per task.
Quick Answer: Solve snake game, peak search, and task scheduling evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.
Snake Game Simulation
Design a grid-based snake simulation on a W×H board. The snake starts at cell (row 0, col 0) with length 1. Process a sequence of `move(direction)` operations where each direction is one of 'U' (up, row-1), 'D' (down, row+1), 'L' (left, col-1), 'R' (right, col+1).
Food is given as a list of `[row, col]` coordinates that must be eaten in order. When the snake's head lands on the current (front-of-list) food coordinate, the snake grows by 1 (its tail does NOT move that step) and the score increases by 1; the food pointer then advances to the next coordinate. Otherwise the snake moves forward and its tail vacates the trailing cell.
After each move, return the current score, or -1 if that move drives the head out of bounds (hits a wall) or into a cell occupied by the snake's own body. Once the snake dies, every subsequent move also returns -1.
Implement `snakeGame(width, height, food, moves)` returning the list of per-move results.
Key insight: keep the body in a deque (O(1) head push / tail pop) and a hash set of occupied cells for O(1) average collision detection. Crucially, vacate the tail from the occupied set BEFORE testing the new head, so the snake may move into the cell its own tail is leaving.
Constraints
- 1 <= width, height <= 10^4
- 0 <= len(food)
- Each food coordinate is a valid in-bounds [row, col]
- Snake starts at (0, 0) with length 1
- Moves are characters in {'U','D','L','R'}
- Once dead, all subsequent moves return -1
Examples
Input: (3, 2, [[1, 2], [0, 1]], ['R', 'D', 'R', 'U', 'L', 'U'])
Expected Output: [0, 0, 1, 1, 2, -1]
Explanation: Move R,D (no food, score 0). R lands on food [1,2] -> grow, score 1. U,L: L lands on food [0,1] -> score 2. Final U exits the top wall -> -1.
Input: (3, 3, [], ['R', 'D', 'L', 'U'])
Expected Output: [0, 0, 0, 0]
Explanation: A length-1 snake can cycle freely because the tail always vacates; it never collides with itself, so the score stays 0.
Hints
- Store the body in a deque so the head pushes and the tail pops in O(1).
- Maintain a hash set of occupied cells for O(1) average self-collision checks.
- Vacate the tail from the occupied set BEFORE checking the new head — otherwise the snake wrongly collides with the cell its tail is leaving. When food is eaten the tail stays put (the snake grows).
- Check the wall (out-of-bounds) condition before any set mutation, and latch a 'dead' flag so later moves also return -1.
Find a Peak Element
Given an integer array `nums`, return the index `i` of any peak element — an element strictly greater than its immediate neighbors. Conceptually nums[-1] and nums[n] are treated as -∞, so an element only needs to beat the neighbors that exist (the first/last element only needs to beat its single neighbor). If the array is empty, return -1.
You must run in O(log n) time and O(1) extra space.
Implement `findPeakElement(nums)`.
Key insight: at any midpoint, if nums[mid] < nums[mid+1] then an ascending slope guarantees a peak somewhere to the right (because the array is bounded by -∞ on the far right), so move right; otherwise a peak exists at mid or to its left, so move left (keeping mid). The search window always contains a peak, and it shrinks each step.
Constraints
- 0 <= len(nums) <= 10^5
- -2^31 <= nums[i] <= 2^31 - 1
- Out-of-bounds neighbors are treated as -infinity
- Any valid peak index is accepted (the array may have several)
Examples
Input: ([1, 2, 3, 1],)
Expected Output: 2
Explanation: nums[2]=3 is greater than both neighbors 2 and 1.
Input: ([1, 2, 1, 3, 5, 6, 4],)
Expected Output: 5
Explanation: nums[5]=6 > nums[4]=5 and > nums[6]=4. (Index 1 is also a valid peak; this binary search returns 5.)
Hints
- Compare nums[mid] with nums[mid+1] to decide which half must contain a peak.
- If nums[mid] < nums[mid+1], the rising slope guarantees a peak to the right; otherwise keep mid and search left.
- Use a half-open window with `while lo < hi` and never read out of bounds (mid+1 is always valid because lo < hi).
- Correctness: the invariant is that the [lo, hi] window is always bordered by smaller (or out-of-bounds = -infinity) values, so a peak must lie inside it.
Task Scheduler with Cooldown
You are given a list of `tasks` (each a character) and a non-negative integer cooldown `n`. In each time slot you may either run one task or stay idle. The same task must be separated by at least `n` slots (i.e. there must be at least n other slots — different tasks or idles — between two runs of the same task). Return the minimum number of time slots required to finish all tasks.
Implement `leastInterval(tasks, n)`.
Key insight: the bottleneck is the most frequent task. If it occurs `maxCount` times, it forms `maxCount - 1` full frames each of width `n + 1`, then a final partial frame holding every task that ties for the maximum frequency. So the answer is `max(len(tasks), (maxCount - 1) * (n + 1) + numMax)`. The `len(tasks)` floor handles the case where there are enough distinct tasks to fill all idle gaps (no idling needed).
Constraints
- 0 <= len(tasks)
- 0 <= n
- Tasks are single characters
- With n = 0 there is no cooldown, so the answer is simply len(tasks)
Examples
Input: (['A', 'A', 'A', 'B', 'B', 'B'], 2)
Expected Output: 8
Explanation: A B idle A B idle A B = 8 slots. maxCount=3, numMax=2 -> (3-1)*3+2 = 8.
Input: (['A', 'A', 'A', 'B', 'B', 'B'], 0)
Expected Output: 6
Explanation: No cooldown -> just run all 6 tasks back to back.
Hints
- The most frequent task dictates the skeleton: it creates (maxCount - 1) frames of length (n + 1).
- Tasks that tie for the maximum frequency each add one extra slot in the trailing frame — add numMax (not 1).
- If there are many distinct tasks, the idle gaps fill up and you never idle: floor the answer at len(tasks).
- Final formula: max(len(tasks), (maxCount - 1) * (n + 1) + numMax).