The Google India Code Jam final round was held in Bangalore last Saturday. Among the fifty finalists, there were a good number of contestants who had been flown in from Singapore. Most of the finalist were students. The contest was held in two Reliance Webworlds in Cunningham road and CMH road. This time the problems were tougher than those in the qualifiers, though the time limit was increased to two hours. The first problem was related to web crawling. You are given a list of URLs that the crawler traversed first. The second list contains URLs crawled from the pages in the first list. Each URL would be preceded by an index into the page in the first list. These URLs would be relative to the URLs in the first list (can contain ../). A third list contained URLs found in pages in the second list. The aim was to find the total number of unique pages in the list. This took some time to finish.
The second problem involved finding the path with the shortest number of turns between two points in a 500x500 matrix. All the roads in the matrix were specified by their start and end coordinates. This problem was far too tedious to attempt in the remaining time. One had to find all the intersections of the roads and construct a graph. After determining the edges on which the points lay you had to find all possible paths between the two points and get the one with the minimum turns. In case two paths had the same number of turns, there was a crazy sorting criterion for resolving the order. I wasted some time on this before giving up and moving to the next problem.
The last problem was a battle game. You are given a certain number of armies in your territory. Your opponent has three territories and the number of armies in those territories is also given. When you attack any of your opponent's territories, there are probabilities for 2 to 3 possible outcomes (you lose 2 armies, he loses none, both lose one and so on). If you win a territory, you need to post one of your armies in the territory before attacking the next one. Depending on the sequence of the attack, the probability of winning would change. The aim was to determine probability of the best winning strategy. I coded up a solution with a recursive algorithm to this one, but it was far too buggy. I ran out of time while debugging it. No regrets though since I'm not sure if the algo would have worked even if all the bugs were thrashed out.
Luckily for me, there were hardly any submissions for the second and third problems. Based on the submission time for the first problem, I was at the 16th position. After the contest ended at 1:30, everyone went to the Google office for lunch and technical talks. Lunch was good and the tech talks were interesting. The first talk was about the page rank algorithm. Spammers are always coming up with ways to get the Googlebot to rank them higher and Google is always looking at ways to counter their moves through changes in their page ranking system. The next talk was about the massive Google cluster and their cluster file system. I think they did a good job of convincing everyone that Google is the place to be in if you want to do interesting work in computer science.
The awards ceremony was next. I was relieved to know I had retained the 16th position after the system tests. That means a cheque for 25 K (minus the taxman's share :( ). There was a dinner in the evening at the Taj where I got to chat with some of the other contestants and the hosts.
It was a great experience. Google intends to interview finalists who are interested in a job with them. I have declined the interview for now.
No comments:
Post a Comment