Wednesday, January 18, 2012

I feel like a dork

Biggest mistake ever. The other day I was doing a Facebook engineering puzzle using C++, and the puzzle description warned about performance and how important it would be to go through a large amount of data real fast. Before I go any further into that, let’s talk about Project MADA. The now defunct ho ha of mine.

When I was doing the project back into university, I had to look up bi grams within a large amount of text. Essentially I had to keep running tab of all possible combinations of two letters {aa,ab,ac,ad….zw,zx,zy,zz}. That’s 2^26 combinations.

My solution to this problem turned out to be, a list, where I would store each bi gram along with its corresponding count as a tuple. Thus, for each bi gram I read into the system, I would go through the list to see if I had a mach. If yes, I would increment the count by 1 and if not, I’d add the new bi gram along with a corresponding count of 1.

Back to the Facebook problem, which is liar liar. There’s a forum of users and you have a list of people who have come frward to name the others as liars or truthful. From this knowledge, you have to derive who is truly truthful and who is just a big fat liar. The logic for this is a no brainer. The implementation however requires keeping a track of number of accusations corresponding to a name. Now I could have used by bi gram method, but for some reason, just because I was doing a Facebook puzzle, all that was in my head was efficiency. And my first thought was, hash table (Map in C++) where the key would be the person’s name.

Two days later I was thinking of my FYP, and I just realized how stupid I must have sounded coming up with my method to insert stuff into a list and keep track of it when the hash table was there along for me to use. Instead I had an implementation which was utterly inefficient, (nested for loop, traversing through list each time to find element. Talk about a worst case) and what’s worse, I feel like a dork because I stood in front of my lecturers proudly showing off my implementation as it was the best thing since peanut butter and jelly. I can’t even believe the hash table didn’t occur to me.

I can’t help but wonder, if they thought I was a bit of a dud for not using a hash table. Sigh.

On a side note, it truly is amazing just how differently I thought simply because the thought of Facebook efficiency was in my head the whole time.

No comments:

Post a Comment