Katkat
Back

Solve expression evaluator and string decoder

InstacartSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

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.

  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.