1
\$\begingroup\$

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 + diffCounter

text1=")))("
print(bracket_match(text1))
\$\endgroup\$
3
\$\begingroup\$

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 of text, then using a for loop of over the range(length), assigning the index to i, but then never using i for anything other than fetching the character text[i].

Far, far better is looping over the letters of text:

    for ch in text:
        # use `ch` here.

Efficiency:

        if text[i] == '(':
           # ...
        elif text[i] == ')':
           diffCounter -= 1
        if diffCounter < 0:
           diffCounter += 1
           # ...

Will diffCounter ever be negative, without first subtracting 1 from it? No? Perhaps the next test belongs in the elif 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 the diffCounter is an understandable variable name (barely), the variable named answer is completely mysterious. Answer to what? Why is it incremented when there is an underflow? Why is it added to diffCounter at the end. Not a comment in sight, and the code is anything but self documenting.


Follow PEP-8 coding standards, and use pylint or other style checker. For instance, variables should not be camelCase, and answer +=1 needs an extra space.

\$\endgroup\$
  • \$\begingroup\$ Just for the fun of it, I've refactored your suggestions, and renamed some variables into this repl. \$\endgroup\$ – holroy Feb 10 at 1:21
  • \$\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 Feb 10 at 5:58
1
\$\begingroup\$

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)
\$\endgroup\$
  • \$\begingroup\$ Forgot to return the len of the stack obviously, thanks! \$\endgroup\$ – hodisr Feb 9 at 16:25
  • \$\begingroup\$ I like the stack approach, but how does it handle tests starting with ending brackets? Or have a surplus of ending brackets? Are those conditions properly handled by the res += 1 option? \$\endgroup\$ – holroy Feb 10 at 1:06
  • \$\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 Feb 10 at 8:10
  • \$\begingroup\$ apparently you copied most part of your code from here. 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 Feb 10 at 8:52
  • \$\begingroup\$ ... and I think it is very impolite to use code of other people without citing the source. \$\endgroup\$ – miracle173 Feb 10 at 8:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.