FastPrepShortest Path Around Moving Parades
Problems/Shortest Path Around Moving Parades

Shortest Path Around Moving Parades

Zip logoZip● HardFULLTIMENEW GRADPHONE SCREEN
QuestionFunctionExamplesConstraints

Problem statement

Source note: Two reports preserve the infinite-grid path task, a complete static example, semi-infinite moving parade geometry, and two taxi steps per parade advance. The finite search rectangle and tie rule are practice assumptions; the judged core task matches the source at about 90%.

A taxi moves on integer grid intersections. It begins at start = [x, y] at time 0 and must reach destination. Each second it moves exactly one cell east, north, south, or west. It may not wait.

Static barriers are blocked at every time. Each string in parades has the form "x,y,D", where D is E, N, S, or W. At time t, a parade head has advanced floor(t / 2) cells from [x, y] in direction D. The parade occupies its head and the entire semi-infinite line behind it:

  • An eastbound parade blocks its row at every x-coordinate at or west of its head.
  • A westbound parade blocks its row at every x-coordinate at or east of its head.
  • A northbound parade blocks its column at every y-coordinate at or south of its head.
  • A southbound parade blocks its column at every y-coordinate at or north of its head.

The taxi may not enter a cell blocked at its arrival time. Search only inside the inclusive rectangle bounds = [minX, maxX, minY, maxY].

Return a shortest valid direction string using E, N, S, and W. If several shortest strings exist, return the lexicographically smallest one. Return an empty string when no route exists.

Function

shortestParadePath(start: int[], destination: int[], barriers: int[][], parades: String[], bounds: int[]) → String

Examples

Example 1

start = [3,0]destination = [8,3]barriers = [[7,0],[7,1],[7,2],[7,3],[7,4],[8,2]]parades = []bounds = [-2,12,-2,8]return = "EEENNNNNEESS"

The route takes 12 steps, matching the minimum length reported for this barrier layout. It is the lexicographically smallest shortest route inside the rectangle.

Example 2

start = [3,0]destination = [3,4]barriers = []parades = ["2,3,E"]bounds = [-2,8,-2,8]return = "EENNNNWW"

The direct north route meets the growing eastbound parade on row 3. Moving east first crosses beyond its head before returning west above the parade.

Example 3

start = [0,0]destination = [0,2]barriers = [[0,1]]parades = []bounds = [0,0,0,2]return = ""

The only intermediate cell inside the rectangle is a barrier.

Constraints

  • start.length == destination.length == 2 and bounds.length == 4.
  • minX <= x <= maxX and minY <= y <= maxY for the start, destination, every barrier, and every parade head.
  • 1 <= maxX - minX + 1 <= 40 and 1 <= maxY - minY + 1 <= 40.
  • 0 <= barriers.length <= 1000 and 0 <= parades.length <= 20.
  • Static barriers are distinct, and every parade string is valid.

More Zip problems

  • Maximum Survival Time in a Graph PursuitPHONE SCREEN · Seen Sep 2026
  • Find All Zip Rummy MeldsPHONE SCREEN · ONSITE INTERVIEW · Seen Apr 2026
  • Furthest Building with Sandbags and RopesPHONE SCREEN · Seen Feb 2026
All Zip interview questionsSee Zip hiring insights
Saved
class Solution {
    public String shortestParadePath(int[] start, int[] destination, int[][] barriers, String[] parades, int[] bounds) {
        // Write your code here.
    }
}
Checking account…