Protobuf-Style Schema: Look Up Message Sizes and Field Types, Then Parse the Schema
Company: Applied
Role: Software Engineer
Category: Software Engineering Fundamentals
Difficulty: medium
Interview Round: Technical Screen
Implement a small schema service for a simplified Protocol Buffers (protobuf) style schema language. A schema defines named messages. Each message has a list of fields, and each field has a type, a name and a field number. A field's type is either a scalar type or the name of another message in the same schema, in which case that message is embedded as the field.
Implement two queries:
- `get_size(message_name)` returns the size of the named message.
- `get_type(message_name, field_name)` returns the type of the named field exactly as written in the schema: a scalar type name or a message name.
For this practice version, use these size rules:
| Scalar type | Size in bytes |
| --- | --- |
| `bool` | 1 |
| `int32` | 4 |
| `float` | 4 |
| `int64` | 8 |
| `double` | 8 |
- A message's size is the sum of the sizes of its fields.
- A field whose type is a message contributes that message's full size.
- Field numbers, field names and formatting do not affect size, and there is no per-field overhead.
Example schema:
```text
message Point {
int32 x = 1;
int32 y = 2;
}
message Segment {
Point start = 1;
Point end = 2;
double weight = 3;
}
```
With this schema, `get_size("Point")` is 8, `get_size("Segment")` is 24 (8 + 8 + 8), `get_type("Segment", "start")` is `"Point"`, and `get_type("Point", "y")` is `"int32"`.
The task starts as just the two query functions. Near the end, the interviewer adds that the schema arrives as raw text input like the example, so a parser is needed as well (Part 2).
### Clarifying Questions
- What should each function do for an unknown message name or field name: raise an error or return a sentinel value?
- Is "size" the sum of fixed scalar widths as assumed here, or the protobuf wire-encoded size with field tags and variable-length integers?
- Can a message refer to a message defined later in the schema, and can two messages embed each other in a cycle?
- Are there variable-size types such as `string` or `bytes`, or `repeated` fields, and how would they count toward size?
- How is the schema provided to the code: as an in-memory structure, or as text that must be parsed?
### Part 1 — Size and type queries
Assume the schema is already loaded into an in-memory structure of your choice. Design that structure and implement `get_size` and `get_type`.
```hint Shared building blocks
A message's size depends on the sizes of the messages it embeds, and several fields may embed the same message. Think about how many times each message's size really needs to be worked out.
```
#### Clarifying Questions for this Part
- Should a type error in the schema, such as a field whose type is neither a scalar nor a defined message, be reported when the schema is loaded or when it is queried?
- If a message embeds itself directly or through other messages, what should `get_size` return?
#### What This Part Should Cover
- A data model with fast lookup of a message and of a field within a message.
- Correct recursive sizing through embedded messages without redundant recomputation.
- Explicit behavior for unknown names, unknown types and self-embedding cycles.
### Part 2 — Parse the schema from text
The schema now arrives as a single string in the format of the example. Write a parser that builds the Part 1 structure, and connect it so that the queries work directly from the text.
```hint Separate reading from understanding
Formatting varies: a field may be written `int32 x=1;` or spread over lines with extra spaces. Consider splitting the input into small meaningful pieces before applying the grammar.
```
#### Clarifying Questions for this Part
- Can the input contain comments, blank lines, a `syntax` or `package` line, or definitions other than messages, such as enums or messages nested inside messages?
- Is the input guaranteed to be well formed, or should malformed input produce an error that says where the problem is?
- Can a message name or a field name appear twice?
#### What This Part Should Cover
- A parser that is robust to whitespace and layout differences and reports malformed input clearly.
- Validation that runs after the whole input is read, so forward references work and duplicates are caught.
- Integration with Part 1 without changing the query code, plus tests for the parser.
### What a Strong Answer Covers
- Confirming early how the schema is supplied and what the size rules are, since the parsing requirement surfaced late.
- A clean split between parsing, validation and querying, so a late requirement does not force a rewrite.
- Time and space complexity for loading the schema and for each query.
- Tests covering nested embedding, forward references, cycles, unknown names and formatting variants.
### Follow-up Questions
- How would `get_size` change if fields could be `repeated` or of type `string`, whose size depends on the data in a message rather than on the schema?
- If size had to follow the real protobuf wire encoding, with a tag per field and variable-length integers, what extra input would `get_size` need?
- How would you support messages declared inside other messages and fully qualified names such as `Outer.Inner`?
- How would you extend `get_type` to accept a dotted path such as `get_type("Segment", "start.x")`?
Overview: Implement size and field-type lookups over a simplified protobuf-style schema in which messages embed other messages, then write the parser that builds the schema from raw text. Tests schema data modeling, handling of nested, cyclic and unknown message references, clear error behavior, and robust parsing of proto-like definitions.