Thursday, November 23, 2006

A rant at Schulich library

According to Webster dictionary, useful means:

1 capable of being put to use or account <useful suggestions for limiting the amount of food we eat> -- see PRACTICAL 1
2 capable of or suitable for being used for a particular purpose

suggested example: McGill Schulich library is NOT useful.

why did I say that?

I was expected to complete an Autosuggest component for my work using Ajax. But for two days I was banging my head against the monitor because the problem seems more complicated than I initially thought, and of course I'm no Javascript guru. I decided that I would take a tour at Schulich to find the appropriate book that can arm me and let me finish the work once and for all.

I founded the Javascript section and searched through all the book dated after 2003, in the glossary for Ajax, (since not many people understand Ajax probably until 2003).

You know what, there's only 3-5 books dated after 2003 out of around 30 books there, and NONE mentioned the word Ajax or XML throughout its content!

So all the students at McGill, if they want to become the next Javascript guru or become a web entrepreneur, like reddit, digg, or flickr, will be armed with pre-AJAX technology! I guess this will get them a job at... hmm... a web developer at... (You cannot believe how outdated the site is...)

It's interesting when I was walking around the CS section through.... it's filled with a lot of SE and C++ books that probably no one would read... or the "Introduction to Program Analysis" for those (may it imply 0) who are (probably is) interested~ I also came across the Gunnerson's A Programmer's Introduction to C#. 2 of them actually! One for the 1st edition and one for the 2nd edition, dated one year apart. I'm now real impressed with McGill's swift and bold adoption of technology! However, I doubt many read it, considering that no classes are offered in C# here.

And it must make Mr Gunnerson a rich man! That book was alright but didn't delve much into the .NET and i remembered in my intern days that I actually had to use the Andrew Troelsen's C# and the .NET Platform instead.

I wonder how much tuition money we actually spent in buying those books? Are they screened by a computer literate or just some brain-dead librarians? Had they ask one of the SOCS prog I'm sure the quality would be much higher.

Hopefully I wouldn't get kicked out from McGill for post this :P

Sunday, November 19, 2006

The tale of two interviews, Part I

As you all know (even though 'all' implies singular or none here), I am graduating soon from my degree soon but I wasn't actively search for jobs yet. I was still planning to go back to HK after graduation. Hazel is still in HK and I don't want to part with her for too long. However, every CS grad has his/her own dream job and during the early October when companies came to McGill to advertise about their employment, I decided to apply for two companies. I asked my friend Albert for his resume, since he got his dream job already and I thought his resume must be impressive enough to push him pass the resume screen! I spent around an afternoon, doing nothing but reformatting my resume.

Two weeks later, I was blessed enough to receive the phone interviews from both companies. I made some mistakes, but I guess not yet enough for them to screen me out. I received the invitation for in-person interviews from both places, around one week apart. As of today, I am just on my way back from the interview from the second company! I don't know the result yet, but in any case I feel blessed to have these opportunities and the purpose of this blog isn't about me boasting anyway. What I really want to document is the experience from both interviews and the impression that I was left, how it would have impact my choice if I had the offer from both places.

First I'm going to talk about company A.

My impression of company A was that everything was taken care of. Upon receiving the invitation, it asked me to choose the date and time among the available days. I chose my date and one day later it emailed my the itinerary of my flights and the accommodation! It was also kind enough to let me choose to use taxi or rental car! More impressively, it would reimburse me of ALL meal and transportation expenses I incurred during my stay!

However, for some reasons the interview was held not in its headquarter, but in a closer-by Canadian city called Vancouver! Maybe this would produce less visa problem? I wondered... Turned out it wasn't true most interviewees I met during the interview period were canadians. Personally, I prefer Vancouver since I have some very good friends there and I could also tour the city, and later in fact I got to meet my parents as they were also on the way back to Edmonton! So personally, it was very good for me and I wonder if it attributed to the Lord since He let me meet my parents after my grandpa's funeral. Truly I was thankful...

But this doesn't have its implications either, and allow me to suspend it for a while.

So I arrived Vancouver, lodged at one of the best hotels in town, and slept on a king-sized bed in the first time of my life. I need not to worry about the expense cuz' Bill is paying my bill! All the gratitude to him! That night I drove to Richmond and met my friends, had my meals. I was having a blast!

Then came the interview the next day.

I woke up at around 6:30 am that morning cuz' the interview was held at UBC and I was supposed to arrive at 8:30. I arrived half an hour early, toured UBC a bit, ate my breakfast, and got ready to rock-and-roll.

As I arrived at the career centre at uBC, I discovered that there were 4 other people being interviewed in this morning section. Each of us would have three individual interviews with some of the top SEs in the world, and by the end of the session they would let us know if we got hired or not.

You can probably see that the pressure rose instantly! Dead-of-alive in 3 hrs! Better not screwed up! And then five nervous souls were led to rooms and started the duels.

Let me conclude that I had my ups and downs. The first two went alright, but the last one (about testing) really killed me and by Joel Spolsky's standard, my fate looked grim. However, the most grueling moments were between the interviews. You know, some of us came out early, some finished late. You could see our nervous faces though, and it's most unnerving when some guy stayed a lot longer than you did and you wonder if you looked so unintelligent that they threw you out early. Generally we had around 10 min before we went into the next round, but then it meant we had to stare at each other for 10 min! We tried to steer the conversation away from the interview questions to lighten our mood! But you could see that everyone wished this 10 min could pass by ASAP.

I could remember another annoying thing they told us in the beginning. We were told that this interview round was pretty successful! Out of 30 candidates they interviewed 11 got the offers! Wow! What a great news to know! 1/3 of survival rate! Only 1-2 out of us 5 would be the offer and the rest would go back to our hotel room, lie on our king-size bed, and ponder for the rest of the trip what on earth I did wrong such that I was deemed unqualified. You could see the tension on our faces during those breaks. We were NOT comfortable.

In retrospect, maybe it was a way to generate pressure in between such that they could measure how well our brain operate under those circumstances. Wait till one day when I sit on the other side of the table and I can tell you :)

Anyway, each of us completed 3 interviewed, and we were asked to sit outside to wait for the final result. By that time we knew the "moment" was coming and we were out of topic to converse anyway so we kept our silence.

Then, the main recruiter came out, and asked the guy from SFU go have a one-on-one. And the rest of us waited.

5 minutes passed by...

Then 10 minutes...


I guess each of us wonder why did that guy take so long! The only reasonable explanation was, maybe he got an offer! Or else they would've just say "Thank you very much and you did an excellent job, but currently we cannot find an appropriate position that suits your skills. We will keep your file and may notify you in the future if there's a suitable position"!. But tt was around that th 20 min mark that someone finally broke out this thought, and I was sure each of us started panicking. One got hired already! That left 0-1 spaces left! Oh no I'm toasted~! It was a long 20 min.

However, I never got to know who else got hired. I was the second one called into the room and because I bombed my third interview, they decided to hold a fourth interview to try me out! I had that, and when I came out all others were gone. Again they asked me to wait and by then the afternoon session had started already (and they got delayed for at least an hour because of us! Poor souls~) Finally as I was waiting I met one guy, the Concordia guy who was the least conspicuous of us all and he told me that he got an offer! Of course he comforted me that I would probably get an offer but I wasn't so sure. Eventually the second group went in as well and I was left alone again, and waited for another 15 min until the recruiter called me into a separate room to break me the news.

Now for those who know me, most of you would know about my fate, and again I must thank you all for your prayers :)

I haven't finished yet though... let me eat my dinner with Albert the Googler first, and finish part 2.

To be continued~

Saturday, November 18, 2006

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!


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.