FastPrepAll Paths for a Rat in a Maze
Problems/All Paths for a Rat in a Maze

All Paths for a Rat in a Maze

Adobe logoAdobe● MediumINTERNPHONE SCREEN

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: You list every route a rat can take through a small grid maze, from the top-left corner to the bottom-right corner. An Adobe SDE intern report from an on-campus drive (May 2024, rejected) puts it first among the three tasks of its single interview round. That round followed a CGPA cut and an online test. It names the classic rat-in-a-maze task and asks for every path. It gives no move set, output order, limits or examples.

We chose these rules. There are four moves: down, left, right, up. No cell is used twice on one path. Paths are written as move letters in dictionary order. A 1 x 1 maze gives the empty string. Mazes are at most 4 x 4, so the list stays short. We wrote new examples.

Our version is about 85% the same as the reported question.

A rat starts at the top-left cell of an n x n maze and wants to reach the bottom-right cell. maze[i][j] is 1 if the cell is open and 0 if it is blocked.

In one move the rat goes one cell down (D), left (L), right (R) or up (U). It never leaves the maze, never enters a blocked cell, and never enters a cell that is already on its current path.

Return every path from the start to the goal as a string of moves, sorted in dictionary order. If the start or the goal is blocked, or no path exists, return an empty list. If n is 1 and the cell is open, the only path is the empty string.

Function

findPaths(maze: int[][]) → List<String>

Examples

Example 1

maze = [[1,1,0],[1,1,0],[0,1,1]]return = ["DRDR","RDDR"]
maze
012011011102011

From the top-left the rat can go down then right (DR) or right then down (RD) to reach the middle cell, and then D and R to the corner. Sorted: DRDR, RDDR.

Example 2

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

Both neighbors of the start are blocked, so there is no path and the answer is empty.

Example 3

maze = [[1,0,0],[1,1,0],[0,1,1]]return = ["DRDR"]
maze
012010011102011

Only one way through: down, right, down, right, so the answer is ["DRDR"].

Constraints

  • 1 <= n == maze.length == maze[i].length <= 4
  • Each maze[i][j] is 0 or 1

More Adobe Phone Screen questions

  • Evaluate a Parenthesized Integer ExpressionPHONE SCREEN · Seen Oct 2026
  • All Elements of Two BSTs in OrderPHONE SCREEN · Seen Aug 2026
  • Rotate an Array In PlaceOA · PHONE SCREEN · Seen Aug 2026
  • Binary Tree Level-Order Traversal by LevelsPHONE SCREEN · ONSITE INTERVIEW · Seen Aug 2026
  • Count Occurrences in a Sorted ArrayPHONE SCREEN · ONSITE INTERVIEW · Seen Jul 2026
  • Count Pairs with Absolute Difference KPHONE SCREEN · Seen Jul 2026
  • Count Subsets with Sum KPHONE SCREEN · Seen Jul 2026
  • Numbers with Exactly Three DivisorsPHONE SCREEN · Seen Jul 2026
  • Sum of Even Nodes on a Path in a Numbered Binary TreePHONE SCREEN · Seen Jul 2026
  • Largest Value in Every Sliding WindowPHONE SCREEN · Seen Jul 2026

Similar questions at other companies

  • Directional Tiles: Find a Valid Reconfiguration PathDuolingo · PHONE SCREENDuolingo interview questions
  • Enumerate Character Paths to a MarkerTesla · ONSITE INTERVIEWTesla interview questions
  • Trace a Word Through a Letter GridExpedia · ONSITE INTERVIEWExpedia interview questions
  • Word Search with Eight-Direction AdjacencyMicrosoft · ONSITE INTERVIEWMicrosoft interview questions
  • Word SearchBloomberg LP · OA · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
  • Binary Tree Target-Sum PathsByteDance · PHONE SCREENByteDance interview questions
  • Max Area of Island Without Changing the GridFlexport · PHONE SCREENFlexport interview questions
  • SubsetsTemu · PHONE SCREENTemu interview questions
  • Delete and Compact a Forest SubtreePinterest · PHONE SCREEN · ONSITE INTERVIEWPinterest interview questions
  • PermutationsEPAM · PHONE SCREENEPAM interview questions

Interview reports that mention this question

  • Adobe SWE Intern Interviews: 27 Experiences (Part 2 of 4)
  • Adobe Intern Interview Questions: 54 Experiences (Part 1 of 4)

Adobe interview experiences

  • Adobe Web, QA, DevOps, ML Roles: 13 Experiences (Part 3 of 3)
  • Adobe SWE Interviews, Level Unknown: 25 Experiences (Part 2 of 3)
  • Adobe Interviews, Level Unknown: 38 Experiences (Part 1 of 3)
  • Adobe New Grad MTS Interview Questions: 7 Experiences
All Adobe interview questionsSee Adobe hiring insights
Saved
class Solution {
    public List<String> findPaths(int[][] maze) {
        // Write your code here.
    }
}
Checking account…