LeeMobile

Google Code Jam Round 1

Well, this weekend was round 1 of the Google Code Jam, and unfortunately I did not advance to the second round.  I’m actually really disappointed in myself.  Not because I had high hopes of making it far, but that I *could have* advanced if I had just paid more attention and focused.

I wouldn’t be disappointed if I felt that I had my ass handed to me, but I slipped up on fairly rookie and stupid mistakes.

In all fairness though,  I was beat squarely in my inability to recognize where I went wrong within the two hour time limit.  Given that I had two chances to redeem myself (you’re allowed to compete twice out of the three time slots), I should have made it passed this round.

At any rate, I learned a lot of lessons which will be hard to forget for next time :-).  I still enjoyed the experience, and I’ll probably sign up for Top Coder, a programming competition league which holds frequent competitions.  I could see myself doing this every few months or so just for shits and giggles.

For those interested, here are the questions I attempted to solve, and where I went wrong:

The format is that you are presented with 3 questions.  To solve the question, you write a program which takes in the input data set, and you submit the output for verification.   There are two input data sets, a small one and a large one, with the large one worth more points.  Each question is worth different points (depending on level of difficulty), and those with the most points advance.  If there’s a tie in points, then those who submit earliest advance.

Had I solved any one of these problems I would have advanced to the next round.

The three questions I attempted to solve in both slots this round were:

First attempt:

Question 1:

Problem

You are given two vectors v₁=(x₁,x₂,…,x_n) and v₂=(y₁,y₂,…,y_n). The scalar product of these vectors is a single number, calculated as x₁y₁+x₂y₂+…+x_ny_n.

Suppose you are allowed to permute the coordinates of each vector as you wish. Choose two permutations such that the scalar product of your two new vectors is the smallest possible, and output that minimum scalar product.

I chose this question because it was obviously easy.  You just have to sort one vector from largest to smallest, and the other vector oppositely.  Fast and easy problem to code, so I submitted a solution pretty quickly and was already ahead of the pack. Someone was able to read the problem, solve it, code a solution, download the data set, and submit the data set in 3 minutes time… now that is FAST.  I wasn’t that fast, but I was quite ahead.

The large data sets are verified after the competition is over, so you have no way of knowing if it’s valid until the end.  You also get only one shot at it too. In all my hubris, I ran the large data set and submitted.

I found out that my large set was incorrect, and I quickly realized the costly mistake.  The large data set contains values in the vector that are between -1000000 and 1000000.  And in my solution I used a 32 bit integer to calculate the values, which would lead to an overflow since it can’t represent a number like 1000000 x 1000000 (those tricky bastards at Google!).  Had I simply just used a 64 bit integer it would’ve worked out, and I would’ve scored enough points to advance.

Lesson learned… read the bounds more carefully.

Question 2:

 Problem

In this problem, you have to find the last three digits before the decimal point for the number (3 + √5)ⁿ.

For example, when n = 5, (3 + √5)⁵ = 3935.73982… The answer is 935.

For n = 2, (3 + √5)² = 27.4164079… The answer is 027.

This question was weighted heavily enough that if I got just the small data set to work correctly, I would have had enough to pass.  But no, I didn’t solve it correctly either.

My naive solution, because my math skills suck, was to just compute the value and parse the value for the answer.  For the small dataset, the maximum bound on n is 30… so computation should be enough for a correct answer.  There was no way that I would attempt the large, as n had a max of 2000000000 (that’s a shitload of zeroes).  Sounds simple enough, but how do you compute such a huge number with enough precision.  Precision is at the heart of the problem.  So I used Java’s BigDecimal data type, which is really accurate.

However, to get the square root of 5, I initially calculated it using the Math.sqrt() Java function before wrapping it in BigDecimal…. and there was my big mistake.  Math.sqrt returns a double precision float… and when n starts to get large that’s simply not precise enough.

What I should’ve done was use the Newton-Raphson method to calculate the square root of 5 with enough precision to solve the question.  Just solving the small data set alone would’ve been enough to push me through.

