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.

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)