Quick Overview

Resolve a target variable through an acyclic chain of named assignments until reaching an integer literal, independent of definition order.

Resolve a Variable Through Literal and Reference Assignments

Company: Instacart

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Resolve a variable whose assignment is either an integer literal or the name of another variable. ### Function Signature `resolve_variable(assignments: list[list[str]], target: str) -> int` ### Input Each assignment is `[variable_name, right_hand_side]`. A right-hand side is either a decimal integer literal or another variable name. The order of assignments is arbitrary. For this exercise, names match `[A-Za-z_][A-Za-z0-9_]*`. Integer literals use an optional minus sign followed by one or more digits, with no whitespace or plus sign. Literal values are in `[-1000000000, 1000000000]`. ### Output Follow references beginning at `target` and return the terminal integer value. ### Constraints - `1 <= len(assignments) <= 100000`. - Variable names are unique, and `target` is defined. - Every referenced variable is defined. - The complete reference graph is acyclic, so every chain ends in an integer literal. - Each string has at most 40 characters. - These validity rules are explicit baseline assumptions; malformed definitions and cycles are outside this console contract. ### Examples Input: `assignments = [["T1","T2"],["T2","-8"],["unused","4"]], target = "T1"` Output: `-8` Input: `assignments = [["A","007"],["B","A"]], target = "B"` Output: `7` Input: `assignments = [["value","0"]], target = "value"` Output: `0`

Overview: Resolve a target variable through an acyclic chain of named assignments until reaching an integer literal, independent of definition order.

Read the full Instacart Software Engineer interview experience this question came from

You are given a list of variable assignments. Each assignment is a two-element list [variable_name, right_hand_side]. A right-hand side is either a decimal integer literal or the name of another variable. The order of assignments is arbitrary, so a variable may be referenced by an assignment that appears earlier in the list than its own definition. Starting at the variable named target, follow the references: while the current variable's right-hand side is another variable name, continue from that variable. Stop when the right-hand side is an integer literal and return that integer value. Variable names match [A-Za-z_][A-Za-z0-9_]*. An integer literal is an optional minus sign followed by one or more digits, with no whitespace and no plus sign; leading zeros are allowed, so "007" is the value 7 and "-0" is the value 0. Because a name can never begin with a digit or a minus sign, a right-hand side is an integer literal exactly when its first character is a digit or '-'; otherwise it is a variable name. Variable names are unique, target is defined, every referenced variable is defined, and the complete reference graph is acyclic, so following references from target always terminates at an integer literal. Malformed definitions and cycles are outside this contract. The answer is a single integer and is unique, so there is no ordering or tie-breaking question. The return type is a 64-bit signed integer (long in Java, long long in C++); since literal values are in [-1000000000, 1000000000], no returned value exceeds 2^31 - 1. Example 1: Input: assignments = [["T1", "T2"], ["T2", "-8"], ["unused", "4"]], target = "T1" Output: -8 Explanation: T1 references T2, and T2's right-hand side is the literal -8. The assignment for 'unused' is never visited. Example 2: Input: assignments = [["A", "007"], ["B", "A"]], target = "B" Output: 7 Explanation: B references A, and A's right-hand side is the literal 007, whose value is 7.

Constraints

  • 1 <= len(assignments) <= 100000.
  • Each assignment is [variable_name, right_hand_side].
  • The order of assignments is arbitrary.
  • Names match [A-Za-z_][A-Za-z0-9_]*.
  • Integer literals use an optional minus sign followed by one or more digits, with no whitespace and no plus sign; leading zeros are allowed.
  • Literal values are in [-1000000000, 1000000000].
  • Variable names are unique, and target is defined.
  • Every referenced variable is defined.
  • The complete reference graph is acyclic, so every chain ends in an integer literal.
  • Each string has at most 40 characters.
  • These validity rules are explicit baseline assumptions; malformed definitions and cycles are outside this console contract.

Examples

Input: ([["value", "0"]], "value")

Expected Output: 0

Explanation: Minimum valid input: one assignment whose right-hand side is already the literal 0.

Input: ([["T1", "T2"], ["T2", "-8"], ["unused", "4"]], "T1")

Expected Output: -8

Explanation: T1 references T2 and T2 is the literal -8; the unrelated assignment 'unused' is never visited.

Hints

  1. The assignments arrive in arbitrary order, so the definition you need next may sit anywhere in the list; think about what you want in place before you start following anything.
  2. You can tell a right-hand side apart from a variable name by its first character alone: a name may never begin with a digit or a minus sign.
  3. A chain can be as long as the number of assignments, and leading zeros or a minus sign are part of a perfectly ordinary literal.

Loading coding console...

Show the approach

Approach

Algorithm: build a hash map from variable name to its raw right-hand side string in one pass over the assignments. Because the input order is arbitrary, the whole map must exist before any reference is followed; indexing the list directly would fail whenever a definition appears after its use. Then walk iteratively from target: read the current variable's right-hand side, decide whether it is a literal or a name, and either return the parsed literal or move to the named variable.

Classification invariant: a name must start with a letter or an underscore, and a literal must start with a digit or a minus sign. Those two character classes are disjoint, so the first character alone decides the case with no backtracking and no exception handling. This is why '_1' is a variable and '1' is a literal, and why '-8' must not be classified by a digits-only test.

Loop invariant: 'current' is always a defined variable name, so values[current] exists. It holds initially because target is defined, and it is preserved because a right-hand side that is not a literal is a variable name and every referenced variable is defined. Termination: the reference graph is acyclic and finite, so each hop moves strictly forward along a finite chain and the walk must reach a literal; there is no need to track visited nodes.

Parsing: int/Long.parseLong/std::stoll/parseInt(radix 10) all accept an optional minus sign with leading zeros, so '007' yields 7 and '-007' yields -7. The '-0' case parses to 0; JavaScript's parseInt returns -0 there, which is normalized to 0 so that the emitted value is exactly 0.

Edge cases: the target itself may already hold a literal (zero hops); unrelated variables and unrelated chains are never visited; several variables may share one tail, which costs nothing because each resolution walks only its own chain; names differing only by case or underscores are distinct keys; the chain may be as long as the number of assignments, so the walk is iterative rather than recursive to avoid stack overflow at 100000 links. Values stay within [-1000000000, 1000000000], well inside 64-bit range.

Time complexity:
O(n + L) where n is the number of assignments and L is the length of the resolved chain, which is O(n) overall (each right-hand side has at most 40 characters).
Space complexity:
O(n) for the name-to-right-hand-side map.