The fourteenth post of the series of programming job interview challenge is out, 79 comments with answers were provided to job interview challenge #13. We didn’t publish a question last week due to a sever lack of time, so another week is gone and here we are again.

Mark R was the first to provide a correct and detailed answer (which I can quote here):

As you examine each character, classify it as either an opening or closing bracket. If it’s an opening bracket, push it onto a stack. If it’s a closing bracket, pop the top character off of the stack; if the stack was empty, or the character was not the matching open bracket, then return an error. At the end of input, if the stack is empty, you have a legal expression.

C++ has a built-in stack class, so this becomes a trivial problem. I’m not sure about other languages. You could always simulate a stack by appending and deleting characters from the end of a string.

So, in one word, the most efficient answer is use a stack. Here is a nice image which was crafted by David Tchepak in his blog post Brackets, braces, parentheses, and other such creatures:

During the Job Interview Challenge Series we are running here at Dev102.com, we usually get some comments from readers who think that the quality of a specific question is not good. Here are some of those comments:

1. “I hate interview questions like this, as it’s just a race to see who gets the a-ha moment first“.
2. “This is not a good interview question. What does it tell you about someone’s engineering ability? Little. It’s a brain-teaser; either you get it or you don’t”.
3. “Really enjoying the problems so far but I’m a little disappointed with this one. I prefer ‘thinking’ problems to ‘research’ ones“.
4. “Isn’t this an awfully language-specific question?“.
5. “If you presented this problem in an interview and made me an offer, I’d turn you down“.

On the other hand, many readers provided answers to the questions and enjoyed participating in those challenges. Some thought that the questions are very good:

The sixth of the series of programming job interview challenge is out. Other then commenting the solution, I remind you that you can post the solution on your blog and get a link next week!

Here is the solution to the previous challenge:
Two-way merge sort (External Sorting) : The idea is breaking the big file into subfiles, sorting them and than merging them back together. In the first pass read one page at a time, the records in the page are sorted (quicksort for example) and the page is written back to disk. in subsequent passes, each pair of sorted output from the previous pass are read and merged to produce sorted subfile twice as long:

1. Read each page, Sort it, Write it back
2. while more than one sorted subfile:
while subfiles from previous pass left to merge:
- Choose next two subfiles from previous pass
- Read each subfile into a memory page (one page at a time)
- Merge the subfiles (remember each of them is already sorted), write output to a memory page
- Write output page to disk when needed.

This is the fifth challenge in the series of programming job interview challenge. As usual, we’ll provide an answer to the previous challenge and give you a new challenge to keep you busy this week. Other then commenting the solution, I remind you that you can post the solution on your blog and let us know about it [...]

This is the fourth post in the series of programming job interview challenge. Today, I will provide the answer to job interview challenge #3, talk about readers answers (all of the comments are now approved) and give you a new challenge. So, lets get into business:

The correct answer to challenge #3:

1. Start with the lower left cell (first column, last row).
2. If the value matches, you’re done.
3. If the searched value is bigger than the current cell, go right. That way an entire column is eliminated (all of the values left in that column are lower than the searched value). If you can’t go right - the searched value is not in the matrix.
4. If the searched value is smaller than the current cell, go up. That way an entire row is eliminated (all of the values left in that row are bigger than the searched value). If you can’t go up - the searched value is not in the matrix.
5. Go back to 2.

This post is third in the series of programming job interview challenge, if you are not yet familiar with these series please take your time and read:

1. A Programming Job Interview Challenge
2. A Programming Job Interview Challenge #2

Well, last weeks challenge was very successful, all of the comments which contain answers to the question are now approved and can be viewed in challenge #2 post.

Last week I posted A Programming Job Interview Challenge which was very successful, both in the amount of page views and, in the amount of comments and mails we received. This fact made us (the Dev102 team) decide to add a weekly programming job interview challenge column to www.Dev102.com.