Parse password from indexed matrix file
Company: Instacart
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
##### Question
Given a filepath to a text file containing one index line [x, y] followed by a matrix of characters (origin at lower-left (0,
0)), return the character at coordinate (x,y). Extend to multiple (index, matrix) blocks in the same file: for each block read the character and prepend it to a password string using its index order, then return the password. If the file contains several passwords, stop after constructing the first complete password and return it.
Quick Answer: This question evaluates file parsing, matrix indexing with a specified coordinate origin, handling multiple indexed blocks, and string assembly into an ordered password, testing competencies in file I/O, coordinate transformations, and robust input handling.
You are given a string content that encodes one or more passwords. Each password consists of one or more blocks. A block has an index line followed by a character matrix: the index line is of the form [x,y] (0-based, optional spaces allowed), and it is followed by one or more lines of equal-length characters forming the matrix. A blank line terminates the matrix. Coordinates use origin at the lower-left corner of the matrix: x increases to the right, y increases upward. For each block in the first password group, read the character at (x,y) and prepend it to an accumulating password string in the order blocks appear. Password groups are separated by a line containing exactly '---'. Parse only the first password group (up to '---' or EOF) and return the resulting password string.
Constraints
- Input is well-formed per the format.
- Index lines match: [x,y] with 0-based non-negative integers and optional spaces.
- Each block's matrix has 1 to 1000 rows; all rows have the same length (1 to 1000).
- 0 <= x < number_of_columns, 0 <= y < number_of_rows for each block.
- Blocks within a password are separated by at least one empty line after each matrix.
- Passwords are separated by a line that is exactly '---'. Only the first password group must be processed.
- Total characters across the first password group <= 200,000.
Examples
Input: [1,2]\nabcd\nefgh\nijkl\n\n[0,0]\nXYZ\nPQR\n\n---\n[0,1]\nab\ncd\n
Expected Output: Pb
Input: [0,0]\nA\n\n[2,1]\n012\n345\n
Expected Output: 2A
Solution
import re\n\ndef parse_password(content: str) -> str:\n lines = content.splitlines()\n i = 0\n chars = [] # collect in encounter order; we'll reverse at the end to simulate prepend\n index_re = re.compile(r"^\[\s*(\d+)\s*,\s*(\d+)\s*\]\s*$")\n\n # Skip leading empty lines\n n = len(lines)\n while i < n and lines[i].strip() == '':\n i += 1\n\n # Process first password group only\n while i < n:\n s = lines[i].strip()\n if s == '---':\n break # end of first group\n if s == '':\n i += 1\n continue\n\n m = index_re.match(s)\n if not m:\n # Per constraints, inputs are valid; if encountered, skip line defensively\n i += 1\n continue\n\n x = int(m.group(1))\n y = int(m.group(2))\n i += 1\n\n # Gather matrix lines until blank line, group separator, or EOF\n matrix = []\n while i < n:\n t = lines[i]\n t_stripped = t.strip()\n if t_stripped == '---':\n break\n if t_stripped == '':\n i += 1 # consume the blank line delimiter\n break\n matrix.append(t.rstrip('\
').rstrip('\r'))\n i += 1\n\n if not matrix:\n # Empty matrix should not occur under valid input\n continue\n\n width = len(matrix[0])\n # Verify rectangularity (valid per constraints)\n for row in matrix:\n if len(row) != width:\n raise ValueError('Jagged matrix encountered')\n\n h = len(matrix)\n if not (0 <= x < width and 0 <= y < h):\n raise ValueError('Coordinate out of bounds')\n\n row_idx = h - 1 - y # convert from lower-left origin to top-down indexing\n ch = matrix[row_idx][x]\n chars.append(ch)\n\n # If next line is group separator, finish after this block\n if i < n and lines[i].strip() == '---':\n break\n\n # Prepending per block encounter order is equivalent to reversing the collected list\n return ''.join(reversed(chars))\nExplanation
Scan lines to process only the first password group (terminated by a line '---' or by EOF). Each block starts with an index line '[x,y]', followed by its matrix lines until a blank line or group separator. Convert (x,y) with origin at the lower-left to a zero-based top-down row index by row = height - 1 - y. Extract the character at column x in that row. To satisfy 'prepend per block' efficiently, append characters to a list as blocks are encountered and reverse the list at the end to form the password.
Time complexity: O(T) where T is the total size of the first group's input (lines plus matrix characters).. Space complexity: O(T) for storing matrices during parsing and O(B) for collected characters (B = number of blocks in first group)..
Hints
- Parse the index line with a regex like ^\[\s*(\d+)\s*,\s*(\d+)\s*\]$.
- Remember the origin is at the lower-left: matrix row index = (height - 1 - y).
- Collect characters per block in encounter order and prepend; an efficient way is to append and reverse at the end.