algoadvance

You are keeping score for a baseball game with strange rules. The game consists of several rounds, where the scores of past rounds may affect future scores.

At the start of the game, you are given an empty record. You are given a list of strings ops, where ops[i] is the i-th operation you must apply to the record and is one of the following:

1. An integer x - Record a new score of x.
2. "+" - Record a new score that is the sum of the previous two scores.
3. "D" - Record a new score that is double the previous score.
4. "C" - Invalidate the previous score, removing it from the record.

Return the sum of all scores on the record after applying all the operations.

Clarifying Questions:

1. Q: What should we do if the input list ops is empty? A: If the input list ops is empty, the sum of scores should be 0 as there are no operations to perform.

2. Q: Can we assume the input list ops will always be valid and contain valid operations? A: Yes, we can assume that the input list will always be valid according to the given rules.

Strategy:

1. Initialize an empty list record to keep track of the scores.
2. Iterate through each operation in the list ops.
   • If the operation is an integer x, append x to record.
   • If the operation is "+", append the sum of the last two scores in record.
   • If the operation is "D", append double the last score in record.
   • If the operation is "C", remove the last score from record.
3. Finally, return the sum of all scores in record.

Time Complexity:

• The time complexity is O(n), where n is the number of operations, because we process each operation once.
• The space complexity is also O(n) for storing the scores in the list record.

Code:

Here’s a Python function for the solution:

def calPoints(ops):
    record = []
    for op in ops:
        if op == "+":
            record.append(record[-1] + record[-2])
        elif op == "D":
            record.append(2 * record[-1])
        elif op == "C":
            record.pop()
        else:
            record.append(int(op))
    return sum(record)

# Test cases
print(calPoints(["5", "2", "C", "D", "+"]))  # Output: 30
print(calPoints(["5", "-2", "4", "C", "D", "9", "+", "+"]))  # Output: 27
print(calPoints(["1"]))  # Output: 1

In these test cases:

• For ["5", "2", "C", "D", "+"], the expected output is 30.
• For ["5", "-2", "4", "C", "D", "9", "+", "+"], the expected output is 27.
• For ["1"], the expected output is 1.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?