8 coding problems Part 1

8 Coding Questions:

In two weeks I got interviewing for a position of two big IT companies. During the interviews they asked me some interesting questions that really puzzled me. After the gruesome process I truly learn a few things or two about some fundamental rules in programming and computer science and if I don't put them down one day I'm bound to forget. Also, maybe one day if my blog is read by more than a few people then I hope this can help some enlightened minds out there to think deeper about the code they write, and keep improving their skills. I don't know if exposing these questions will infringe the rules of the companies that I got interviewed for, so let's remain anonymous with them and pretend that I got interviewed by G-M. (Yes, there's a company called GM though I have no idea if it does hire programmers. All I heard is that it's going bankrupted~ But maybe this is my misinformation so don't count on it.)

Q.1 Write a function that find integer k in an n-by-n matrix. However, this matrix has this property that:
i. the value of the cell in each column is non-decreasing, and;
ii. the value of the cell in each row is non-decreasing as well.

x11 x12 ... x1n
x21 x22 ... x2n
. ... ... .
. ... ... .
xn1 xn2 ... xnn where xai <= xak, and xmb <= xnb

I got this question in one of the first interviews! After sharing about my research with the interviewer, and my nerves started to calm down, he dropped me this bomb and not only did he ask me to write the fastest algorithm that could solve the problem, he also asked me to write the code for it! Not pseudocode, but real code! Well I thought about using Java (my natural language) but I kind of want to impress him so I digged up whatever C knowledge I have remaining in my cerebrum and chunked out the code once I got enough hints from him to use an algorithm that uses pointer! Took me around 30 min, but that was only I guess since I was in the room and the whole interview last around 55 min and we talked a LONG time about our project when I had to explain what AOP was!

Answer:

This questions has 3 different answers, but their complexities vary by a factor of log n.

The naive one is the O(n^2) one that searches everything. No need to mention it~

The better one has the complexity of O(n log n). Once I got enough hints about this algorithm I realize a very important concept that every programmer must know. That's, you should choose an algorithm that takes advantage of the data structure you're playing around with, such as:

Sorted => Binary search

This is probably the fundamental property of algorithms in CS and I cannot emphasize more! Think about how many algorithm we use to sort! (Bubble sort, mergesort, heapsort, quicksort, and something called radix sort that I have never been taught about!) The reason is that once we sort the data structure, we can use BS to find the element in O(log n) time! Isn't it beautiful?

By this time it's not hard to see where this O(n log n) algorithm comes from (we have n rows)! But I had this quirky feeling that it could be solve in O(n) so I asked for more hints and my interviewer was find enough to ask me to start at the top-right element, and he poked me around enough to make me realize that by elimination I can create an algorithm that will have in maximum 2n times. Once I realized it, I started chewing out C code and the interview poked around the algorithm for more but I finished in time. Mission accomplished.

Well, not exactly. Towards the end of the interview I asked if this was the most efficient algorithm. He started telling me this story.

One day, he was asked by his colleague about this question. His colleague told him about this problem and concluded that the most efficient algorithm is the start-from-top-right one! He looked at it and said, "No". In fact, if you start from the middle of the matrix, you can at least eliminate 1/4 of all elements in each step in a divide-and-conquer technique! This algorithm in fact give a log^2 n complexity! As a comfort note, he told me that the code is actually pretty complex and he did not expect most interviewees to get it.

Two lessons to learn:

i. The property of the data structure can give you the important clue for your algorithm
ii. There's always someone out there who's smarter than me so be humble!

Wow, this is a long entry. And I was going to write the rest at once! Well I can since I've nothing better to do on my flight from SJ to Dallas, but then my creativityd dwindles and I cannot write something more interesting. Better stop now and maybe eat some snacks first.