FastPrepRat in a Maze: All Simple Paths
Problems/Rat in a Maze: All Simple Paths

Rat in a Maze: All Simple Paths

PeopleStrong logoPeopleStrong● MediumFULLTIMEOA

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: Reported in a PeopleStrong online assessment. The report names Rat in a Maze with four directions and sorted output of all simple paths. We chose small limits on the size and on the number of paths, that the input is kept as it is, and the rule for a one-cell maze. Our version is about 95% the same as the reported question.

A rat starts at the top-left cell of a square binary matrix maze and wants to reach the bottom-right cell. A value of 1 means open and 0 means blocked. It may move down, left, right or up between adjacent open cells.

Return every path that never visits a cell twice. Encode moves using D, L, R and U, and sort the path strings in alphabetical order. Return an empty array if either endpoint is blocked or no path exists.

For this exercise, assume a one-cell open maze has one path, represented by the empty string. Do not change the input matrix.

Function

mazePaths(maze: int[][]) → String[]

Examples

Example 1

maze = [[1,0,0,0],[1,1,0,1],[1,1,0,0],[0,1,1,1]]return = ["DDRDRR","DRDDRR"]
maze
012301000111012110030111
→
return
0123450DDRDRR1DRDDRR

Exactly two simple paths reach the destination. They are listed in lexicographic order.

Example 2

maze = [[1,0],[0,1]]return = []
maze
01010101

The open endpoints are separated by blocked cells.

Constraints

  • For this exercise, assume the square side length is from 1 through 5.
  • Every cell is 0 or 1.
  • A path may revisit a cell used by another path, but may not repeat a cell within itself.
  • For this exercise, assume at most 500 valid simple paths reach the destination.

More PeopleStrong interview questions

  • Reverse Linked-List Nodes in Groups of KOA · PHONE SCREEN · Seen Mar 2026
  • Unique Paths Through a GridOA · Seen Mar 2026
  • Aggressive CowsOA · Seen Oct 2021
  • Shortest Path in an Unweighted GraphOA · Seen Oct 2021
  • Total Set Bits from 1 to NOA · Seen Oct 2021
  • Swap Two Array ElementsOA · Seen Sep 2021
  • Minimum Travel Time with Flashing Traffic LightsOA · Seen Aug 2021
  • Permutation in a StringOA · Seen Aug 2021
  • Add Two Binary StringsONSITE INTERVIEW · Seen Mar 2026
  • Four SumONSITE INTERVIEW · Seen Mar 2026

Similar questions at other companies

  • Word SearchBloomberg LP · OA · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
  • Find a Word Path Moving Right or DownIntuit · OAIntuit interview questions
  • Cave AdvantureMeta · OAMeta interview questions
  • Word SearchAmazon · ONSITE INTERVIEW
  • Word SearchMicrosoft · ONSITE INTERVIEWMicrosoft interview questions
  • Enumerate Character Paths to a MarkerTesla · ONSITE INTERVIEWTesla interview questions
  • Word SearchCognitiv · PHONE SCREEN
  • Find a Word in a Letter GridAdobe · PHONE SCREENAdobe interview questions
  • Word SearchWhatNot · PHONE SCREENWhatNot interview questions
  • Trace a Word Through a Letter GridExpedia · ONSITE INTERVIEWExpedia interview questions

Interview reports that mention this question

  • PeopleStrong SDE OA and Interview Questions: 12 Experiences
All PeopleStrong interview questionsSee PeopleStrong hiring insights
Saved
class Solution {
    public String[] mazePaths(int[][] maze) {
        // Write your solution here.
    }
}
Checking account…