UPDATE: I got an email saying that I passed the interviews, and now waiting to be matched to a project.

Today I had the chance to interview with Google. It was a unique experience, and worth blogging about.

Application

I started applying for summer internships towards the middle of February. But it turns out this is too late to apply for some companies, Google was at the late stages of interviews too. So to make sure that you get the best experience, start applying right after you have results from the Fall-Winter semester.

If there’s a possibility to get a recommendation from within Google, that would increase the chance of your resume getting a good look.

Response & Preparation

I got a response from my recruiter within 2 weeks, and she asked me for my schedule, and we set up the days for the interview. After that I had to fill in a questionnaire, sign a NDA, and fill up some other forms.

They ask you about the programming language(s) that you want to use for the interview. I said C++/Java, whatever language you select, make sure you know everything about it, because the questions can be from non-obvious parts, which you never thought was important.

For preparation, Steve Yegge has two posts regarding this. I highly recommend reading them.

I borrowed Introduction to Algorithms by CLRS from the library, and read through it to refresh my memory. The next thing was to do questions in the practice rooms at TopCoder. This would really help you get your problem solving skills polished.

Doing practice problems in other websites, such as Codeforces or UVa judge also helps a lot. But I found working on TopCoder questions to be more convenient. Because I told them that I know both Java and C++, I did TopCoder problems in Java, and Codeforces problems in C++.

Actual Interview

I was very nervous while waiting for my interviewer to call me, I had Google Docs open. They give you a link to a shared document, where you can type in code for the interviewer to see.

The nervous stage lasted halfway through the first interview, and by the end of it I was in good form. The first interviewer was from the Google Search Quality team, and his questions were more focused on optimizations. I found this interview to be hard, partly because this was the first interview I’ve had. Luckily I was able to answer all the questions correctly, within the given time.

Second interview was from an engineer with the Google Plus team, first half of the interview was writing a C program with lots of edge cases. I missed one edge case, but he was happy because I finished the program in 5 minutes, and only missed one case. From what he said, I performed better than many others.

After that I had to answer an algorithmic question, something similar to what you get on TopCoder, I got the solution to that pretty fast too, again he was happy with it. There were few more questions and the whole interview was done in 30 minutes. We spent the rest of the interview talking about life at Google, and he answered the questions I had about Google.

There were few incidents, including Sergey Brin going by my interviewer on roller-blades, wearing a pink helmet, and my interviewer promptly informed me about it.

I am very happy with how it went, and awaiting feedback from my recruiter.

During the past few days I have been trying out some random stuff with Slick2D. I used Slick2D for my last game and I thought that it was amazing at what it does. It doesn’t get in my way of coding, it just helps you while you keep coding.

I’ve been reading Ziggy’s blog and he has talked about Artemis Entity Framework. Instead of having an Object Oriented approach at creating your entities (player, creeps, etc.) you have components and systems. I won’t go on explaining it in this post, you can read about it here.

• http://piemaster.net/2011/07/entity-component-artemis/

Artemis framework is a very clever framework. When you start writing a game using that, you do feel that it is very extensible. But the only problem is that it’s too much work when just getting started. If you are only creating a small scale game, then you are better off with the good old OO approach. Unfortunately it took me 2-3 days of messing around plus a thread on Slick Forums to realize that.

What’s good about using Artemis ?