My mistake again was another data type error.  That and not remembering a few years back into my numerical methods class about the Newton-Raphson method…. because every person should know it off by heart.  How could you not?!

I won’t bore you with more details about the third problem which I failed at… but it was one where I screwed up by not reading thoroughly enough (I missed a vital constraint).  *Had I* solved it, it would’ve pushed me into the top 100 and I would’ve made it to Round 2 (sigh).

–

So all in all I felt like a newb this weekend.  Shitty in that I could have moved on if I just paid a little more attention to detail and read the questions more thoroughly.  I also felt really rushed and under the gun, so that really clouded my judgment.  All I had to do was take a deep breath and chill out… the answers would have come right to me.

I learned a few lessons though.  Mainly that my math skills suck and that I should maybe re-read some of my old numerical methods and calculus text books.  Also, I should just pay more attention to details. I think that’s more important than anything.

Oh well, there’s always next year.

Posted in Uncategorized | 1 Comment »

Google Code Jam

So I’ve made it past the qualifier round of the Google Code Jam.

The Code Jam is an annual programming competition where the top contestants win cash prizes and a free trip to the Google headquarters in California.  The first place prize is $10000 and 10 free lunches at Google, although the true prize is a job offer from Google.  If anything, it’s a great way for Google to hire the best and the brightest.

I’m taking part in it not necessarily for the job, as I don’t have any plans on leaving Ottawa anytime soon.  But I’m jumping myself here, as the probability of me getting far in this contest is pretty remote.  For one thing, I haven’t trained or practiced for this competition, and I haven’t really competed all that often.

This will be my second ever programming competition.  I did participate in one back in third year University.  I was actually happy on how well I did that time, as my partner and I were short a team member (we didn’t know you could have 3 members per team) and we were also short reference material (you were allowed to bring your textbooks).  We ended up placing 6th in Alberta, and like 16th in the national pool.  It sounds bad, but that beat my expectations as we were up against Masters and 4th year students.  We also didn’t know what to expect and hadn’t prepared at all.

That’s the thing about programming contests.  It’s that they ask a specific type of question which does require some preparation and training for to do well.  Most of the time the types of problems presented are heavy on the algorithms and math side, the kind of problem solving that take up only 5% of your time in real world everyday programming situations.  However, it’s the most critical and interesting (to me anyways) part of programming.  Much like having a broad chess opening repertoire, it’s also good to have a broad understanding of various algorithms.  And much like chess, it’s something that you don’t achieve simply through practice.

So, my whole point is that having not prepared for the Google Code Jam, I totally have low expectations of how well I do.  I actually don’t even think I’ll make it past the first round.  The qualifiers were pretty easy and a basic screen for competency.  I really don’t expect to make it past the first round.

But I’m not doing it to win prize money or get a job offer.  I think I’m taking part in it because I enjoy the challenge, and the pressure it puts on me to be on my toes.  It’s also a good way to keep sharp and use my critical thinking skills.  It’s easy to solve problems at work when there’s no hard time constraint, but in thick of competition against the clock and other competitors, it really demands you to be sharper.

I’ve actually found this whole experience to be even more enjoyable now that I’ve convinced a few of my programming friends to take part too.  My geek friend Pat, who I’ve enjoyed many geeky programming language debates with, has made it past the qualifiers too.  The competition itself is performed on an individual basis, but it’s somehow re-assuring to know that I’ve got a friend who’s feeling the pain and pleasure of competing.

Hopefully I’ll do better than expected for round one this coming weekend.

Posted in Uncategorized | No Comments »

Car Hunting

So it’s about time that I owned my very own vehicle.  You know, being a broke student for years on end didn’t really help in that endeavour while I was going through school.  And the usual routine is that for most people, parents are the ones who help you buy your own car when you’re young.  I grew up in a pretty poor family, so that didn’t really work for me as my folks could barely afford to keep the rusty old family car running.

