Validate NFT Addition - codepath/compsci_guides GitHub Wiki

Unit 4 Session 1 Standard (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 structure of the input?

  • A: The input is a list of strings, where each string is either "add" or "remove".

• Q: What is the output?

  • A: The output is a boolean value: True if the actions are balanced, False otherwise.

• Q: What does it mean for the actions to be balanced?

  • A: Every "add" action must have a corresponding "remove" action, and no "remove" action should occur before a matching "add".

• Q: What should be returned if the list is empty?

  • A: True, since an empty sequence is trivially balanced.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use a stack to track "add" actions. For each "remove" action, check if there is a corresponding "add" on the stack. If the stack is empty when a "remove" is encountered, or if any "add" is left unmatched, the sequence is unbalanced.

1) Initialize an empty list called `stack` to simulate the stack behavior.
2) Iterate through each `action` in `actions`:
   a) If `action` is `"add"`, push it onto the stack.
   b) If `action` is `"remove"`, check if the stack is empty:
      i) If empty, return `False`.
      ii) If not empty, pop the top of the stack.
3) After the loop, return `True` if the stack is empty, otherwise return `False`.

**⚠️ Common Mistakes**

- Forgetting to return `False` if a `"remove"` action occurs with an empty stack.
- Not ensuring the stack is empty at the end to confirm all `"add"` actions were matched.

I-mplement

def validate_nft_actions(actions):
    stack = []

    for action in actions:
        if action == "add":
            stack.append(action)
        elif action == "remove":
            if not stack:
                return False
            stack.pop()

    return len(stack) == 0