This is the second assignment from the interview (see also my previous blog entry):

A collection of particles is contained in a linear chamber. They all have the same speed, but some are headed toward the right and others are headed toward the left. These particles can pass through each other without disturbing the motion of the particles, so all the particles will leave the chamber relatively quickly.

You will be given the initial conditions by a String init containing at each position an 'L' for a leftward moving particle, an 'R' for a rightward moving particle, or a '.' for an empty location. init shows all the positions in the chamber. Initially, no location in the chamber contains two particles passing through each other. We would like an animation of the process. At each unit of time, we want a string showing occupied locations with an 'X' and unoccupied locations with a '.'.

Create a class Animation that contains a method animate that is given an int speed and a String init giving the initial conditions. The speed is the number of positions each particle moves in one time unit. The method will return an array of strings in which each successive element shows the occupied locations at the next time unit. The first element of the return should show the occupied locations at the initial instant (at time = 0) in the 'X', '.' format. The last element in the return should show the empty chamber at the first time that it becomes empty. The method signature: public String[] animate(int speed, String init).

You may assume the following constraints: speed will be between 1 and 10 inclusive, init will contain between 1 and 50 characters inclusive, and each character in init will be '.' or 'L' or 'R'.

Here are some examples:

1) 2, "..R...."
Returns:
..X....
....X..
......X
.......


The single particle starts at the 3rd position, moves to the 5th, then 7th, and then out of the chamber.

2) 3, "RR..LRL"
Returns:
XX..XXX
.X.XX..
X.....X
.......


At time 1, there are actually 4 particles in the chamber, but two are passing through each other at the 4th positio.

3) 2, "LRLR.LRLR"
Returns:
XXXX.XXXX
X..X.X..X
.X.X.X.X.
.X.....X.
.........


At time 0 there are 8 particles. At time 1, there are still 6 particles, but only 4 positions are occupied since particles are passing through each other.

4) 10, "RLRLRLRLRL"
Returns:
XXXXXXXXXX
..........


These particles are moving so fast that they all exit the chamber by time 1.

5) 1, "..."
Returns:
...

6) 1, "LRRL.LR.LRR.R.LRRL."
Returns:
XXXX.XX.XXX.X.XXXX.
..XXX..X..XX.X..XX.
.X.XX.X.X..XX.XX.XX
X.X.XX...X.XXXXX..X
.X..XXX...X..XX.X..
X..X..XX.X.XX.XX.X.
..X....XX..XX..XX.X
.X.....XXXX..X..XX.
X.....X..XX...X..XX
.....X..X.XX...X..X
....X..X...XX...X..
...X..X.....XX...X.
..X..X.......XX...X
.X..X.........XX...
X..X...........XX..
..X.............XX.
.X...............XX
X.................X
...................


Here is my solution:

public String[] animate(int speed, String init)
{
	int curr[] = new int[init.length()];
	List<String> result = new ArrayList<String>();
	boolean empty = false;

	for(int i = 0; i<init.length(); i++)
		curr[i] = init.charAt(i)=='.'?0:init.charAt(i);

	while(!empty)
	{
		StringBuilder state = new StringBuilder();
		int next[] = new int[curr.length];
		empty = true;

		for(int i = 0; i<curr.length; i++)
			if(curr[i] != 0)
			{
				state.append('X');
				empty = false;
			}
			else
				state.append('.');

		for(int i=0; i<curr.length; i++)
		{
			if(curr[i]>='R' && i+speed<next.length)
				next[i+speed]+='R';
			if((curr[i]=='L' || curr[i]>'R') && i-speed>=0)
				next[i-speed]+='L';
		}

		result.add(state.toString());
		curr = next;
	}

	return result.toArray(new String[0]);
}

The complete source code, with the test cases: Animation.java.

One of my friends recently interviewed with a hedge fund in New York. The fund conducted a brief phone interview and then sent an email with two interesting coding problems. You could choose any of the three major languages, i.e. C, C++, or Java. I like Java. They’re not all that challenging at the end of the day; however, with limited time, one may not find these assignments trivial. Since these are actual interview questions from yesterday, I’m not going to mention the fund’s name. In theory, although very unlikely, someone could find this while their taking the very same exam.

The first assignment:

Sentences such as “A quick brown fox jumps over the lazy dog”, contain every single letter in the alphabet. Such sentences are called pangrams. You are to write a method getMissingLetters, which takes a String, sentence, and returns all the letters it is missing (which prevent it from being a pangram). You should ignore the case of the letters in sentence, and your return should be all lower case letters, in alphabetical order. You should also ignore all non US-ASCII characters. The code you submit must contain a method that conforms to the expected method signature, as follows: public String getMissingLetters(String sentence).

Here are some examples:

1) "A quick brown fox jumps over the lazy dog"
Returns: ""

2) "A slow yellow fox crawls under the proactive dog"
Returns: "bjkmqz"

3) "Lions, and tigers, and bears, oh my!"
Returns: "cfjkpquvwxz"

