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.

In it’s 11th installment in a series of posts of interesting/quirky questions you may (or may not) be asked in a job interview, this series has definitely challenged everything I knew (or thought I knew) about computer science fundamentals and mathematical reasoning.

My response is to the 11th question about summing numbers is below:

PROBLEM:
Given a list of n integers and another integer called m, determine (true / false) if there exist 2 numbers in that list which sum up to m.
Example: 2,6,4,9,1,12,7 and m=14 -> 2 and 12 sum up to 14, so the answer is true.
Provide the best algorithm in both manners: performance and memory to solve this puzzle. Don’t forget to mention the complexity of your solution!

Answer
I suppose I will start by giving my answer first because it seems logical to me, and i’m generally better at providing solutions rather than the mathematical proof behind them 🙂

Basically put, the most efficient way I can think of to determine if any of the numbers sum up to m is to work from left-right, subtract the current number from m, and then scan the rest of the list for the resulting number.
ie:

In a list consisting of the numbers 2,6,4,9,1,12,7 and m=14, my process will look like:

idx = 0
val = a[idx] (2)
searchFor = m - val (12)
Found 12 in the 5th position


Because you’re working from left to right, you don’t need to scan the array from the start every time, so on the first scan you’ll search through n – 1 elements, on the second scan you’l search through n – 2 elements and so on until you’re up to the last element in the array. According to the rules, there needs to exist 2 numbers which add up to m, so the last element CANNOT = m

I believe the most efficient way of scanning the list of values. Happy to be proven wrong 🙂 I guess one optimisation would be to sort the elements of the array upfront, and then you can use a super-efficient sorted list scan algorithm, if you have a large array of elements. Also one of the commenters questioned whether duplication of numbers was/was not allowed – i see this point as irrelevant under this solution because 7 + 7 = 14, so why wouldn’t it be allowed?!

Reasoning

Here (for me) is where things start falling apart. I might have this totally wrong but i’ll give it a shot anyway….

Given m=14,
With List = 2, 6, 4, 9, 1, 12, 7 (ie: 7 elements in array)

The maximum complexity of the alg would be given by the maximum number of scans it would have to do to find the winning combination of numbers. In this example, it would be expressed as:
(1 * 7-1) + (1 * 7-2) + (1 * 7-3) + (1 * 7-4) + (1 * 7-5) + (1 * 7-6)
Again, we don’t worry about case 7-7 because there needs to exist 2 numbers which add up to m (and either way it’s a zero ;P)

Which roughly translates into:
6 + 5 + 4 + 3 + 2 + 1

Now substituting for n, we see it comes to
(n – 1) + (n – 2) + (n – 3) + … (n – (n – 2)) + (n – (n – 1))
which boils down to n(n+1)/2

So the maximum complexity of this solution would be O(n(n+1)/2)

This feels like such a hacky maths proof – my HS maths teacher would be livid…