FastPrepRestricted JSON Parser

Restricted JSON Parser

Old Mission logoOld Mission● HardFULLTIMEPHONE SCREEN
Learn

Problem statement

Implement a parser for a restricted JSON language. Given a valid JSON string text, parse it without using a JSON library and return its canonical serialization.

The supported values are:

  • null, true, and false
  • integers
  • strings enclosed in double quotes
  • arrays
  • objects with string keys

Strings may contain the escapes \", \\, \n, and \t. Whitespace outside strings is insignificant.

The canonical serialization must:

  • contain no insignificant whitespace;
  • preserve array order;
  • sort every object's members by decoded key in lexicographic order;
  • serialize literals and integers in their ordinary JSON form; and
  • escape quotes, backslashes, newlines, and tabs inside strings.

Function

normalizeJson(text: String) → String

Examples

Example 1

text = " { \"b\" : [true, null], \"a\" : \"line\\nnext\" } "return = "{\"a\":\"line\\nnext\",\"b\":[true,null]}"

The parser discards whitespace outside strings, sorts object keys so a precedes b, and emits the newline as \n.

Example 2

text = "[\"a\\\\b\",-12,{\"x\":false}]"return = "[\"a\\\\b\",-12,{\"x\":false}]"

The backslash inside the first string remains escaped, and nested values retain their original order.

Constraints

  • 1 <= text.length <= 20000
  • text is valid under the restricted grammar.
  • Nesting depth is at most 100.
  • Integers are in the range [-10^9, 10^9], use no leading zero except for 0, and never use negative zero.
  • Object keys are unique within each object.
  • Unescaped string characters are printable ASCII characters other than double quote and backslash.
  • Do not use a language-provided JSON parser or serializer.

More Old Mission problems

See Old Mission hiring insights
public String normalizeJson(String text) {
  // Write your code here.
}
text" { \"b\" : [true, null], \"a\" : \"line\\nnext\" } "
expected"{\"a\":\"line\\nnext\",\"b\":[true,null]}"
Checking account…