Quick Overview

Build a fixed-grid string spreadsheet with concatenation formulas, dependency updates, repeated references, and read-time circular-reference errors.

Spreadsheet String Concatenation with Dependent Cells

Company: Ramp

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Implement a 26-column, 100-row spreadsheet that stores strings and supports formulas that concatenate other cells. When a referenced cell changes, future reads of dependent formulas must reflect the new string. Use columns `A` through `Z` and rows `1` through `100`. Implement `concatenate_sheet(operations: string[][]) -> string[]`: - `["set", cell, raw]` stores a literal string or formula and returns the string `"OK"`. - A raw value starting with `=` is a formula, such as `=C1C2`, which concatenates the computed values of `C1` and `C2` in that order. - `["get", cell]` returns `"VALUE:"` followed by the computed string, or exactly `"CYCLE"` if the read reaches a circular reference. - Return one string per operation. The `VALUE:` prefix is part of the output contract and distinguishes arbitrary literal content from error/status tokens. ### Constraints & Assumptions - The fixed grid size and concatenation form are the reported variant; the following parsing and error rules make the practice task deterministic. - A formula is `=` followed by one or more valid cell names with no separators or spaces. Each name has exactly one uppercase column letter followed by a decimal row number without leading zero. - Repeated references repeat the corresponding string. Formula order matters. - A literal does not start with `=`. Unset cells evaluate to the empty string, so getting one returns `"VALUE:"`. - Set replaces the old literal or formula completely. Cycles are stored and diagnosed on reads that reach them; an unrelated cycle does not affect another cell. - There are at most 500 operations, at most 20 references per formula, and at most 100 characters per literal. Every successfully evaluated cell has a computed length of at most 10,000 characters. - All inputs follow the grammar and grid bounds. Persistent stale caches must not survive an input update. ### Examples ```text operations = [ ["set","C1","hello"], ["set","C2"," world"], ["set","A1","=C1C2"], ["get","A1"], ["set","C1","goodbye"], ["get","A1"] ] result = ["OK","OK","OK","VALUE:hello world","OK","VALUE:goodbye world"] ``` ```text operations = [["set","A1","=B1B1"],["set","B1","=A1"],["get","A1"]] result = ["OK","OK","CYCLE"] ``` ```hint Parse references before evaluating them The next uppercase letter starts the next cell reference. Preserve the resulting reference sequence even if a separate dependency set is used for cycle detection. ```

Overview: Build a fixed-grid string spreadsheet with concatenation formulas, dependency updates, repeated references, and read-time circular-reference errors.

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

Implement a 26-column, 100-row spreadsheet that stores strings and supports formulas that concatenate other cells. When a referenced cell changes, future reads of dependent formulas must reflect the new string. Use columns `A` through `Z` and rows `1` through `100`. Implement `concatenate_sheet(operations: string[][]) -> string[]`: - `["set", cell, raw]` stores a literal string or formula and returns the string `"OK"`. - A raw value starting with `=` is a formula, such as `=C1C2`, which concatenates the computed values of `C1` and `C2` in that order. - `["get", cell]` returns `"VALUE:"` followed by the computed string, or exactly `"CYCLE"` if the read reaches a circular reference. - Return one string per operation. The `VALUE:` prefix is part of the output contract and distinguishes arbitrary literal content from error/status tokens. ### Constraints & Assumptions - The fixed grid size and concatenation form are the reported variant; the following parsing and error rules make the practice task deterministic. - A formula is `=` followed by one or more valid cell names with no separators or spaces. Each name has exactly one uppercase column letter followed by a decimal row number without leading zero. - Repeated references repeat the corresponding string. Formula order matters. - A literal does not start with `=`. Unset cells evaluate to the empty string, so getting one returns `"VALUE:"`. - Set replaces the old literal or formula completely. Cycles are stored and diagnosed on reads that reach them; an unrelated cycle does not affect another cell. - There are at most 500 operations, at most 20 references per formula, and at most 100 characters per literal. Every successfully evaluated cell has a computed length of at most 10,000 characters. - All inputs follow the grammar and grid bounds. Persistent stale caches must not survive an input update. ### Examples ```text operations = [ ["set","C1","hello"], ["set","C2"," world"], ["set","A1","=C1C2"], ["get","A1"], ["set","C1","goodbye"], ["get","A1"] ] result = ["OK","OK","OK","VALUE:hello world","OK","VALUE:goodbye world"] ``` ```text operations = [["set","A1","=B1B1"],["set","B1","=A1"],["get","A1"]] result = ["OK","OK","CYCLE"] ```

Constraints

  • The sheet has columns A through Z and rows 1 through 100.
  • At most 500 valid set/get operations; return one string per operation.
  • A formula is = followed by 1 through 20 valid cell names without separators or spaces. Each cell name has one uppercase letter and a decimal row without leading zeros.
  • Literals do not start with = and contain at most 100 characters. Unset cells evaluate to the empty string.
  • References retain their order and multiplicity. Every successfully evaluated cell has length at most 10000.
  • Set replaces the old value completely; only cycles reachable from a get cause CYCLE, and future reads reflect updates.

Examples

Input: ([['set', 'C1', 'hello'], ['set', 'C2', ' world'], ['set', 'A1', '=C1C2'], ['get', 'A1'], ['set', 'C1', 'goodbye'], ['get', 'A1']],)

Expected Output: ['OK', 'OK', 'OK', 'VALUE:hello world', 'OK', 'VALUE:goodbye world']

Explanation: Source update example.

Input: ([['set', 'A1', '=B1B1'], ['set', 'B1', '=A1'], ['get', 'A1']],)

Expected Output: ['OK', 'OK', 'CYCLE']

Explanation: Source two-cell cycle example.

Hints

  1. A get must preserve literal content even when it resembles a status token.
  2. An unrelated circular reference must not affect the requested cell.

Loading coding console...

Show the approach

Approach

Store the latest raw string for each set. For each get, start a fresh memo table and active-recursion set. A cell already active lies on the current dependency path, so reaching it proves a cycle. A completed memoized cell is safe to reuse, including in a shared dependency graph. An unset cell contributes the empty string. For a formula, parse its references from left to right, evaluate every occurrence, and concatenate in that same order. Mark a cell complete only after all of its references complete. Induction on the dependency DAG proves each completed value equals its definition. A reachable cycle aborts the read; all traversal state is discarded, so repairing formulas or changing literals is visible on the next get.

Time complexity:
O(S + sum_g(P_g + L_g)) expected, where S is total stored-input processing, P_g is reachable raw-text size, and L_g is total constructed string length for read g
Space complexity:
O(S_live + max_g(V_g + L_g)) auxiliary, excluding returned strings; memoization and traversal state are per read