The Java ShiftScanner Class – A Story.

I hate interviews. I really do. It doesn’t matter how much I know or how much I’ve done, there’s always some jerk in the interview process who keeps a special set of questions on obscure topics in Java just to use as a reason to keep you from getting a job – no doubt to save their own butt from getting fired. Case in point – the Disney Internet Group. This group was started by Patrick Naughton – that wonderful dot-com wunderkind who ended his fame and fortune by going to Southern California with the intent of having sex with a 14-year-old girl. The girl in this case was a 40-year-old male FBI Agent.

I think some of the original employees might still be there – certainly the culture of arrogance he created still exists. One day I interviewed with them and things went fine until the last interviewer of the day. Even the recruiter said this guy was a jerk. He was pretty creepy and I think he might have been a friend of Patrick’s.

But I digress. I had a rough time with this question he asked because it involves bit manipulation in Java. Something that unless you’ve been studying for the SCJP you probably won’t quickly answer. I struggled my way through the question and did *ok*. But I really wanted to make this class, so I went home and hashed it out in about 30 minutes.

The problem – you have a string of letters (e.g. ABBCDZEIFUAGHAFY). You need to return the unique occurrences of the letters in ascending order (e.g. ABCDEFGHIUYZ). Now you can do this different ways, but if you need to put this in a mobile phone, you’re going to want to use something that work’s with minimal resources – enter the ShiftScanner.

So here it is, complete with comments on how it works… Enjoy!

package com.codethought.utils;

/**
 * Scan a string, find all of the unique instances of the letters in the string
 * and return them in ascending order back to the caller.
 * <P>
 * <strong>Technical challenge</strong>: Do the actual processing without using
 * a string, an array, or sorting.
 * <P>
 * <strong>Technical overview:</strong>
 * <P>
 * Imagine instead of using an array of 26 <code>char</code> values, use a set
 * of 26 bits in an integer, with the low-order bit representing 'A', the next
 * bit to the left 'B', etc. Conceptually the representation looks like this:
 *
 * <pre>
 *    Z Y X W U V T S R Q P O N M L K J I H G F E D C B A
 *    ===================================================
 *    0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 * </pre>
 *
 * There are 64 bits in an integer - so you have more than enough room to work
 * in.
 *
 * So, if you string had "DZBBCZA" the representation in the 'accumulator' would
 * be:
 *
 * <pre>
 *    Z Y X W U V T S R Q P O N M L K J I H G F E D C B A
 *    ===================================================
 *    1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1
 * </pre>
 *
 * Finding out which letters are in your "bit array" is just a case of comparing
 * (bitwise 'and') your low-order bit to a 1. If the result is a 1, then the
 * letter was part of your original string. Append the letter representing that
 * bit to your <code>StringBuffer</code>. Then remove the low-order bit with
 * a right-shift and repeat the process until you've checked all 26 bits.
 *
 * <P>
 * <b>History</b><br>
 * Posed to me in a technical interview by some smarmy weasel jerk who was
 * trying to assert his superiority and therefore keep his job at the company I
 * was applying for. Considering how creepy this guy was I'm sure he was
 * interviewing his own replacement and just didn't know it. Prior to this I had
 * never tried using bit manipulation in Java - so I was caught a bit off guard
 * by this challenge. Actually this is a fun bit of code and very fast and
 * compact, ideal for environments like mobile phones. It doesn't change that
 * the guy I was interviewing with was a weasel, however.
 *
 * @author David Orriss Jr
 */
public final class ShiftScanner {

	private int accumulator = 0;

	private StringBuffer sbuf = new StringBuffer();

	public ShiftScanner(String data) {
		for (int i = 0; i < data.length(); i++) {
			accumulator = accumulator | 1 << ((int) data.charAt(i) - 65);
		}

		// now start from the lowest order (right-most) bit.
		// each bit that represents a 1 is letter that was in the
		// source string. put that letter in sbuf.
		for (int i = 0; i < 26; i++) {
			if ((accumulator & 1) == 1) {
				sbuf.append((char) (i + 65));
			}

			// right-shift the last-compared letter
			// out of the 'array' of bits.
			accumulator = accumulator >> 1;
		}
	}

	/**
	 * Returns the sorted StringBuffer back to the caller as a String.
	 *
	 * @return
	 */
	public String getResult() {
		return sbuf.toString();
	}

	public static void main(String[] args) {
		ShiftScanner scanner = new ShiftScanner("SSIRRO DIVAD");

		System.out.println(scanner.getResult());
	}
}