From the department of things that should throw exceptions...

    System.out.println("value: " + Math.abs(Integer.MIN_VALUE));

Try it out yourself! If this makes any kind of damn sense to you please enlighten me in the comments.

Someone should really fix that

Well there is a fantastic set of slides entitled: "Why python, ruby, and javascript are slow"


It is right here and you should go read it. but I can sum it up for you by copying a couple of slides

First: here is how you might define a point in C:

struct Point {
   double x;
   double y;
   double z;
};

Ok, thats nifty, lets do that in javascript:

var point = {
   'x':x,
   'y':y,
   'z':z
}

Correct so far, that is pretty much how you'd do that in javascript. But what you are really doing can be best explained by doing a literal translation of the javascript back into C:

std::hash_set<std::string, double> point;
point["x"] = x;
point["y"] = y;
point["z"] = z;

"If you put this in a code review, first your coworkers would laugh alot, and then they'd make mean jokes about you for the next year."

Nobody will laugh at you for doing it in javascript, because that is the best that we've got.

Someone should really fix that.

Is your development methodology wrong?

Agile is too unpredictable, we need more process!
Waterfall doesn't allow us to react to market changes fast enough, lets look at agile!

I hear this all the time in software and mostly ignore it, in general, if you are getting stuff done more or less on time, don't mess with your process, it is too much time for the benefit (assuming it doesn't make things worse).

There is a whole lot of meat in Sinofsky's most recent blog post about software methodology, and you should just go read it, but I'll pick out the hit list of Signs That Things are Going Off the Rails:

• Unpredictable.  Some efforts become unpredictable.  A team says they are going to be done on Friday and miss the date or the team says a feature is working but it isn’t.  Unpredictability is often a sign that the work is not fully understood—that the upfront planning was not adequate to begin the task.  What contributes to unpredictability is a two-steps forward, one-step back rhythm.  Almost always the answer to unpredictability is the need to slow down before speeding up.

• Lots of foundation, not a lot of feature.  There’s an old adage that great programmers spend 90% of the time on 10% of the problem (I once interviewed a student who wrote a compiler in a semester project but spent 11 of 12 weeks on the lexical phase).  You can overplan the foundation of a project and fail to leave time for the whole point of the foundation.  The checkpoint is a great time to take a break and make sure that there is breadth not just depth progress.  The luxury of time can often yield more foundation than the project needs.

• Partnerships not coming together.  In a project where two different teams are converging on a single goal, the checkpoint is the right time to sanity check their convergence.  Since everyone is over-booked you want to make sure that the changes happening on both sides of a partnership are being properly thought through and communicated.  It is easy for teams that are heads down to optimize locally and leave another team in a tough spot.

• Unable to make changes.  In any project changes need to be made.  Surprisingly both ends of the methodology spectrum can make changes difficult.  Teams moving at a high velocity have a lot of balls in the air so every new change gets tougher to juggle.  Teams that have done a lot of up front work have challenges making changes without going through that process.  In any case, if changes need to be made the rigidity of a methodology should not be the obstacle.

• Challenging user experience.  User interface is what most people see and judge a product by.  It is sometimes very difficult to separate out whether the UI is just not well done from a UI that does not fit well together.

• Throwing out code.  If you find you’re throwing out a lot of code you probably want to step back—it might be good or it might be a sign that some better alignment is needed.  We’re all aware that the neat part of software is the rapid pace at which you can start, start over, iterate, and so on.  At some point this “activity” fails to yield “progress”.  If you find all or parts of your project are throwing out more code, particularly in the same part/area of a project then it is a good time to check the methodology.  Are the goals clear?  Is there enough knowledge of the outcome or constraints?

• Missing the market. The biggest criticism of any “long” project schedule is the potential to miss the market.  You might be heads down executing when all of a sudden things change relative to the competition or a new product entry.  You can also be caught iterating rapidly in one direction and find competition in another.  The methodology used doesn’t prevent either case but a checkpoint offers you a chance to course correct.

That's pretty much it and if you are uncertain about what criteria you want to use for deciding when to revisit your team's process, you could do alot worse than to adopt this list.

Giving up on Java's Constructors

As much as I'm not always a fan of objective-c, I really like the method calling syntax:

    Merger merger = [[Merger alloc] initWithFirstString:"foo" andSecondString:"Bar" startingAt:1 suffleOutput:false lowercaseOutput:true];

