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!

Related posts:

  1. A Programming Job Interview Challenge #14 – 2D Geometry Well I could tell a lie and say that I...
  2. A Programming Job Interview Challenge #11 – Summing Numbers In it’s 11th installment in a series of posts of...
  3. Level 57 – Outland, i’m OMW I’m just about close enough to join Outland….after my 4...
  4. Passing Interfaces Instead of Concrete Classes I’ve just read a blog post about why you should...
  5. MissingMethodException: ? Sometimes though when you’re changing interfaces across several projects, you...

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)