Your code would be very neat, and organized. Game data is handled by components and logic is handled by systems. Very little confusion, after you get yourself familiar with it (After reading through the source of their example game - Star Warrior.

What alternatives do I have ?

MarteEngine. This is a framework built on top of Slick2D. Created by Gornova at RandomTower.

Although still a work in progress, and aimed at beginners. It gives you lots of utilities, and a nice way to organize your code, without getting on our nerves all the time. For me it just took 30 minutes of going through their wiki, and reading the source of the awesome game Fuzzy, by Gornova. To get familiar with it.

What I like about the MarteEngine.

For your characters, you can create an object of their Entity class. Or you can extend their Entity class to create your own character.

Here’s an example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

public class Hero extends Entity {

  private Image image;
  private float velocityX = 5.0f;

  public Hero(float x, float y) {
    super(x, y);
    image = new Image("hero.png");
    this.setGraphic(image);

    // Controllers
    this.define("RIGHT", Input.KEY_RIGHT);
    this.define("LEFT", Input.KEY_LEFT);
  }

  @Override
  public void update(GameContainer container, int delta) throws SlickException {
    super.update(container, delta);

    if(check("RIGHT")) {
      x += velocityX;
    }
    if(check("LEFT")) {
      x -= velocityX;
    }
  }

As you can see, the update logic for that entity is in it’s own class. And easy to manage. This code can be further extended to support collision / gravity and various other things.

MarteEngine has a built in collision detection system, and you can use it. But if you decide not to use it, you can use your own system. Basically it’s up to you to decide.

A quick “game” developed to test MarteEngine.

Home made graphics, using Inkscape

EDIT: Turned out to be more than just a test. Legless Runner is now available at https://github.com/yasithv/Legless-Runner.

I hope to compete for the 22nd Ludum Dare using Slick2D and MarteEngine, and I will write a development blog post about the experience.

I got a chance to attend my first Hackathon in Toronto, last month. It was organized by Random Hacks of Kindness

This was in downtown Toronto, not on my campus, so it was also a nice opportunity for some sight seeing. As it was also a very nice experience for me, I decided to make a post about it.

I was expecting to walk into a room full of people, but when I arrived I was the only one. After an hour or two, we were ready to begin. Still there were only 5 people including me. 3 coders and 2 designers.

What we decided to build was a platform where people in rural areas in Canada (apparently there are places where getting good quality drinking water is hard) can report about their issues with water.

After eating lots of muffins and bagels, we had a rough plan of what we were about to do. This is when the learning began.

Lesson 1 - Don’t re-invent the wheel

You don’t have to code everything from scratch, there are libraries, better yet-frameworks. Which people have built and tested through some time. So before you start coding something, analyze your needs and search for libraries/frameworks that can help you with it.

Lesson 2 - Licenses

Not every code found on the internet can be used like we want to. Make sure that you check the license of the library you are going to use, and that it is allowed to be used for the purposes of your application, before adding that library to your code base. Also see what the conditions of the license is.

I used a wrapper for some database access, which had an ambiguous license. So I had to redo it with some other code.

Lesson 3 - Consider what’s appropriate and what’s not

We have decided to call our site, “My Water Sucks”. But we were also going to forward detailed reports of water issues to politicians in the affected area, in a weekly log. Depending on the people you are trying to work with, some things might not be appropriate. It was finally decided that, because we wanted to be taken seriously, we should not use “sucks”. It was changed to “Water Voices”.

Lesson 4 - You don’t have to be there (always)

After coming back from downtown Toronto to Mississauga on the first day of the Hackathon, I did not feel like I want to experience the slower-than-a-dying-turtle-slow afternoon traffic from Toronto to Mississauga again.

Solution: I decided to contribute online. After all we were using github, when we were physically there. So why can’t I just commit my contributions from home. I was happily home, and contributing to the project at the same time. We kept the conversations going through IRC.

Also one of the most awesome things about attending an event like this, is that you get to know a lot of awesome people. And someday that would be really useful. And you do learn a lot from those people too.

Floyd-Warshall all pairs shortest path algorithm uses dynamic programming, to geenrate shortest paths between all vertices in a given graph.

This algorithm is very simple to implement. It even works for edges with negative weight. Fails when there are negative cycles (For that you would need to implement the Bellman-Ford algorithm).

There are n vertices. Distance between the pair of vertices $i$ and $j$ is, $d(i, j)$. Because it’s the same vertex, $d(i, i) = 0$ So for every pair of vertices, $i, j$. We select a vertex $k$ such that $(i \neq j \neq k)$.

This is saying that, the minimum distance between $i$ to $j$, is either, going from $i$ to $j$ straight. Or going from $i$ to $k$ and then going from $k$ to $j$.

C/C++ Code would be as follwing. Given that we keep the graph in a adjacency matrix (map[n][n]).

1
2
3
4

for(int i = 0; i < n; i++)
    for(int j = 0; j < n; j++)
        for(int k = 0; k < n; k++)
            map[i][j] = min(map[i][j], map[i][k]+map[k][j]);

As you can see, there are 3 loops within each other, going from 0 to n. Therefore the time complexity is $O(n^3)$.

The code is very quick and easy to whip up. So the best places to be using this is if you want to find all or most pairs of shortest paths. It is easier and simpler than Dijkstra’s $O(n^2)$ shortest path algorithm to implement. You won’t be wasting much time, if most of the pairs of shortest paths are required.

Also check out the Bellman-Ford and Dijkstra’s shortest path algorithms.