Parse a password from a matrix
Company: Instacart
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Given an m x n matrix of characters, a starting coordinate (row, col), and a string of moves consisting of 'U', 'D', 'L', 'R', parse a password by visiting cells in order: append the character at each visited cell unless it is the same as the previous appended character. Cells marked '#' are blocked and cannot be entered. If a move would leave the grid or hit a blocked cell, return an error. Return the final password string and analyze time/space complexity.
Quick Answer: This question evaluates proficiency in grid traversal, sequence-driven state tracking, string manipulation, and boundary/obstacle validation while requiring time and space complexity reasoning.
You are given an m x n matrix of single characters `matrix`, a starting coordinate `(start_row, start_col)`, and a string of `moves` consisting of the characters 'U' (up), 'D' (down), 'L' (left), and 'R' (right).
Starting from the starting cell, you build a password by visiting cells in order. At each visited cell (including the starting cell) you append that cell's character to the password, UNLESS it is the same as the character you most recently appended — in that case you skip it (consecutive duplicates collapse into one character).
Cells marked '#' are blocked and cannot be entered. If a move would step outside the grid, or would step onto a blocked '#' cell, the input is invalid: return the string "ERROR". (If the starting cell itself is out of bounds or blocked, also return "ERROR".)
Return the final password string, or "ERROR" if any move is invalid.
The method name is `solution`. Signature: `solution(matrix, start_row, start_col, moves)` where `matrix` is a list of lists of one-character strings, `start_row`/`start_col` are integers, and `moves` is a string. It returns a string.
Constraints
- 1 <= m, n (the matrix is non-empty and rectangular)
- Each cell of matrix is a single character; '#' denotes a blocked cell.
- moves consists only of the characters 'U', 'D', 'L', 'R' (any other character is treated as invalid and yields "ERROR").
- 0 <= len(moves) <= 10^5
- Return "ERROR" if a move leaves the grid or enters a blocked cell, or if the starting cell is out of bounds or blocked.
Examples
Input: ([['a','b','c'],['d','e','f'],['g','h','i']], 0, 0, 'RRDD')
Expected Output: 'abcfi'
Explanation: Path: (0,0)a -> (0,1)b -> (0,2)c -> (1,2)f -> (2,2)i. All characters differ from the previous, so the password is 'abcfi'.
Input: ([['a','a','b'],['c','d','e']], 0, 0, 'RR')
Expected Output: 'ab'
Explanation: Path: (0,0)a -> (0,1)a -> (0,2)b. The second 'a' matches the previously appended 'a', so it is skipped, giving 'ab'.
Hints
- Track two things as you walk: your current (row, col) position and the last character you appended. A new character is only appended when it differs from that last-appended character.
- Map each move letter to a (dr, dc) delta. Before committing to a move, compute the candidate cell and validate it: it must be inside the grid AND not a '#'. Fail fast with "ERROR" the moment a move is invalid.
- Don't forget the starting cell itself — it must be valid (in-bounds and not blocked), and its character seeds the password before you process any moves.