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.