Baseball Game
Baseball Game is a Easy Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Stack Patterns pattern, in the Simulation / Backtracking Helper subpattern.
Problem statement
Implement Solution.calPoints, which evaluates a sequence of baseball scoring operations in the order given by operations. Maintain the scores that are currently recorded; an integer operation records that integer as a new score.
The operation + records a score equal to the sum of the two most recently recorded scores. The operation D records twice the most recently recorded score. The operation C removes the most recently recorded score, so that score no longer contributes to the total or to later operations.
Return the sum of all scores remaining after every string in operations has been processed. Every operation is valid: + always has two previous scores available, and D and C always have one. All answers fit in a 32-bit signed integer.
Example 1:
Input: operations = ["7","3","+","D","C","5"] Output: 25 Explanation: The scores become 7, 3, 10, and 20. C removes 20, after which 5 is added, leaving 7 + 3 + 10 + 5 = 25.
Example 2:
Input: operations = ["-4","6","D","+","C","9"] Output: 23 Explanation: The scores become -4, 6, 12, and 18. C removes 18, after which 9 is added, giving -4 + 6 + 12 + 9 = 23.
Example 3:
Input: operations = ["10","C","8","8","+"] Output: 32 Explanation: The first score is removed, leaving 8 and 8; the final operation adds 16, so the total is 8 + 8 + 16 = 32.
Constraints:
- 1 <= len(operations) <= 1000 - Each element of operations is either a valid decimal integer, "+", "D", or "C". - Every "+" operation has at least two previously recorded scores when processed. - Every "D" operation has at least one previously recorded score when processed. - Every "C" operation has at least one previously recorded score when processed. - The returned answer fits in the 32-bit signed integer range.
Topics and companies
Topics: Stack, Array, Simulation.
How to practise Baseball Game on Thita.ai
Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n), where n is the number of operations. time and O(n) for the stack of recorded scores. space.
Open Baseball Game in the code editor, or read the Baseball Game editorial for a worked solution with its approach and complexity analysis.
Where Baseball Game sits in the DSA pattern sheet
- Stack Patterns pattern guide
- Simulation / Backtracking Helper subpattern
- The full DSA patterns sheet
- All coding practice problems
Problems related to Baseball Game
Other problems that use the same Simulation / Backtracking Helper and Stack Patterns techniques:
- Asteroid Collision — Medium, same subpattern
- Decode String — Medium, same subpattern
- Reconstruct Itinerary — Hard, same subpattern
- Simplify Path — Medium, same subpattern
- Basic Calculator — Hard, same pattern
- Basic Calculator II — Medium, same pattern