PracHub
QuestionsPremiumCoachesLearningGuidesInterview Prep

Quick Overview

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.

  • Medium
  • IXL Learning
  • Coding & Algorithms
  • Software Engineer

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.

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

Expected Output: [-1]

Explanation: Moving L from (0,0) goes to column -1, hitting the left wall immediately.

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

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

Explanation: On a 1-row 5-col board, columns 0..4 are valid; the 5th R steps to column 5 and hits the right wall.

Input: (3, 3, [[0, 1], [0, 2]], ['R', 'R', 'D', 'L'])

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

Explanation: First R eats food [0,1] (score 1), second R eats [0,2] (score 2). The now length-3 snake continues D,L without colliding.

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

Expected Output: []

Explanation: No moves -> empty result list.

Hints

  1. Store the body in a deque so the head pushes and the tail pops in O(1).
  2. Maintain a hash set of occupied cells for O(1) average self-collision checks.
  3. 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).
  4. 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.)

Input: ([1],)

Expected Output: 0

Explanation: A single element is a peak by definition (both neighbors are -infinity).

Input: ([],)

Expected Output: -1

Explanation: Empty array has no peak.

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

Expected Output: 0

Explanation: Strictly descending: the first element is the only peak.

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

Expected Output: 4

Explanation: Strictly ascending: the last element is the only peak.

Input: ([2, 1],)

Expected Output: 0

Explanation: nums[0]=2 > nums[1]=1, so index 0 is a peak.

Hints

  1. Compare nums[mid] with nums[mid+1] to decide which half must contain a peak.
  2. If nums[mid] < nums[mid+1], the rising slope guarantees a peak to the right; otherwise keep mid and search left.
  3. Use a half-open window with `while lo < hi` and never read out of bounds (mid+1 is always valid because lo < hi).
  4. 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.

Input: (['A', 'A', 'A', 'A', 'A', 'A', 'B', 'C', 'D', 'E', 'F', 'G'], 2)

Expected Output: 16

Explanation: A dominates (maxCount=6, numMax=1): (6-1)*3+1 = 16. The 6 non-A tasks fit into the idle gaps but A's spacing still forces 16 slots.

Input: ([], 5)

Expected Output: 0

Explanation: No tasks -> 0 slots.

Input: (['A'], 3)

Expected Output: 1

Explanation: A single task takes 1 slot regardless of cooldown.

Input: (['A', 'B', 'C', 'D'], 2)

Expected Output: 4

Explanation: All distinct: no cooldown conflicts, answer is len(tasks)=4 (the floor dominates the formula's value of 4).

Input: (['A', 'A', 'B', 'B'], 100)

Expected Output: 103

Explanation: maxCount=2, numMax=2: (2-1)*101+2 = 103. Schedule A B then 99 idles then A B -> last slot index 102, length 103.

Hints

  1. The most frequent task dictates the skeleton: it creates (maxCount - 1) frames of length (n + 1).
  2. Tasks that tie for the maximum frequency each add one extra slot in the trailing frame — add numMax (not 1).
  3. If there are many distinct tasks, the idle gaps fill up and you never idle: floor the answer at len(tasks).
  4. Final formula: max(len(tasks), (maxCount - 1) * (n + 1) + numMax).
Last updated: Jun 26, 2026

Related Coding Questions

  • Find value on most distinct levels - IXL Learning (Medium)
  • Identify and prevent code-breaking inputs - IXL Learning (Medium)

Loading coding console...

PracHub

Master your tech interviews with 8,000+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.