Coding Algorithms — Parsing Strings

source: quanta magazine

Many FAANG level companies likes to ask string parsing problems to check how candidates approach the problem and what all test cases they handle. In this post I will demonstrate some common string parsing problems that have been asked by some of these companies and how to approach the problems.

Problem 1:

Given an array in the form of a string, which may contain positive integers and also nested arrays. Parse the string to return an array object.

Assume that the string is a valid array and do not contain any spaces.

Example:

Input: "[3,1,46,[25,901,[30],66],0,[78,21,[55,[378]]]]"
Output: array object [3,1,46,[25,901,[30],66],0,[78,21,[55,[378]]]]

Solution:

The problem can be solved using both recursive as well as non-recursive approaches.

In the recursive approach, we keep track of the number of open brackets using a counter. Whenever we encounter an open bracket we increment the counter by 1 and whenever we encounter a closed bracket we decrement the counter by 1.

Also we keep track of the start and end index of the next level nested array.

start index of next level nested array = (s[i]=='[' and open brackets count = 2)
end index of next level nested array = (s[i]==']' and open brackets count = 1)

Once we get the start and end indices for the next level nested array, we recursively call the method on the next level nested array.

Time and space complexity is O(N).

The non-recursive approach uses stacks. The code with stack is much more cleaner to implement and understand.

The idea is that whenever we encounter a closing bracket, we start popping from the top of stack until we find a opening bracket. Store all the integers found by popping in a temporary array and then append the reverse of the temporary array back into the stack.

Time and space complexity is O(N).

Problem 2:

Given an arithmetic expression in the form of a string, evaluate the expression.

Assume that the expression contains the operators ‘+’, ‘-’, ‘*’ and ‘/’, inputs are real numbers (+ve as well as -ve floating point) and opening and closing brackets ‘(‘, ‘)’.

Assume that the string is a valid expression and do not contain any spaces.

Example:

Input: "(32.9+56.01-(85.5-34.0+100.125))+4.75*5.0/2.4"
Output: -52.82

Solution:

The idea is to use stack here also.

1. Whenever we encounter ‘*’ or ‘/’, we do inplace evaluation and update stack with the operation result.
2. Whenever we encounter ‘)’, we start popping from top of stack into a temp stack until we encounter a ‘(‘. Here the operands are ‘+’ and ‘-’ because ‘*’ or ‘/’ would already have been evaluated before encountering the closing bracket. Finally we do normal left to right evaluation on temp stack.

Time and space complexity is O(N).

Problem 3:

Parse a nested JSON. Given a JSON string representation, convert it into a nested dictionary of key-value pairs (similar to json.loads() method in python).

Assume that the string is a valid JSON and do not contain any extra spaces.

The keys are strings and values could be strings or JSON strings themselves.

Example:

Input: "{'firstname':'elon','lastname':'musk','attributes':{'age':40,'height':'175cm','weight':'150 pounds'}}"
Output: dictionary object {'firstname':'elon','lastname':'musk','attributes':{'age':40,'height':'175cm','weight':'150 pounds'}}

Solution:

We use stack to solve this problem too, similar to the 1st problem of parsing an array.

Save the key and the value (separated by : in JSON) in consecutive index positions in the stack.

Time and space complexity is O(N).