Implement matrix-indexing and expression resolver

Q: Implement matrix-indexing and expression resolver

This question evaluates a candidate's ability to parse structured text files, perform matrix indexing with a nonstandard origin convention, reconstruct data across multiple blocks, and resolve symbolic variable expressions and dependencies for arithmetic evaluation in the Coding & Algorithms domain.

Q: 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.

Q: What difficulty level is this coding question?

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

Q: What role is this question designed for?

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

Question

##### Question

Given a text file path whose contents include a single block starting with a line like "[2,4]" followed by rows of equal-length characters (e.g., "S3KDA4" … "RTRYYU"), write code to return the character(s) at each coordinate pair, where [0,0] is the bottom-left character of the block. Follow-up 1 (multiple blocks): each block starts with an integer giving the character’s index in a password, then the "[row,col]" header and the character matrix. Return the reconstructed password across all blocks (e.g., blocks for indices 1 and 0 should output "XK"). Follow-up 2 (multiple passwords): continue reading blocks until an index value repeats; the repeat marks the start of a new password. Return the first complete password only. Expression evaluation: Given a target variable computeExp (e.g., T
3) and a list of assignments such as T1=1, T2=2, T3=T4, T4=T5, T5=T2, compute the numeric value of computeExp by resolving dependencies. Follow-up 1: An assignment may contain exactly one + or – (e.g., T3=T4+T
5). Handle integer arithmetic with one operator. Follow-up 2: If the dependency graph contains a cycle (e.g., T4 depends on T5 and T5 depends on T
4), return "IMPOSSIBLE".

PracHub · Accepted Answer

import sys
import re

def evaluate_expression(target: str, assignments: list[str]) -> int | str:
    # Build mapping from variable to raw RHS expression
    mapping: dict[str, str] = {}
    var_re = re.compile(r"^T\d+$")
    for line in assignments:
        if '=' not in line:
            return "IMPOSSIBLE"
        left, right = line.split('=', 1)
        v = left.strip()
        if not var_re.fullmatch(v):
            return "IMPOSSIBLE"
        mapping[v] = right.strip()

if target not in mapping:
        return "IMPOSSIBLE"

sys.setrecursionlimit(1_000_000)

memo: dict[str, int] = {}
    state: dict[str, int] = {}  # 0=unvisited, 1=visiting, 2=visited

def eval_term(tok: str) -> int:
        # tok has no spaces
        if var_re.fullmatch(tok):
            return eval_var(tok)
        # Allow integers with optional leading '+' or '-'
        return int(tok)

def parse_and_eval(expr: str) -> int:
        s = expr.replace(' ', '')
        if not s:
            raise ValueError("empty expression")
        # Find the first '+' or '-' that is not the very first char (to allow leading sign)
        op_pos = -1
        op_char = ''
        for i in range(1, len(s)):
            if s[i] in '+-':
                op_pos = i
                op_char = s[i]
                break
        if op_pos == -1:
            # Single term
            return eval_term(s)
        left = s[:op_pos]
        right = s[op_pos+1:]
        if left == '' or right == '':
            raise ValueError("malformed binary expression")
        left_val = eval_term(left)
        right_val = eval_term(right)
        return left_val + right_val if op_char == '+' else left_val - right_val

def eval_var(v: str) -> int:
        if v in memo:
            return memo[v]
        st = state.get(v, 0)
        if st == 1:
            # cycle detected
            raise RuntimeError("CYCLE")
        if st == 2:
            return memo[v]
        if v not in mapping:
            raise KeyError("undefined variable")
        state[v] = 1
        val = parse_and_eval(mapping[v])
        state[v] = 2
        memo[v] = val
        return val

try:
        return eval_var(target)
    except (RuntimeError, ValueError, KeyError):
        return "IMPOSSIBLE"

Build a dependency graph implicitly by mapping each variable to its right-hand expression and evaluate with DFS. While visiting a variable, mark it as 'visiting'. If it is encountered again in the current path, a cycle exists and the result is 'IMPOSSIBLE'. Use memoization to cache evaluated variables. Parse each expression by removing spaces, then either evaluate a single term (variable or integer) or split on the first '+' or '-' (ignoring a leading sign) and evaluate both terms recursively.

Quick Overview

Solution

Explanation

Hints

Quick Overview