I would like to receive feedback on my coding interview for the following problem:
Bracket Match
A string of brackets is considered correctly matched if every opening bracket in the string can be paired up with a later closing bracket, and vice versa. For instance, “(())()” is correctly matched, whereas “)(“ and “((” aren’t. For instance, “((” could become correctly matched by adding two closing brackets at the end, so you’d return 2.
Given a string that consists of brackets, write a function bracketMatch that takes a bracket string as an input and returns the minimum number of brackets you’d need to add to the input in order to make it correctly matched.
Explain the correctness of your code, and analyze its time and space complexities.
Examples:
input: text = “(()” output: 1
input: text = “(())” output: 0
input: text = “())(” output: 2 Constraints:
[time limit] 5000ms
[input] string text
1 ≤ text.length ≤ 5000 [output] integer
def bracket_match(text): diffCounter = 0 answer = 0 length = len(text) for i in range(length): if text[i] == '(': diffCounter += 1 elif text[i] == ')': diffCounter -= 1 if diffCounter < 0: diffCounter += 1 answer +=1 return answer + diffCountertext1=")))("print(bracket_match(text1))
2 Answers2
Doesn't look like you've done this:
Explain the correctness of your code, and analyze its time and space complexities.
This is an anti-pattern:
length = len(text) for i in range(length): # code using only `text[i]`, but never using `i`You are computing the length oftext, then using afor loop of over therange(length), assigning the index toi, but then never usingi for anything other than fetching the charactertext[i].
Far, far better is looping over the letters oftext:
for ch in text: # use `ch` here.Efficiency:
if text[i] == '(': # ... elif text[i] == ')': diffCounter -= 1 if diffCounter < 0: diffCounter += 1 # ...WilldiffCounter ever be negative, without first subtracting 1 from it? No? Perhaps the next test belongs in theelif clause:
if text[i] == '(': # ... elif text[i] == ')': diffCounter -= 1 if diffCounter < 0: diffCounter += 1 # ...But that is still subtracting 1 and then (possibly) immediately adding 1 again. Better: check for the underflow condition first.
if text[i] == '(': # ... elif text[i] == ')': if diffCounter > 0: diffCounter -= 1 else: # ...While thediffCounter is an understandable variable name (barely), the variable namedanswer is completely mysterious. Answer to what? Why is it incremented when there is an underflow? Why is it added todiffCounter at the end. Not a comment in sight, and the code is anything but self documenting.
FollowPEP-8 coding standards, and usepylint or other style checker. For instance, variables should not becamelCase, andanswer +=1 needs an extra space.
- \$\begingroup\$@holroy I disagree with your space complexity. While it is true the input string has N characters, you are only using 2 extra scalar state variables, so I'd say the space complexity is \$O(1)\$.\$\endgroup\$AJNeufeld– AJNeufeld2019-02-10 05:58:48 +00:00CommentedFeb 10, 2019 at 5:58
From my experience in job interviews that question usually takes you to implements a solution with one type of data-structure.
A good implementation will be using a stack that load each '(' bracket and unloads each ')' bracket. In that way you can iterate over the text and if you encounter ') bracket beforehand you add to the result.
In Python you can use list type object as a Stack,reference.
Implementation example using stack in python3:
def bracket_match(text): pairs = {'(': ')'} # Using dictionary for O1 get sk = [] res = 0 for c in text: if c in pairs: sk.append(pairs[c]) elif sk and c == sk[-1]: sk.pop() else: res += 1 return res + len(sk)
- \$\begingroup\$Forgot to return the len of the stack obviously, thanks!\$\endgroup\$hodisr– hodisr2019-02-09 16:25:20 +00:00CommentedFeb 9, 2019 at 16:25
- 2\$\begingroup\$a big -1 from me. 1) This is a code review. you should review the code of the OP and not present your solutions of the problem. If you have your implemented a solution and want to know what this community thinks about your solution then post your solution as question and it will be reviewed.2) it makes no sens to use a stack if an integer variable is sufficient, 3)your code isn't good and the OP should not try to copy it.\$\endgroup\$miracle173– miracle1732019-02-10 08:10:33 +00:00CommentedFeb 10, 2019 at 8:10
- 3\$\begingroup\$apparently you copied most part of your code fromhere. But the original code handles different types of brackets and this makes it necessary to use a stack. In the OP there is only one kind of brackets is used and a stack makes no sense. Also the usage of the dictionary 'pair' makes sense in the original source but no sense in your code. It does not make sense to present code here that was written by other people that you apparently do not completely understand ...\$\endgroup\$miracle173– miracle1732019-02-10 08:52:58 +00:00CommentedFeb 10, 2019 at 8:52
- 3\$\begingroup\$... and I think it is very impolite to use code of other people without citing the source.\$\endgroup\$miracle173– miracle1732019-02-10 08:54:41 +00:00CommentedFeb 10, 2019 at 8:54
- 1\$\begingroup\$@hodisr, Your suggestion to start with a stack is a good one, but if you can get rid of the stack and reduce the space complexity (without sacrificing the time complexity), you should at least make that suggestion to your interviewer during your coding interview and ask if they would prefer that solution (to which, they'll probably say 'yes'). And no, those problems you saw on leetcode and hackerrank may all look identical to this one, but they're not completely identical. And if you want to do well during your technical coding interviews, you need to be able to pick up on those differences.\$\endgroup\$Stephan Branczyk– Stephan Branczyk2021-05-07 00:56:36 +00:00CommentedMay 7, 2021 at 0:56
You mustlog in to answer this question.
Explore related questions
See similar questions with these tags.