Now that I’m all out of school I can actually for once afford my own set of wheels.  It’s exciting!

Anyways, Renata and I went out car shopping and I had my heart set on getting a Toyota Camry.  There’s just something so roomy and comfortable about Camry’s, and with my first test drive I fell in love with it.  I know it’s odd… you’d think I’d get something sportier and such.

In the winters Renata’s folks hibernate in Arizona, so I get to use her Mom’s Civic SI.  It’s sporty, can accelerate pretty hard (198 horses for a such a small car), and you can feel every bump and knick on the road.  But, I think I’ve opted for the calming and smooth effect rather than the speedy sportster.  Yes, I’m getting old and more boring.

As I was saying, we were out car shopping and I learned a few things.  For one, I should just shut up and let Renata do all the bargaining.  I’m a terrible haggler, and Renata is a born salesperson.  So she knows all their tricks, and knows how to play the game herself.

The whole process took 6 hours, as we hit up 3 different Toyota Dealerships that day.  We met a variety of sales people, with different bargaining strategies and sales pitches.  Some were more pleasant to deal with than others, and all reacted differently to our bargaining.

The first dealership, Tony Graham Toyota, had really nice sales-people.  But they were shielded from bargaining with a sales process where they had to ask their manager for every bargain.  I’m not sure if it was a sales “ploy” where they made us stew while they asked their managers for a price, but it got annoying pretty fast.  They gave us a decent discount, $2700 off of the MSRP, but we wanted to at least shop around some more to see who can offer us better deals.

We swung by Mendes Toyota, and I kid you not I’ve been to hole-in-the-wall pho shops that have a larger room.  Their show room fit like 3 cars, and with 4 or 5 other customers there it felt like a packed house.  Anyways, a sleazy car salesman handled us and didn’t even budge.  Basically, he offered us the retail price, and that was it.  Of course, it got escalated to his manager, and we dealt with him in his rickety old office.  After a lot of hemming and hawing and talking, we got an improved deal.  He showed us his “books”, and the cost of each car and his profit margins.  $3000 off he offered.  Not bad… but the place felt pretty sleazy.

Apparently Toyota’s have very narrow margins (of course, it’s their services that pull in the majority of their profit for dealerships), so we couldn’t get it much lower than that.  At least we knew what the costs of each car was.  He could’ve fabricated the numbers, but they seemed about right from all our haggling.

Finally, we showed up at Bel-Air Toyota at a 4 PM on a Saturday… last day of their work week, and it looked like they were having a slow day.  Bingo!  The sales guy was pretty nice, and he wanted to push a car out as seamlessly as possible.  We settled on the $3k discount, plus some packages and so on.  We got what we wanted, a Toyota Camry that came to $20400.  Apparently Toyota lowered Camry costs down about $4k from the 2008 models, so we got a really good deal.

At the end of the day, I felt like a sleazy car dealer from all the bargaining.  I am not a good bargainer, but at least now I’ve learned how to play a little hard ball.  It makes me think twice every time I buy something, that you can usually get things a little less than the listed price.  I know… I’m so naive.

So, I’m now the happy owner of a brand new ‘09 Camry.  That new smell always gives me a tingly sensation.  Perhaps it’s the formaldehyde in the new upholstery, but I’m pretty happy with my purchase

Posted in Uncategorized | No Comments »

Fire Sale

Huge huge savings going on right now!  That’s right, you too can own a piece of corporate America at 20%, 30%, even 40% off the normal going price!

That’s right folks,  the economy is giving us amazing deals on stock prices right now, and the prices keep dropping!

How things have changed so quickly in such a short period of time.  I remember back in April and May picking up a bunch of stocks.  Things were cheap, and it looked like a great time to buy in.  In only two months time, things have slid far below what I imagined.

With the price of oil spiking up and reaching almost $150 per barrel, and the financial sector doing a nose dive, the American stock markets have been taking a severe beating.  I’m just glad that I didn’t get in earlier than I did, but I am starting to feel the pain.