If you wanted to write that in java, it would be fairly incomprehensible:

    Merger merger = new Merger("foo", "Bar", 1, false, true);

Just looking at this, who the hell knows what "foo" and "bar" are and why there is a number and a couple bools after it. You've have to look at the docs. Assuming you wrote docs... You could just nuke all the constructor params and create a whole lot of setters, and do this:

    Merger merger = new Merger();
    merger.setFirstString("foo");
    ...

But that sort of stinks too. First, it six lines of code for something that should go in one. Second, what if you want those parameters to be final?

So I've basically given up on constructors in java and added the following eclipse template to my tool belt:

            ${:import(com.google.common.base.Preconditions)}
            public static ${enclosing_type}Builder Builder() {
                return new ${enclosing_type}Builder();
            }

            public static class ${enclosing_type}Builder {
            private String property = null;

            @SuppressWarnings("synthetic-access")
            public ${enclosing_type} build() {
                Preconditions.checkState(this.property != null,
                    "property is required.");
                return new ${enclosing_type}(this.property);
            }

            public ${enclosing_type}Builder property(
                final String property) {
                this.property = property;
                return this;
            }
        }

It ends up being quite a bit longer than the original java code, but only slightly longer than objective-c. And I'm fairly certain that the next person that comes across my code is going to be very clear about what I was trying to do here.

If Eclipse templates had the support, I'd have it find all the members of constructors in the enclosing type for the builder and run checkState on all the final members but I'm fairly certain that would require plugin development.

What do you think?

Another Day, Another Java-In-The-Browser security hole

This one affects even fully patched, up to date browsers.
It works like so:

1. use any browser with java enabled
2. visit a page
3. owner of page can now execute arbitrary code on your computer

I love java, but, damn if it doesn't suck in the browser. This is just the latest, if you still have it enabled in your browser, now is the time to disable it. 

Do it now.

By convincing a user to visit a specially crafted HTML document, a remote attacker may be able to execute arbitrary code on a vulnerable system.

http://thenextweb.com/insider/2013/01/10/new-java-vulnerability-is-being-exploited-in-the-wild-disabling-java-is-currently-your-only-option/

Resume Visualization: What does your resume look like?

my resume, according to Tagxedo

I like to keep my resume up to date. Every time some new task comes along, I'll add that in there somewhere. Then if a new job comes up, I'll just edit out the old stuff, make a quick attempt at removing the irrelevant things, and mail it out. 

So what is my resume saying? 

Well on the advice of my wife I threw my resume into a word cloud generator. There are a few of them, but I picked tagxedo. 

So what does it say about me? Well not a whole lot about the technologies that I use, but a bunch about "management", "product", "design". I suppose that would be great if I were mostly focused on more management. Or if I were a product manager. But I'm probably not.

Now lets look at some of the jobs that I might be interested it.

I just took a stab in the dark: I like kindle, I like enterprise software, so I threw in the first job description from the kindle team that caught my eye. The result: a very different word cloud.

A Kindle SDE Job Description

Now I'm not saying you should lie on your resume: that will always come back to bite you very quickly. But your resume is basically just the sign on the front of a restaurant. I've done a bunch of things, and they'll all be reflected on my resume, but I am clearly spending much more time talking about things I've done that aren't relevant to the jobs I want than I should.

Because I'm in software and everybody needs them I get reasonably good responses when I apply for jobs, but I suspect now, that I'm getting this traction in-spite of my resume, not because of it.

Time to update.

Write your complicated, shared code once

write once, sorta runs everywhere

One of the deadly sins of software development is duplicating logic. I won't attempt a software engineering 101 class in a blog post: but you are more or less guaranteed to create bugs when you have logic doing the same thing implemented in two different places.


There was a time when this was easy: just don't cut and paste your code. Put everything in a library, then just use your library across projects. This time pretty much ended when we started using javascript to do Interesting Things on the web. When we started also doing interesting things on phones, it was long past.

Now we end up writing lots of code twice or more, because your server is probably written in java or .net, or php, or ruby and your phone is written in objective-c, or java, or something else.

Take a look at the fairly amazing diff-match-patch library used for keeping text documents in sync:

http://code.google.com/p/google-diff-match-patch/source/browse/#svn%2Ftrunk

Neil Fraser has written that library in python (both 2 and 3), java, javascript, c++, c#, lua, dart, and objective-c. While I have to admit a certain amount of awe for that guy's multilingual skills and the attention to detail necessary to get that stuff written in a way that all those implementations talk to each other correctly, I am not sure I want to spend that kind of time.

