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.

This may well be the reason for the latest, phenomenal market volatility. Anyway, got this great clip from someone. However, since I don’t remember who and I don’t know the name of the artist, I can’t really give credit to anyone at this time. Brilliant though?

One of the great products of the blog-vlog-pod culture: wallstr**.com.