← Applied Intuition Interview InsightsSoftware Engineer

Applied Intuition·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
Apr 2026

Summary

Got a coding question at Applied Intuition for a software engineer role that was essentially a mini parser design problem. Not super algorithmically heavy but required clean thinking about how you structure and query data.

Questions Asked (1)

Q1

Given a message definition string where each line specifies a field name and its type, implement a parser that supports two operations: one that returns the size in bytes for a given field name, primitive type, or user-defined message type, and another that returns the type string for a given field name.

Algorithms & Data StructuresSystem DesignTechnical Trade-offs
Author's notes

I spent the first few minutes just trying to nail down the parsing logic before even thinking about the two query functions, which was probably the right call.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the message definition format and the expected behavior of the two operations, including error handling for unknown fields or types. Then design a two-pass parser: first parse all lines to build a symbol table mapping field names to types and user-defined types to their field lists, then compute sizes recursively with memoization. Finally, implement the two query functions using the symbol table and discuss trade-offs like eager vs lazy size computation.

Pro tip: Mention that you would validate the message definition for cycles and undefined types upfront, and use memoization to avoid exponential recomputation for nested types—this shows you think about robustness and efficiency beyond the basic implementation.

1. Clarify requirements and assumptions

Ask about the exact syntax of the message definition (e.g., 'fieldName: type'), whether types can be nested, and how to handle errors like unknown fields or cyclic definitions. Confirm the expected return values for size (in bytes) and type string.

2. Design the data structures

Propose a symbol table: a map from field name to its type, and a map from user-defined type name to its list of fields. Also define a mapping for primitive types to their byte sizes (e.g., int32 -> 4).

3. Implement parsing and validation

Parse each line into field name and type, populating the symbol tables. Validate that all referenced types are defined (either primitive or user-defined) and detect cycles in user-defined types to avoid infinite recursion.

4. Implement size computation with memoization

Write a recursive function that computes the size of a type: for primitives, return the fixed size; for user-defined types, sum the sizes of all fields. Use memoization to cache results for each user-defined type.

5. Implement query operations and discuss trade-offs

Implement getSize(fieldNameOrType) and getType(fieldName) using the symbol tables. Discuss trade-offs: eager vs lazy size computation, memory vs speed, and handling of unknown inputs (e.g., throw exception vs return null).

Key Points to Mention

  • Parsing the message definition into a symbol table for fields and user-defined types.
  • Mapping primitive types to their byte sizes (e.g., int32 = 4 bytes, bool = 1 byte).
  • Recursive size computation for nested user-defined types with memoization to avoid redundant work.
  • Cycle detection in user-defined types to prevent infinite recursion.
  • Error handling for unknown field names or types (e.g., throw an exception or return a sentinel value).
  • Trade-offs between eager (precompute all sizes) and lazy (compute on demand) size calculation.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.