I also don't want to try to shoe-horn a project into a single common language. We tried that with Java once upon a time, we are currently trying it with javascript (in the form of node.js, and phonegap). These solutions always force you to accept some unacceptable compromise. Maybe phonegap and node.js works for your product. But chances are, someone else has something that is much better written in python and objective-c.

Write-once, run everywhere remains a non-starter in the general case.

What makes a whole lot more sense to me is to write only the code that must be shared once.

Figure out what your complicated, shared code is. If you are writing a shared text editor using diff-match-patch, it is that algorithm that is complicated, and must be shared across platforms.

Write _that_ in javascript.

Embed it in your code using a hidden WebView in IOS, Rhino in java, or maybe Ringo in Python.

There are a million embedded javascript solutions out there.

Then you are free to write the rest of your client and server independently of one another.

Slate (or How I Learned to Hate The Finder)

Sometimes I find myself tolerating something that sucks because I haven't really thought about how much better it could be. Moving, hiding, and window switching in Apple's Window manager is one of those things.

I didn't realize how much it sucked until I discovered Slate (Installer & Github site). It's a great little tool that allows you to bind hotkeys to window focus, move, or hide events.

It is a hyper-configurable (in fact it'll be mostly useless to you without a configuration file; but I'll point you at my configuration as a starting point) app for managing focus, size, and position of your windows with hotkeys.

A few examples that I've set up:

Command-Shift-B: bring my browser into focus.
Command-Shift-T: bring my terminal app into focus.
Command-Shift-Space: hide everything other than whatever window I have in focus.
Command-Shift-Delete: hide the current app.
It would be worth installing as just a replacement for command-tab as a window switcher, but you can do super-complicated things by chaining a bunch of operations together like so:

Command-Shift-=: hide everything except safari, eclipse, and iterm. Then move eclipse to the right side of the screen taking up 80% it. Then move iTerm to the other side and Safari to the bottom left. Finally, bring eclipse to the foreground.

Oh, and if you find yourself moving between laptop and monitor (or monitors) you can set up operations like that one to be triggered automatically when you plugin your monitor and get your apps into the right positions on all your monitors as soon as the OS detects them.

Here is my current configuration file:
http://code.google.com/p/geekery-blog-code/source/browse/trunk/src/main/scripts/slate.config

If you want to install it, just download it, and save it to ~/.slate with terminal or something.

And here are a few more resources I've found:

The Github Site: https://github.com/jigish/slate

Closure could be a bit more javascripty

My new years resolution for this year has been to take javascript more seriously. In that time, one of the things that has caught my attention (and affection) has been the closure compiler.

I do love closure, I do but as it is now, it can't really think of itself in a universe where one would write code that would _ever_ be executed uncompiled.

Until there is a (working) realtime compilation plugin for Eclipse, I'm going to need to run my JS uncompiled until I get it right, and then compile it.

Consider the following two types: ns.Type1 and ns.Type2.

var ns = {};
(function() {

 /** @constructor  */
  ns.Type1 = function() {
  };
  
})();

/** @constructor  */
ns.Type2 = function() {
};

/**
 * @param{ns.Type1} bar
 */
function foo(bar) {
}

/**
 * @param{ns.Type2} bar
 */
function baz(bar) {
}

They only differ in that ns.Type1 is created inside a closure. This lets you have actually private variables in javascript and generally allows for the sort of encapsulation that javascript should have had built into it. The second one, just defines everything out in the global namespace.

Everything works great for Type2. For Type1, you get a warning (and a failure) for attempting to reference the type in @param{ns.Type1} in your function at the bottom.

If you are always going to run your code compiled with ADVANCED_OPTIMIZATIONS, it really doesn't matter. You'll define your privates private with annotations and any illegal usage is going to fail compilation. Thats great. Except if you do your development and debugging in naked JS, you won't find these problems until you compile.

Is that a bug? Hard to tell: I suspect, given what I've read from the closure discussion groups, that this sort of thing was designed in.