It’s nothing that I’m awfully worried about though, as it’s just one of those cyclical things.  The markets will eventually come back and rebound, it’s just a matter of waiting out the storm.  Having said that, my stock picks are still holding out pretty well and I’m “beating the market” so to speak… even if that does mean that I’m now in the red.

I think I have the worst sense of timing though.  If I only would be patient and wait out the nastiness that was forecasted, I’d be making a killing on the current fire sale on the stock market.  Today, the S&P 500 is trading below what it was 2 years ago!

For anyone sitting on a pile of cash right now, the opportunity to buy ridiculously cheap stocks is coming soon.  Hell, you could buy a ton of random stocks today and look like an absolute genius in a year or two.

Buy low and sell high, that’s all there is to it.  Oh, that and not panicking :-).

Posted in Uncategorized | No Comments »

Moving On

Well, it’s been a good 13 month run with Waypoint (www.waypointinfo.com) but it’s about that time to move on to another job.

On Monday, I started my new job at Rove Mobile (www.rovemobile.com).  They’re situated right in the middle of the Byward Market, so it’ll be a fun environment to work in.  It’s a bit of a commute, but hopefully it’ll be worth it.  It is definitely a nice change from the isolation from my previous office.  I do believe that your environment can stimulate you in many ways.

A career in software development is unlike a lot of jobs.  It’s a career where you change jobs often.  Of course, there are a few exceptions such as running your own company, working in a very large corporation, or in the government.  Even then, there are always stories of Microsoft employees and Googlites switching jobs quickly too.  Yours truly left the federal government to enter the private sector.  I personally think moving around is healthy, albeit at the cost of job security and a fat pension.

I guess it comes down to the nature of work in software development. It’s a job where you do problem-solving on a daily basis. It requires that developers are always on their feet, ready to adapt and solve various problems that are thrown at them.  That’s why I’m in it, because I wanted a career where I wouldn’t have to continually “grind” over the same thing.  The unfortunate side effect is that when we’re not challenged, developers quickly become bored and leave.

–

Life at Waypoint had its ups and downs, like any company.  The people there were great, and the atmosphere was casual.  However, for a small startup I didn’t feel like I was part of a focused and cohesive team. I think that’s an essential ingredient for succes, because it’s too costly to be inefficient when you’re small.

Compensation was a sticking point too. Right now there are just way too many jobs and too few quality developers.  Hell, in this market you don’t need to be great to find work, just simply being decent will get you pretty far.  It’s the simple case of supply and demand, and the supply is really small and the demand keeps on growing.

Salaries are rising each year, and I was forgoing a bit in the hopes of getting into a company early on.  For me to stay any longer, I would’ve had needed to be convinced that there was a better chance for great success.  It couldn’t just be average success, or mediocre success, because that’s all too easy to find in a city like Ottawa.  It had to be worth the opportunity cost.

I learned a lot of things there at Waypoint, and met some really good people.  I’ve never felt as confident about my skills, and I attribute that to my experience with the company.  I wish I could have stayed longer, but it was about time I had to go.

–

Anyways, enough with the negative news.  The positive news is that three days in with Rove Mobile I’m pretty happy and assured that I made the right choice to switch.  I get a pretty good set of benefits and a pay bump.  More importantly, I’m part of a more energetic and vibrant work environment.  There is a greater sense of focus, and they seem to be much more agile and current in an industry that is always changing.  The people are pretty friendly, and though the commute is a little longer it’s nice to see crowds of miscellaneous people again.  I’m already holed up in Barhaven, so it’s nice to get out.

The working environment really helps too.  I get a pretty nice desk, dual screens, and the company has invested in a lot of Herman Miller Mirra office chairs.  If anyone remembers the dot com bubble, those $1000 chairs used to be the icon of startups.  I even got my own box of business cards!  I’ve never had business cards before.  I must be moving on up.

Anyways, things change and life goes on.  Things seem really good at my new job so far, I hope things stay that way.

Posted in Uncategorized | No Comments »