Understand what the interviewer is asking for by using test cases and questions about the problem.
- Established a set (2-3) of test cases to verify their own solution later.
- Established a set (1-2) of edge cases to verify their solution handles complexities.
- Have fully understood the problem and have no clarifying questions.
- Have you verified any Time/Space Constraints for this problem?
HAPPY CASE
Input: "(())"
Output: 2
Input: "(()(()))"
Output: 6
EDGE CASE (Empty String)
Input: ""
Output: 0
Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.
For brackets problems, we want to consider the following approaches:
Plan the solution with appropriate visualizations and pseudocode.
General Idea: (STACK) Iterate through input string and use a Stack to keep track of all of the computations and incomplete pairings.
1) Create a Stack
2) Iterate through the input string from left to right:
a) If we see a "(":
i) If we see a "(": push a 0 into stack
b) If we see a ")":
i) Add current value to previous value
3) Return the only item which equals total value of stack.
General Idea: (Core Count) Iterate through input string and keep track of the number of open parenthesis this represents the number of exterior set of parentheses that contains this core. If we close this core lets use bit manipulation to double the value according to the number of exterior set of parentheses and add it to the total.
1. Initialize the total and current balance
2. Iterate through the string and keep track of the number of exterior set of parentheses using balance
a. Upon seeing a opening parentheses: add to balance
b. Upon seeing a closing parentheses: reduce the balance
i. If it happens to close, because the previous item was an opening parentheses.
ii. Then this core needs to be added to the total and it's value is doubled with each exterior set of parentheses(aka the balance).
3. Return the total
⚠️ Common Mistakes
Implement the code to solve the algorithm.
Approach #1 Stacks
class Solution:
def scoreOfParentheses(self, S: str) -> int:
# Create a Stack
stack = [0]
# Iterate through the input string from left to right
for c in s:
# If we see a "(": push a 0 into stack
if c == "(":
stack.append(0)
# Else we see a ")": add current value to previous value
else:
enclosedVal = stack.pop()
stack[-1] += max(2 * enclosedVal, 1)
# Return the only item which equals total value of stack
return stack.pop()
Approach #2 Core Count
class Solution:
def scoreOfParentheses(self, s: str) -> int:
# Initialize the total and current balance
total = bal = 0
# Iterate through the string and keep track of the number of exterior set of parentheses using balance
for i, x in enumerate(s):
# Upon seeing a opening parentheses: add to balance
if x == '(':
bal += 1
# Upon seeing a closing parentheses: reduce the balance
else:
bal -= 1
# If it happens to close, because the previous item was an opening parentheses.
if s[i-1] == '(':
# Then this core needs to be added to the total and it's value is doubled with each exterior set of parentheses(aka the balance)
total += 1 << bal
# Return the total
return total
Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
Evaluate the performance of your algorithm and state any strong/weak or future potential work.
Assume N
represents the number of items in the string
O(N)
because we need to traverse all items in the stringO(N)
or O(1)
O(N)
space.O(1)
Space.