Katkat
Back

Implement a JSON Parser

SnowflakeSoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to implement a recursive-descent parser for a subset of the JSON format, focusing on string manipulation, state management, and hierarchical data structure construction.

Problem Statement

Implement a function parse_json(json_string) that parses a JSON string into its corresponding Python data structures (e.g., dicts, lists, strings, numbers, booleans, and None). You do not need to support escaping characters other than \" and \\.

Requirements

  • The parser must support: objects ({}), arrays ([]), strings ("..."), integers and floats (123, 12.34), booleans (true, false), and null.
  • You must handle whitespace appropriately between tokens.
  • If the input string is malformed, raise a ValueError.

Function Signature

def parse_json(json_string: str) -> any:
    pass

Examples

Example 1: Input: "{\"a\": 1, \"b\": [true, null]}" Output: {'a': 1, 'b': [True, None]}

Example 2: Input: "[1, 2.5, \"hello\"]" Output: [1, 2.5, 'hello']

Constraints

  • The input string may contain nested structures of arbitrary depth.
  • The input string will contain valid whitespace.
  • Assume the input is a single top-level JSON value.

Hints

Hint 1

Use a pointer or an iterator to keep track of the current position in the string as you consume characters.

Hint 2

Implement separate helper functions for each JSON type (e.g., `parse_object`, `parse_array`, `parse_string`, `parse_number`).

Hint 3

Use a recursive approach where each helper function calls the main `parse_value` function when encountering nested structures.

Follow-up questions

  • How would you modify your parser to handle Unicode escape sequences like \uXXXX?
  • What changes would be necessary to support a streaming input, such as a file handle or a socket, rather than a full string in memory?
  • How would you improve the error reporting to provide the line number and column of the character that caused a parse failure?