Parse a protobuf-like schema and answer queries

Q: Parse a protobuf-like schema and answer queries

This question evaluates proficiency in parsing grammar-like schemas, scope-based name resolution for nested types, symbol-table construction, and designing efficient data structures for answering schema queries.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Q: What difficulty level is this interview question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Applied.

Q: What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Applied during technical interviews.

Question

Loading...

You are given a single string schema describing message types in a simplified, protobuf-like language. Your task is to parse the schema and support two query functions.

Schema language

A message definition has the form:
- message <MessageName> { <items> }
An item inside a message is either:
1. A field definition:
  - <field_name> <type>;
2. A nested message definition (recursively following the same grammar).
<type> is either:
- a primitive type: int , long , float , double , bool , string
- or a message type name (either a top-level message or a nested message).
Whitespace and newlines may appear anywhere and should be ignored except as separators.

Name resolution for nested messages

A nested message Inner declared inside Outer has the fully-qualified name Outer.Inner .
A field type reference may use either:
- a fully-qualified name (e.g., Outer.Inner ), or
- an unqualified name (e.g., Inner ). For unqualified names, resolve to the nearest enclosing scope first, then outward, then top-level.

Functions to implement

Implement the following two functions after parsing schema:

get_size(message_name) -> int
- Returns the number of direct fields declared in the specified message (do not count fields of nested message definitions unless they are direct fields of that message).
get_type(message_name, field_name) -> string | null
- Returns the declared type of field_name in message_name .
- Return null (or an equivalent sentinel) if the message or field does not exist.

Example

Given:

message Vehicle {
  wheels int;
  engine Engine;

  message Engine {
    model string;
  }
}

get_size("Vehicle") == 2 (fields: wheels , engine )
get_type("Vehicle", "engine") == "Engine"
get_size("Vehicle.Engine") == 1
get_type("Vehicle.Engine", "model") == "string"

Constraints (assume)

Total schema length up to ~10^5 characters.
Total number of messages + fields up to ~10^5.
Queries should be fast after parsing (e.g., close to O(1) average per query).