Convert Leveled Rich-Text Tokens into Nested Lists

Question

Convert leveled rich-text tokens into nested lists, where each token represents a level of indentation in the list structure.

Codemia · Accepted Answer

To convert leveled rich-text tokens into nested lists, we will iterate through the tokens and maintain a stack that keeps track of the current list structure. Each token will indicate its level of indentation, which will determine where it should be inserted in the nested list.

1. Initialize an empty list `result` and a stack to keep track of the current level.
2. Loop through each token:
   - If the token's level is greater than the stack's size, create a new list and append it to the last list in the stack.
   - If the token's level is less than the stack's size, pop from the stack until the correct level is reached.
   - Append the token to the current list and push it onto the stack.
3. Return the `result` list.

The time complexity of this algorithm is O(n), where n is the number of tokens, as we process each token exactly once. The space complexity is O(h), where h is the maximum depth of the nested lists, due to the stack used to keep track of the current level.

```python
from typing import List, Union

def convert_tokens_to_nested_lists(tokens: List[tuple]) -> List[Union[str, List]]:
    result = []
    stack = [result]

for token, level in tokens:
        # Create a new list for the current token
        new_list = [token]
        # Adjust the stack to the current level
        while len(stack) > level:
            stack.pop()
        # Append the new list to the current level
        stack[-1].append(new_list)
        # Push the new list onto the stack
        stack.append(new_list)

return result
```
This code defines a function that takes a list of tokens with their respective levels and converts them into a nested list structure.

Consider scenarios such as:
- Tokens with the same level appearing consecutively.
- Tokens with invalid levels (e.g., negative levels).
- An empty input list.
Handling these cases ensures robustness in the solution.

Convert Leveled Rich-Text Tokens into Nested Lists

Figma

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Approach

Algorithm

Submit Your Answer

Figma Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string