How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Instacart.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Instacart during technical interviews.

Parse a password from a matrix | Instacart Coding Question

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'.

Input: ([['a','b'],['#','d']], 0, 0, 'D')

Expected Output: 'ERROR'

Explanation: Moving Down from (0,0) lands on (1,0) which is blocked ('#'), so the result is 'ERROR'.

Input: ([['a','b'],['c','d']], 0, 0, 'U')

Expected Output: 'ERROR'

Explanation: Moving Up from row 0 leaves the grid, so the result is 'ERROR'.

Input: ([['x']], 0, 0, '')

Expected Output: 'x'

Explanation: A single-cell grid with no moves: only the starting character 'x' is appended.

Input: ([['a','b','c']], 0, 0, 'RRLL')

Expected Output: 'abcba'

Explanation: Path: a -> b -> c -> b -> a. No two consecutive visited characters are equal, so every character is appended: 'abcba'.

Input: ([['#','b'],['c','d']], 0, 0, 'R')

Expected Output: 'ERROR'

Explanation: The starting cell (0,0) is blocked ('#'), so the result is 'ERROR' before any move is processed.

Input: ([['a','a','a'],['a','a','a']], 0, 0, 'RRDLL')

Expected Output: 'a'

Explanation: Every visited cell holds 'a', so after the first append all subsequent identical characters are skipped, collapsing to 'a'.

Input: ([['a','b'],['c','d']], 0, 0, 'DRUL')

Expected Output: 'acdba'

Explanation: Path loops around: (0,0)a -> (1,0)c -> (1,1)d -> (0,1)b -> (0,0)a. All consecutive characters differ, giving 'acdba'.

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.

Quick Overview

This question evaluates proficiency in grid traversal, sequence-driven state tracking, string manipulation, and boundary/obstacle validation while requiring time and space complexity reasoning.