Market Token Value - codepath/compsci_guides GitHub Wiki

TIP102 Unit 3 Session 2 Advanced (Click for link to problem statements)

U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Q: What is the input to the problem?
  • A: The input is a string token containing pairs of mystical brackets () representing the structure of a mystical token.
• Q: What is the output?
  • A: The output is an integer representing the total value of the mystical token string based on its structure.
• Q: How is the value of the token calculated?
  • A:
    • () has a value of 1.
    • The value of two adjacent tokens AB is the sum of their individual values.
    • The value of a nested token (A) is twice the value of the token inside the brackets.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use a stack to manage the nested structure of the token. As you iterate through the string, maintain a running score that accumulates the values based on the structure of the token.

1. Initialize an empty stack and a variable `score` set to 0.
2. Iterate over each character in the `token` string:
   1. If the character is `'('`, push the current `score` onto the stack and reset `score` to 0.
   2. If the character is `')'`, pop the top value from the stack and update `score` to be the sum of the popped value and the maximum of `2 * score` or 1.
3. After iterating through the string, return the final `score` as the value of the token.

⚠️ Common Mistakes

• Forgetting to reset the score after pushing onto the stack.
• Incorrectly calculating the score for nested structures.

I-mplement

def token_value(token):
    stack = []
    score = 0

    for char in token:
        if char == '(':
            stack.append(score)
            score = 0
        else:
            score = stack.pop() + max(2 * score, 1)

    return score

# Example usage
print(token_value("()"))  # Output: 1
print(token_value("(())"))  # Output: 2
print(token_value("()()"))  # Output: 2