Katkat
Back

Solve Refueling and JSON Parsing Tasks

GeicoSoftware Engineer · Onsite
HardSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests greedy strategies for path optimization and recursive descent parsing techniques for custom data structures.

Part 1: Minimum Refueling Stops

Given a target distance target, a starting fuel level startFuel, and a list of stations stations where stations[i] = [position_i, fuel_i], determine the minimum number of refueling stops required to reach the target. If it is impossible, return -1.

Constraints

  • 0 <= target <= 10^9
  • 0 <= startFuel <= 10^9
  • 0 <= stations.length <= 500

Example

Input: target = 100, startFuel = 10, stations = [[10, 60], [20, 30], [30, 30], [60, 40]] Output: 2 Explanation: Refuel at position 10 and position 60.

Part 2: JSON-Lite Parser

Implement a function that parses a simplified JSON-like string into a nested dictionary or list structure. The input supports:

  • Strings enclosed in double quotes (handle escaped quotes like \").
  • Integers.
  • Booleans (true, false).
  • Null values (null).
  • Objects {} and Arrays [].

Function Signature

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

Example

Input: {"id": 1, "tags": ["a", "b"], "meta": {"valid": true}} Output: {'id': 1, 'tags': ['a', 'b'], 'meta': {'valid': True}}

Edge Cases

  • Empty objects/arrays.
  • Nested structures.
  • Malformed input (raise an exception).

Hints

Hint 1

For the refueling problem, use a max-priority queue to keep track of reachable fuel stations that you have passed but not yet visited.

Hint 2

For the JSON parser, use a recursive descent approach, maintaining a cursor/pointer to track the current position in the string during tokenization.

Hint 3

When parsing the JSON string, differentiate between structural characters like braces or brackets and literal values like strings or numbers by checking the character at the current index.

Follow-up questions

  • How would the refueling logic change if stations have a maximum fuel capacity they can dispense?
  • How does your JSON parser handle extremely large, deeply nested inputs? Could it trigger a stack overflow?
  • How would you optimize the JSON parser to process the input as a stream rather than loading the entire string into memory?