4) ""
Returns: "abcdefghijklmnopqrstuvwxyz"

Here is my solution:

public String getMissingLetters(String sentence)
{
	boolean occurances[] = new boolean[26];

	for(int i = 0; i < sentence.length(); i++)
	{
		int c = (int)sentence.charAt(i);

		if(c >= 'A' && c <= 'Z')
			occurances[c-'A'] = true;
		else if(c >= ('A'+32) && c <= ('Z'+32))
			occurances[c-'A'-32] = true;
	}

	StringBuilder missing = new StringBuilder();

	for(int i = 0; i < occurances.length; i++)
		if(!occurances[i])
			missing.append((char)(i+'A'+32));

	return missing.toString();
}

The complete source code, with the test cases: MissingLetters.java.

Not sure whether you have heard about Amazon’s Kindle yet, but do check out the videos on their site and the Newsweek article on Kindle.  The article not only talks about Kindle, but also about the evolution of writing in general.  Sure eBooks have been around for a while now, but I don’t think none has had such impact as Kindle will.

There are already a lot of negative reviews for the product on Amazon, but they really boil down to a couple of topics: large next and previous page keys, no PDF support, and DRM restriction.  This product to me is quite amazing–it’s revolutionary and it may have a great effect on how we consume written media and save the environment.  Yet, these people are going off on topics that are completely irrelevant; thus my frustration here.  First, if you are not intelligent enough to pick up an object from a different angle and fumble on keys, then perhaps you should really not buy the product; just send it back.  Second, if you want to read PDF documents, read them on your PC or better yet, on your cell phone.  Kindle was not created to be a PDF reader.  Finally, people have to get over the fact that they’re not going to own an object when the pay for something.  Do you own a film after you pay $11 to watch a movie at a theater?   Books on Kindle are digital, and yes, if you have no space on your device, you will have to trust Amazon to keep the content for you.  True, in essence you are borrowing the books.  We seem to accept the very same fact with on-demand movies and other media content, but I guess that it will take a while before we get over our Neanderthal instinct of owning something and feeling it in our hands.  If you’re an avid and evolving reader, you wouldn’t read the same books in 20 years that you are reading today.  Classics yes, but if you feel like reading a couple of books over and over again or lending them to your friends, then get a couple of paper copies.  Kindle and physical books can co-exist.  Kindle is great for reading contemporary literature, newspapers, magazines, and blogs.  For the price a movie ticket, you get any book on your device that lasts as long as, well, Amazon will exist.  Even when Amazon ceases to exist, I’m confident that someone will take over the technology and convert it to some other format.  So your mind can be at peace–you’ll most likely die before the format of the content is outdated; and if you’re really lucky, there are smart people out there who will make sure that your Kindle content will be available for your grandchildren as well.  In case you really think that they will read your Oprah Book Club books from 2007!?

One more point about the environmental benefits.  If you haven’t seen Al Gore’s Inconvenient Truth yet, go see it now!  You obviously know about global warming, but when you see Gore’s story, you start thinking about it differently–you’ll start thinking about saving energy, buying Teslas, halogen bulbs, etc.  When you put Kindle into the context of the environmental benefits, the product becomes quite compelling.  Here’s a related quote from the Newsweek article:

“Microsoft’s Bill Hill has a riff where he runs through the energy-wasting, resource-draining process of how we make books now. We chop down trees, transport them to plants, mash them into pulp, move the pulp to another factory to press into sheets, ship the sheets to a plant to put dirty marks on them, then cut the sheets and bind them and ship the thing around the world. “Do you really believe that we’ll be doing that in 50 years?” he asks.”

Now excuse me, I will go ahead and order a Kindle.

I recently got a new Dell and it had Google Desktop pre-installed.  The gadget idea (appearing on your desktop) originates from the Mac world, I belive.  Anyway, in case you are interested in building your own gadgets, take a look at this tutorial.

Nice document from 2005, out of UC at Irvine on the state of web application technologies: Survey of Technologies for Web Application Development.

I know that a lot of people will dislike me for this blog entry. Being originally from Estonia I should be a big fan of Skype (Skype was primarily developed in Estonia). Unfortunately, I’m not. I don’t like Skype’s evasive interface, some annoying features, it’s charge plan, and the fact that you have to have your computer on to use the service. Yes, I’ve seen the new Skype phones that don’t require a computer… Trust me, I wouldn’t set that aesthetical disaster in my living-room even if someone paid me to do it. Here are some of the new alternatives (some address all, some address some of the issues listed above):

Gizmo Project - allows free calls to a lot of countries

Jajah - works from the US phones, using your phone only, free calls to almost all countries

Rebtel - very similar to Jajah, you can do a lot of things for $4 per month (see pricing):

Of course then you have many services such as the following that provide you with great service by making the VOIP experience transparent, with a lot of add-on services.

The best service, of course, is from AT&T. Why the best? Because I’m using it.