And it gets worse, the further you go off the reservation. Consider Crockford would have us believe (and I am pretty sure he is right, at least I'm not sure he is wrong and he is smarter than me) that we would do well to define our functions for our Types in their constructor. Thats great, but in both cases there seems to be no way to tell the compiler that your Types expose various properties.

At any rate, I love closure. It makes for better javascript, but it could go a long ways towards making better javascript easier by simply adopting some of the best practices that have evolved over the years for making javascript safter without compilation. As an added benefit, these sort of things would make it much easier to make tools like jQuery compile with ADVANCED_OPTIMIZATIONS.

Your Binary Search Implementation Is Wrong

I've lost count of how many times I've written:

     public static int binarySearch(int[] a, int key) {
         int low = 0;
         int high = a.length - 1;

         while (low <= high) {
             int mid = (low + high) / 2;
             int midVal = a[mid];

             if (midVal < key)
                 low = mid + 1
             else if (midVal > key)
                 high = mid - 1;
             else
                 return mid; // key found
         }
         return -(low + 1);  // key not found.
     }

On someone else's whiteboard, usually as a warm up to something more complicated.

Turns out every time I wrote that I was wrong (along with most everyone else). Why? The bug is in this line:

int mid = (low + high) / 2;

Why? Our good friends at google research pointed this out few years ago. Good read it to find out what the bug is and then do it right next time someone asks you to whiteboard binary search (or most other divide and conquer algorithms).

http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html

Binary String Decryption Via Bottom Up DP

This question is primarily lifted from TopCoder, but has been extended slightly. It is, however, very similar to a question I've seen at Amazon as well and the pattern (bottom up dynamic programming) is highly useful for interviews and, occasionally, for real life problems.

Suppose you want to encrypt a string of digits in some radix (binary works well, but the astute reader will realize that this implementation will break down with any radix greater than 4) by traversing the string and for each digit, adding the sum of its adjacent digits.

So 111101 becomes 233201

Algebraically described, encrypted[i] = source[i - 1] + source[i] + source[i + 1]. Where the string is assumed to be padded with 0's before the start and after the end.

Or, setting i to i - 1 and rearranging: source[i] = encrypted[i - 1] - ( source[i - 1] + source[i - 2] ).

Since there is no encrypted value of -1, source[0] can be anything available within the specified radix, so we'll try to decrypt based on each possible value of source[0], eg: 0 - radix - 1 and check that each computed value of source[i] is valid for that radix.

so our recursive definition is

source[0] = {0,1 ... RADIX - 1}
source[1] = encrypted[0] - source[0]
source[i > 1] = encrypted[i - 1] - source[i - 1] - source[i - 2]

    public String[] decode(String in, int radix) {

        String[] mResults = new String[radix];

        for(int i = 0; i < radix; i++) {
            mResults[i] = decode(in, radix, i);
        }

        return mResults;
    }

    private String decode(String in, int radix, int startValue) {

        char[] mString = in.toCharArray(); //
        int[] mEncrypted = new int[mString.length]; //encrpted
        int[] mDecrypted = new int[mString.length];
        //int[] mP = new int[mString.length]; //original
        //bottom up dp
        for(int i = 0; i < mEncrypted.length; i++) {
            mEncrypted[i] = Integer.parseInt(String.valueOf(mString[i]));
        }

        int mPreviousPrevious = 0;
        int mPrevious = 0;
        for(int i = 0; i < mEncrypted.length; i++) {
            
            if(i == 0) {
                mDecrypted[i] = startValue;
            } else {
                mDecrypted[i] = mEncrypted[i - 1] - (mPrevious + mPreviousPrevious);
            }
            if((mDecrypted[i] < 0 || mDecrypted[i] >= radix)) {
                return "NONE";
            }
            mPreviousPrevious = mPrevious;
            mPrevious = mDecrypted[i];
        }
        //now check to see that the last one makes sense
        if( mEncrypted[ mEncrypted.length - 1 ] != mDecrypted[mEncrypted.length - 1] + mPreviousPrevious) {
            return "NONE";
        }

        return intArrayToString(mDecrypted);
    }

    private String intArrayToString(int[] intArray) {
        StringBuilder mBuilder = new StringBuilder();
        for(int i = 0; i < intArray.length; i++) {
            mBuilder.append(intArray[i]);
        }
        return mBuilder.toString();

    }

So, what is the quick and dirty for solving something like this in an interview:

For any function F(x) that can be define with constants and F(i) where i is always less than X:
1. Define the function. Eg: F(x) = input(x - 1) - (F(x - 1) + F(x - 2))
2. Cache the values of F(x) as you compute them (though only as many as you need, in this case our mPrevious, and mPreviousPrevious)
3. Define the base cases and either initialize the cache, or check for them in a loop (we checked for them so we didn't have to do additional logic to catch the cases where the array is one or two digits long.

The rest is just string manipulation which you should be able to do in your sleep.

When I find some more time, I'll do another one of these for calculating the Levenshtein Edit Distance for two strings. A classic!

By the way, I doubt this is secure encryption so please don't kick my ass if you happen to be a security aficionado.

Quickie: Binary Printing

This one is probably about the right size for a phone screen question. I've seen this as print a binary string, print a decimal string, and print a hex string. They are all good and it shouldn't take someone more than a few minutes of thinking and a few minutes of scribbling to get it done.

    public static String printme(int i) {
        StringBuilder mOut = new StringBuilder();
        
        while(true) {
            if(i % 2 == 1) {
                mOut.insert(0, "1");
            } else {
                mOut.insert(0, "0");                
            }
            i = i / 2;
            if(i == 0) {
                return mOut.toString();
            }
        }
        
    }

For the reader: code up an integer representation without using ten else-ifs or java's automatic integer to string converters. Just append chars.

Quickie: String Reversing

An oldie but a goodie (actually, not a goodie, but I'll talk about that at the end). This question is often phrased in two parts:


First: Write an algorithm to reverse a string.


This should be pretty boring to you. Just start at the ends of the array and swap each element until the ends touch. I find keeping a start and an end counter to be easier to code on a whiteboard. Some people like to just increment a single counter for the start and calculate the end pointer from the length of the array. Probably a slight performance hit that way, but I wouldn't no hire someone for it.

        int mStart = 0;
        int mEnd = mChars.length - 1;
        while(mStart < mEnd) {
            char mTemp = mChars[mStart];
            mChars[mStart] = mChars[mEnd];
            mChars[mEnd] = mTemp;
            mStart++;
            mEnd--;
        }

So the second part of the question is: now reverse the order of the words in the string without reversing the words themselves so that a string "this is a test" would convert to "test a is this".


I'm not a fan of this for two reasons: First, half the candidates have seen this an know the trick. Second, for those who haven't seen it, it requires a flash of insight. Anything that requires a flash of insight just tests whether the candidate is lucky enough to have insightful flashes durring interviews. I'd rather see something test coding skill, algorithmic reasoning, grasp of recursing, anything like that. Just not luck.


But whatever, someone is probably going to ask you this question someday so here is the answer: reverse the string once, then reverse each word again. So first you make "tset a si siht" then you reverse that to "test a is this".

         int mStart = 0;
        int mEnd = mChars.length - 1;
        while(mStart < mEnd) {
            char mTemp = mChars[mStart];
            mChars[mStart] = mChars[mEnd];
            mChars[mEnd] = mTemp;
            mStart++;
            mEnd--;
        }
        
        int mLastWordStart = 0;
        int mLastWordEnd = 0;
        int mCurrentLocation = 0;
        while(mCurrentLocation < mChars.length) {
            
            mLastWordStart = -1;
            mLastWordEnd = -1;
            while((mCurrentLocation < mChars.length) && 
                    (mChars[mCurrentLocation] == ' ')) {
                mCurrentLocation++;
            }
            
            mLastWordStart = mCurrentLocation;
            
            while((mCurrentLocation < mChars.length) &&
                    (mChars[mCurrentLocation] != ' ')) {
                mCurrentLocation++;
            }
            
            mLastWordEnd = mCurrentLocation - 1;
            
            while(mLastWordEnd > mLastWordStart) {
                char mTemp = mChars[mLastWordEnd];
                mChars[mLastWordEnd] = mChars[mLastWordStart];
                mChars[mLastWordStart] = mTemp;
                mLastWordEnd--;
                mLastWordStart++;
            }
            
        }

There it is! Variations of this that I've seen include a question about how to flip a bitmapped image which is represented as a two dimensional array of pixels. The solution (which I'll leave largely to the reader) is treat each line of the file as a string to reverse and reverse them once. You could also probably do some cool pattern based conditional flipping by combining the word-by-word string reversal with the bitmap question.

Programmer Competency Matrix

Ran across this excellent matrix

http://www.starling-software.com/employment/programmer-competency-matrix.html

I plan to start using this when I interview people, it'll help.

But more to the point, I suggest that it is highly valuable as a sort of check list that we should all use to help ensure that we build and maintain our skills. I suspect it is a rare developer who is comfortable with everything in the boxes on the far right of the grid, but if you've been in the industry for ten or more years and you can't comfortably check off most of them, it is probably time to start sharpening your skills.

Pick up a new development book, write some code in a language you've never used before. Code up a few new algorithms or data structures. If that doesn't sound like fun to you, you are probably in the wrong industry.

Recursive Money Counting: Or why avoid recursion

Last post I asked this:

Question: Write an algorithm that, when given some number of pennies, will print out all the ways that this value can be represented in nickels, dimes, quarters, and dollars, but don't use recursion.

In this post, I'm going to describe the recursive version and then talk about some of the differences between the two.

As mentioned, I don't much like recursion because of the overhead and because it makes things like ugly in a debugger.

But it does often lead to easier to develop and maintain code. It is, after all, just using another construct of a high level language, like objects or inheritance or function overloading. Those all have costs, but we happily pay them because it tends to make our software faster to develop and easier to maintain.

But here is the big difference in my mind: recursion is used most obviously in the design of the algorithms we most want to execute quickly: sorting, tree traversal, etc.

Algorists tend to love recursion because it makes for tidy algorithms (think quick sort, then try to imagine it without recursion: doable, but really ugly and no good for a text book). But algorithm design is exactly where you want to pay attention to performance issues. After all, if you just wanted easy to understand algorithms, we'd all just use insertion sort or bubble sort in all cases and be done with it and we certainly wouldn't worry about using adaptive sorting algorithms.

What is the cost of recursion? Well each time we call a function, we create a stack frame with the byte code we're executing and any local variables and parameters, then we push the frame onto the stack. When we return, we have to pop that frame off the stack restore the local variables and parameters and jump back to the byte code we were executing before we started. People who write JVMs and compilers care a bunch about making this run fast, but the fastest code is the code you don't execute so it'll always take some time. How much? Lets run through the recursive method and do some comparisons to find out.

For the recursive version of this algorithm, I'm going to leave out the printCurrency and getValue they are identical to the versions in the last post if you want to see them.

  public static void startRecursiveCountPennies(int pennies) {
      int[] mInts = {0,0,0,0};
      recursiveConvertPennies(pennies, mInts, mInts.length -1);
  }
  public static void recursiveConvertPennies(int pennies, int[] currency, int currencyTypeIndex) {
      while(true) {
          if(getValue(currency) > pennies) {
              currency[currencyTypeIndex] = 0;
              return;
          }
          if(currencyTypeIndex == 0) {
              printCurrency(pennies, currency);
          } else {
              recursiveConvertPennies(pennies, currency, currencyTypeIndex - 1);
          }
          currency[currencyTypeIndex]++;
      }
  }

So what is happening here? We're creating an array to represent the total number of each type of coin (except pennies, remember we just calculate how many pennies are left over for each of the coin type sets) and we're using a pointer to indicate where in the array we are working. While the value of our currency array is less than the total number of pennies, we call increment the counter and call ourselves, then increment the number of the type of currency the pointer is pointing at, and so on.

Before we return, we reset the currency type at our pointer to zero.

When the pointer itself is zero we'll print the values rather than calling ourselves again.

As a test, I commented out the printing of the values, set some timers and ran both the recursive and the non-recursive methods with 5000 pennies each. Over and over again, the nonrecursive version ran 20% faster than the recursive version.

So there you have it. Later on, I'll write a post about the recursive vs. non-recursive string mutation method. To be titled: how I didn't get a job I wanted back in 2001.

Take home lesson:

Recursion may make for easy to read algorithms, but be mindful of the costs.

The Rolling Counter Algorithm Pattern

Question: Write an algorithm that, when given some number of pennies, will print out all the ways that this value can be represented in nickels, dimes, quarters, and dollars. And don't use recursion.

Why not recursion? First, because the solution is more elegant. Second, because I don't like recursion. For more on why, see my next post "why I don't like recursion" ... or something like that but the short answer is that it is less efficient.

Before I get into this question, I’m going to discuss the rolling counter algorithm pattern for which this blog post is named: This pattern is often useful in interviews (almost as useful as the "just model it as a graph and traverse it or find the spanning tree" pattern) and usually ends up tripping me up, especially when I fail to recognize that I need to use it rather than (say) a bunch of nested for loops or worse: recursion. Maybe it trips you up too. Hopefully this post will make the pattern clear enough that it’ll stop tripping you and me up.

BTW: any time someone asks you to print the set BLA{…} where condition FOO holds true, you should think of this pattern. Ill try to make the why clear later.

You should think of a rolling counter as being analogous to the odometer on a car. As you’re driving the first roller of the odometer increases one mile at a time until you drive past nine miles. At this point, rather than increasing that roller to 10, it goes back to 0 and increments the second roller. Then you go back to incrementing the first roller for another ten miles. Eventually you have to increment the third roller, and so on. Until you run out of rollers, but you've usually replaced your car by then.

In code, you first, initialize the counter (note that if you are using java as I am, you'll get the initialization to zero done for you).

int[] mRollingCounter = new int[length];
for(int i = 0; i < mRollingCounter.length; i++) {
mRollingCounter[i] = 0;
}

Now the code to roll the counter:

int mCounterPointer = 0
while(mCounterPointer < mRollingCounter.length) {
mRollingCounter[mCounterPointer]++;
if( rollcondition() == true) {
   mRollingCounter[mCounterPointer] = 0
} else {
   break;
}
}

That is all there is to execute a single increase of the counter. The critical bit is the rollcondition() function. It is what tells the odometer that we've tried to roll past 0009 miles and should increment the second roller to 1. Or that you've tried to roll past 0099 miles and you need to increment the third roller.

We start with the first element of the counter and increment it. (This is equivalent to the odometer going from [0][0][0][0] to [0][0][0][1].) If this change triggers the counter rolling condition, set that element back to zero, move to the next element of the counter and continue. (this is what happens when we’re already at [0][0][0][9], first we go to [0][0][0][10] and since any element being greater than 9 is a roll condition for an odometer, we set the counter back to [0][0][0][0], move the pointer one over, and again increment to [0][0][1][0] at which point we break.

If this isn’t clear, code it up in your favorite IDE and play with it for a while (full code sample is below for the lazy) until you understand it or you can just TRUST ME and memorize it to be spit out in your next interview. Your choice, but I’d suggest understanding it.

So implementing an odometer isn’t that interesting but other things are. For example, if you can write a non recursive string permuter with this (ie, given a string of characters, print all the possible re-arrengements of characters). Or something to spit out all the possible ways that 50 cups of beer can be represented with various imperial units. I’m going to now get into the question that I started this post with.

 public static String[] mLabels =
     {"Nickles", "Dimes", "Quarters", "Dollars"};
 public static int[] mUnitBases = {5, 10, 25, 100};

 public static void convertPennies(int pennies) {

     int mCounterPointer = 0;
     int[] mRollingCounter = new int[mUnitBases.length];

     while(mCounterPointer < mRollingCounter.length) {
         printCurrency(pennies, mRollingCounter);
         mCounterPointer = 0;
         while(mCounterPointer < mRollingCounter.length) {
             mRollingCounter[mCounterPointer]++;

             if(getValue(mRollingCounter) > pennies) {
                 mRollingCounter[mCounterPointer] = 0;
             } else {
                 break;
             }
             mCounterPointer++;
         }
     }
 }

 public static int getValue(int[] currency) {
     int mTotalValue = 0;
     for(int i = 0; i < currency.length; i++) {
         mTotalValue += currency[i] * mUnitBases[i];
     }
     return mTotalValue;
 }

 private static void printCurrency(int pennies, int[] currency) {
     for(int i = 0; i < currency.length; i++) {
         System.out.print(String.valueOf(currency[i]));
         System.out.print(" " + mLabels[i] + " ");
     }
     System.out.println(" and " +
         (pennies - getValue(currency)) + " pennies");
 }

And there you have it.

Take home lesson:

Any time you need to iterate through all the permutations of a thing, consider using a rolling counter.

Distributed Sorting

So you've got a pair of servers (I'll call them servers A & B) and each of them has an array of strings in random order. You are to find a way to sort the strings such that if you lined the arrays up server A first, server B second, this combined array of strings would be sorted. That is to say: all the strings are sorted and the higher strings are all on server A and the lower strings are all on server B. These arrays take up most of the storage on the servers and your network connectivity between servers is mediocre.

How do you accomplish this with the lowest network traffic?

The naive solution is pretty simple given these constraints and looks like this:

First, sort all of the strings on each server locally.
Then compare the last string on A to the first string on B
If A[last] > B[first], swap them, then resort the strings locally on each server.
Otherwise, you are done.

So what is the cost (worst case where n is the number of keys per server):

Your local sorts are free since we don't care about those.
If you have to compare every single key, you'll make 2n comparisons.
And so the cost will be 2n * the size of the keys in network traffic + a small amount of overhead to open and close the connection if we use http or similar.

Great! So lets say you have a million ten character strings on each server. How long will this take? Twenty megabytes in a fast data center? A few seconds at most, totally reasonable.

And then things start to get interesting.

So... now we should consider the speed of the whole system, data transfer _and_ local sorting. A smart candidate will have already thought this far ahead, if they are accustomed to thinking about everything in terms of big O. But then it is easy to fall into the trap of thinking that network speed is so much slower than things that happen in memory that we can forget big O in situations like this. We'll see that we can't.

So, ok, we've got a good sorting algorithm O(n ln n) or maybe even O(k n) if you take advantage of the shortness of the strings to be sorted. Great, so we do that. Then, in the worst case we have to move all the strings to different servers, so that is n. AND we're resorting the strings again which should cost O(n) with each string we move across so we're looking at O(n^2).

So what does n^2 mean here? Well if we have fast memory, we can get each 10 char key out of memory in around 100 ns. So lets say (10^6)^2 * 100 ns. If I'm doing my math right here, that comes out to over 27 hours. So we spend a few seconds streaming data across the wire because we managed to minimize network traffic but we spend 27 hours resorting arrays of strings.

At this point, the fix should be pretty obvious. Move all the strings that you need to move, then sort them. But how do we know which ones to sort?

Well here is the trick, obvious to some, not obvious to others: for every string on server B that is lower in value than the lowest string on server A, we can move that string from B to A, and at the same time move the lowest string from A to B.

Think of the keys as arrays on both servers. Set a pointer at the end of the array for the first server (ie: the highest key on the lowest server) and a pointer at the start of the array on the second server (ie: the lowest key on the highest server). As long as the key at the pointer on the first server is greater than the key at the pointer on the second server, we need to swap the keys. Here is a worst case example (with single letter keys for simplicity):


After each swap, we move the pointers (the first server's pointer moves left, the second server's pointer moves right) and again compare the keys under the pointers.


Again, as long as the key at the pointer on the first server is greater than the key at the pointer on the second server, we need to swap the keys.



When we're done, we'll again have an unsorted array of keys on each server, but we can guarantee that all the right keys will be on the right servers. From here we can just resort the servers again, and we'll be done.

Take home lesson:
1. Even though moving data around a datacenter takes a while (20 ms to send a couple k around a data center) moving data around in memory still costs some time: 1/2 a ns for L1 cache kits, 100 ns to hit main memory. Yes, orders of magnitude difference, but:
1. O(n^2) is almost always worse than O( n ln n) even when the operations described by n^2 are much, much faster.

Java Enums

Everyone loves the open-ended interview question:

"So, tell me about java enums."

This is a good question for a reasonably well vetted candidate. Obviously, you don't want to ask any questions that result in a blank stare but if you've taken your candidate through a take home test with actual code in it, these sort of questions can lead to a great deal of fruitful conversation.

Enums are neat, and to tell you the truth, I hadn't really thought much about them until I asked a friend to walk my through some of the finer points of an Amazon job interview.

The most important thing about them (to my mind) is that they are a clean replacement for static final int

So you can replace this:

public static final int BLUE = 15;

public void setColor(int color) {
//do some stuff...
}

which will happily let you pass any integer into the set color method even if it isn't something that you've defined as a color.

with something like below:

public enum Color {
RED, PURPLE, GREEN
}

public void setColor(Color color) {
//do some stuff...
}

which will only let you pass something that you've described in the enum.

Even better if you call toString() on that int named BLUE above, you'll get "15". Call it on the enum Color.RED and you'll get "RED". That will certainly make for some much better debug messages.

What else? Well you can add methods:

public enum Color {
    RED("#FF0000"),
    PURPLE("#FF00FF"),
    GREEN("#00FF00");
    public String cHexValue;
    private Color(String hexValue) {
        cHexValue = hexValue;
    }
    public String getHex() {
return cHexValue;
    }
}
...

System.out.println("What color is Red? " + Color.RED.getHex());

I can think of situations where that would make sense, but honestly, if I needed something like a Color object that had some properties, I'd likely create an actual java class and give it the properties that it needed and back its color labels with an internal enum. Maybe someone can give me a reason why that would be a bad idea in the comments?