Katkat
Back

Parse a nested list from a string

TikTokSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to parse recursive nested structures using stack-based iteration or recursion and string manipulation.

Problem Statement

Given a string representation of a nested list, implement a function to parse it into a structured list of integers or lists. The input string contains integers, commas, and square brackets [ ]. Each list can contain integers or other nested lists. You can assume the input is well-formed.

Function Signature

def parse_nested_list(s: str) -> list:

Examples

Example 1: Input: "[1, [2, 3], 4]" Output: [1, [2, 3], 4]

Example 2: Input: "[10, [20, [30]]]" Output: [10, [20, [30]]]

Constraints

  • The string length is between 1 and 1000 characters.
  • Integers are non-negative and can be multi-digit.
  • All input strings are syntactically valid.

Considerations

  • How will you handle multi-digit numbers (e.g., "123")?
  • Consider edge cases like an empty list "[]" or a deeply nested list "[[[[1]]]]".

Hints

Hint 1

Consider using a stack to keep track of the current nesting level as you iterate through the string.

Hint 2

When you encounter a '[', push a new empty list onto the stack; when you encounter a ']', pop the current list and add it to the list now at the top of the stack.

Hint 3

For multi-digit numbers, use a temporary variable or string buffer to accumulate digits until you hit a non-digit character like a comma or closing bracket.

Follow-up questions

  • How would you modify your solution to handle negative integers?
  • What is the time and space complexity of your solution in terms of the number of characters in the string and the depth of nesting?
  • Could you implement this solution recursively instead of using an explicit stack?