Linked Lists

I had five interviews on Tuesday and one today (Wednesday).  I’ll refrain from talking about them at this point because I’ve decided that discussing the interviews before I’ve been ranked or I’ve made my rankings is probably unwise.  Despite this, I want to discuss a programming question I was asked:

Given a singly linked list, in sorted order, how do you remove duplicates?

During the interview I brain-farted because I forgot that the list was sorted, so I suggested a horrible solution involving keeping another linked list of all unique elements that had appeared and then checking each new element in the original list to see if it appeared in the second.  Clearly, this algorithm has a O(n^2) run time, and O(n) memory usage (I think?).  If I had remembered the list was sorted, I would have suggested simply keeping a copy of the previous element as you advance in the list, and removing the current element if it is the same as the previous.

Maybe it’s my inexperience with these kind of interview questions, but it seems like most of them have a little “trick” to them, and you either get it or you don’t.  If you do get it, great, but if not, well you might not get the job.  Once the interviewer points out the correct method, it often seems obvious.  I understand this is testing whether the candidate understands programming intuitively, but that doesn’t mean the candidate is actually a good software engineer.  I’d explain what I mean here, but I’m hungry… and I might be wrong.

In conclusion, I’m bitter that I fumbled at an interview

EDIT: Karan suggested this solution that removes the next element if it’s the same as the current one.

CUSEC Part Two: Karan’s Warning

I’ve returned to Waterloo from CUSEC.  On Friday, Noah Sugarman and I presented findthehotties.com to the CUSEC democamp.  We were a big hit, but unfortunately, we were hacked by three seperate groups within minutes of finishing the presentation.  Two of the groups personally contacted me with suggestions on how to improve security; of that I’m grateful.  I was surprised when I found out our game was hacked, although, I should have expected it. Firstly, we gave the presentation to a bunch of software engineers, and secondly, my dear friend Karan had warned me that we were doing server validation horribly wrong.  He was 100% correct.

Unfortunately, Noah and I could not fix the site because the hotel took away our internet access for going over our bandwidth limit. (Note: Never stay at a Best-Western).  Today, we finally got the site working again, this time with marginally better security.  To make the site properly secure, we need to do a major overhawl, but that will have to wait because we are both very busy making up school work, preparing for exams, and attending job interviews.

So far, I have five interviews lined up for the coming week.  Finally, I left my fridge open while I was at the conference.  This is most unfortuate because I’d just bought three bags of fresh milk.  Oh well, Murphy’s law, right?

Am I Sacrificing my Integrity?

A couple of days ago, my dear friend Karan shared with me an idea about making a CAPTCHA that forced the user to choose amongst the photos of several women and identify the attractive one. This is a decent CAPTCHA algorithm because bots would be hard-pressed to know what an attractive women looks like in order to defeat it. Karan was being facetious, but the idea intrigued me. It quickly became apparent that it could never be a particuarly effective CAPTCHA because of the limitation of the number of pictures that could be reasonably displayed at once. For example, if nine pictures are shown, a bot has a one-ninth chance of guessing the correct image, which is far higher than for traditional text-based CAPTCHAs.

But, I was not to be deterred. Instead of a CAPTCHA, I along with my friend Noah decided to make a high quality flash game based on the concept of picking out the one “hot chick” from a set of 9 images. The faster you pick the right image, the more points you get. I went and registered a domain, and setup a server. We are currently polishing and improving the game, but you can see our progress at findthehotties.com.

The question is, “Am I losing my integrity by creating the game?” I view it as harmless fun, but maybe others would view at sexist, and degrading. To counteract that, we’ve decided to make a male version as well. If people are really opposed to it, we’ll take it down. Have I gone to far?