A Programming Job Interview Challenge #13 – Brackets

July 22nd, 2008 by Xerxes Leave a reply »

As the title suggests, here is my solution for A Programming Job Interview Challenge #13 – Brackets

Your input is a string which is composed from bracket characters. The allowed characters are:’(‘, ‘)’, ‘['. ']‘, ‘{’, ‘}’, ‘< ’ and ‘>’. Your mission is to determine whether the brackets structure is legal or not.

Example of a legal expression: “([](< {}>))”.

Example of an illegal expression: “({< )>}”.

Provide the most efficient, elegant and simple solution for that problem.I think that this is a well known problem but I am not sure, so excuse me if this week’s question is screwed.

I think this one is rather easy….unless i missed something…..

So to start with, you have a dictionary/hashtable and a stack. The dictionary keys consist of all opening bracket characters (ie: “(, [, <, {" ), and the corresponding values for each key are the closing bracket characters (ie: "), ], >, }”).

Now the process itself is to iterate over the string from left to right, and look up the current character in the dictionary.

  • If the current character is an opening bracket, get the corresponding close bracket, push it on the stack and move on.
  • If it is not an opening bracket, then pop the current closing bracket off the stack.
  • If the popped character is the same as the current character, then move on (ie: valid closing bracket match).
  • If the popped character is NOT the same as the current character, then we’ve hit a broken sequence and error out here.

There is some fine-tuning that would need to be done in the case where the input sequence commenced with a closing bracket and there is nothing in the stack, but what you see is basically it. :) Simple and elegant IMO.

Thank God i don’t need to explain the mathematical complexity of this one…I really wouldn’t know where to start.

Be Sociable, Share!

2 comments

  1. James Curran says:

    Don’t know the complexity?

    You perform a fixed number of steps on each character, so we start with O(n * X).

    So, now we only have to determine X. For each character, we:
    – lookup a character in a dictionary/hashtable, we we determined in a previous Dev102 challenge is either O(1) or O(ln N) depending on the algorithm used.
    – push or pop a value from a stack: O(1).

    Put them all together, we have N * 1 * 1 or N * ln N * 1. O(N) or prehaps O(N ln N).

    Of course, being O(N) isn’t the final word on efficiency. It merely means that the time it taken in given by the function:
    T = C*N + K, and your C value (X in the above analysis) is rather high. (O(1) merely means that value is fixed, not that it is low).

    I gave the full code on mine at http://www.honestillusion.com

    (EDIT: fixed URL link a the bottom)