Quick Overview

This question evaluates a candidate's ability in parsing, expression evaluation, and nested string decoding, including handling malformed input, character encoding nuances, and large-file streaming considerations.

Solve expression evaluator and string decoder

Company: Instacart

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

1) Implement an arithmetic expression evaluator that reads expressions from a text file (one expression per line) and outputs the evaluated result for each line. Support integers, +, -, *, /, parentheses, operator precedence, and whitespace. Describe how you will handle invalid tokens, divide-by-zero, overflow, and very long lines. Explain the data structures you would use (e.g., two stacks or shunting-yard), time/space complexity, and a streaming approach if the file is too large for memory. 2) Implement a string decoder for inputs encoded as k[encoded_string] with possible nesting (e.g., 3[a2[c]] -> accaccacc). Handle multi-digit repeat counts, UTF-8 characters, malformed brackets gracefully, and ensure O(n) time and space. Provide iterative and/or recursive approaches and analyze complexity.

Quick Answer: This question evaluates a candidate's ability in parsing, expression evaluation, and nested string decoding, including handling malformed input, character encoding nuances, and large-file streaming considerations.

Part 1: Arithmetic Expression Evaluator

Given a list of text lines, where each line contains one arithmetic expression, evaluate each expression independently. Expressions may contain signed/unsigned integers, '+', '-', '*', '/', parentheses, and arbitrary whitespace. Operators follow normal precedence rules: parentheses first, then multiplication/division, then addition/subtraction. Division is integer division truncated toward zero, matching C/Java-style integer division. Return the decimal result for each valid expression as a string. If a line contains an invalid token, malformed expression, mismatched parentheses, division by zero, or a result outside signed 64-bit integer range, return 'ERROR' for that line.

Constraints

  • 0 <= len(expressions) <= 10^4
  • 0 <= len(expressions[i]) <= 10^5
  • The total number of characters across all expressions is at most 2 * 10^5
  • Valid integer results and intermediate values must fit in signed 64-bit range: [-2^63, 2^63 - 1]
  • Allowed non-whitespace characters are digits, '+', '-', '*', '/', '(', and ')'

Examples

Input: (['1 + 2 * 3', '(8 + 4) / 3'],)

Expected Output: ['7', '4']

Explanation: Multiplication is evaluated before addition. Parentheses override precedence. Division truncates toward zero.

Input: (['14 - 3 * 2 + 8 / 3', '18 / (3 * (2 + 1))'],)

Expected Output: ['10', '2']

Explanation: The first expression is 14 - 6 + 2 = 10. The second is 18 / 9 = 2.

Hints

  1. Use either recursive descent parsing with grammar levels for expression, term, and factor, or use two stacks/shunting-yard to enforce precedence.
  2. Validate as you parse: after every arithmetic operation, check for divide-by-zero and signed 64-bit overflow.

Part 2: Nested k[encoded_string] String Decoder

Decode a string encoded with the pattern k[encoded_string], where k is a non-negative integer repeat count and encoded_string may itself contain nested encoded patterns. For example, '3[a2[c]]' decodes to 'accaccacc'. Multi-digit repeat counts are supported. Unicode/UTF-8 characters are treated as normal literal characters unless they are ASCII digits or brackets. If the input has malformed brackets, a repeat count not followed by '[', an unexpected '[', an unexpected ']', or the decoded output would exceed the allowed maximum length, return 'ERROR'.

Constraints

  • 0 <= len(s) <= 10^5
  • Repeat counts contain ASCII digits '0' through '9'
  • A repeat count must be immediately followed by '['
  • Literal characters may be any non-digit, non-bracket Unicode characters
  • The decoded output length is limited to 10^5 characters

Examples

Input: ('3[a2[c]]',)

Expected Output: 'accaccacc'

Explanation: The inner pattern 2[c] becomes cc, so a2[c] becomes acc, repeated 3 times.

Input: ('10[a]',)

Expected Output: 'aaaaaaaaaa'

Explanation: Multi-digit repeat counts are supported.

Hints

  1. Use a stack. When you see k[, push the current decoded prefix and k, then start a new current segment.
  2. When you see ], pop the previous prefix and count, repeat the current segment, and append it to the previous prefix.

Loading coding console...