js2-mode: a new JavaScript mode for Emacs

I've written a new JavaScript editing mode for GNU Emacs, and released it on code.google.com.

This is part of a larger project, in progress, to permit writing Emacs extensions in JavaScript instead of Emacs-Lisp. Lest ye judge: hey, some people swing that way. The larger project is well underway, but probably won't be out until late summer or early fall.

My new editing mode is called js2-mode, because eventually I plan to support JavaScript 2, also known as ECMAScript Edition 4. Currently, however, it only supports up through JavaScript 1.7, so the name is something of a misnomer for now.

It's almost ten thousand lines of elisp (just for the editing mode), which is more than I'd expected. So I figured I'd tell you a little about what it does, why I made certain choices, and what's coming up next. Even if you're not a JavaScript user, you might find the technical discussion mildly interesting.

Features

In no particular order, here's what js2-mode currently supports.

M-x customize

All the user-configurable variables are defined as Custom variables for use with M-x customize. This means you can type

M-x customize-group RET js2-mode RET

to see a list of all the configuration options.

All the colors used for syntax highlighting are defined in the same js2-mode customization group, for convenience.

Many people complain that Emacs's Customize feature is lame. I thought so too, for a long time, and I'm certainly not claiming it's as good as a "real" UI. But I now appreciate that it gets the job done admirably for a text editor: there are no dependencies on GUI widgets, and you can use the Customize package over an ssh or telnet session. That's at least kind of cool.

Accurate syntax highlighting

This mode includes a recursive-descent parser that I ported from Mozilla Rhino. That means it's always right. It doesn't use heuristics or guesswork; it's exactly the same parser used by JavaScript engines. If it's ever wrong, then it's a bug in my code, and it's fixable.

The amount of syntax highlighting is configured by a variable called js2-highlight-level. It ranges from 0 to 3, with the default set at 2. Zero (or nil/NaN) means no highlighting. level 1 does basic syntax highlighting: keywords and declarations. Level 2 adds highlighting for Ecma-262 builtins (and SpiderMonkey extensions) such as Infinity, __proto__ and decodeURIComponent. Level 3 adds highlighting for all built-in functions and properties for all native JavaScript objects (Function, Date, Array and so on.)

The highlighting faces are my own choices, because I felt it was important for me to foist my personal style choices on the general public. Actually, that's only partly true: it's also because I like the color schemes employed by Eclipse and IntelliJ better than the default Emacs color scheme. So comments are green (not red!), keywords are blue, strings are soft blue, var decls are sea green, and so forth.

Fortunately for those (hopefully few) among you who love blood-red comments, you can add this to your .emacs file to make js2-mode honor your font-lock settings:

(setq js2-use-font-lock-faces t)

Or, alternately, M-x customize-variable RET js2-use-font-lock-faces RET and set the value to t, which is Lisp for "true". This particular variable requires an Emacs restart to take effect.

I just added a TODO item for myself: define Eclipse and IntelliJ color schemes that you can choose from. Should be pretty easy.

Asynchronous highlighting

Unlike most other Emacs modes (but like nXML mode), js2-mode does not use font-lock-mode, which is the standard Emacs infrastructure for doing syntax-coloring in buffers.

Although font-lock is quite fast and fairly flexible, it still uses heuristics to figure out what to highlight, and they can occasionally be wrong. If you've ever opened up prototype.js in Emacs and seen the second half of the file turned string-blue on account of being confused over a regular expression literal with a quote in it, you know what I'm talking about.

James Clark's nXML-mode does its own syntax coloring without using font-lock. It can do this because James wrote his own, fully-compliant, validating XML parser, so adding colors was a snap. I thought this was pretty macho, and since I also happen to have a full parser, I blatantly copied his idea.

For the OOD-loving and API-minded among you, the "beautiful" way to do syntax coloring would have been to finish parsing, then walk the AST using a Visitor interface, applying the coloring in a second pass. I tried it, and it was, as they say, "butt slow". In fact (perhaps not surprisingly) walking the AST takes exactly as long as parsing, so it was twice as slow as doing it inline.

So I bit the bullet and moved my syntax-coloring to happen inline with parsing. Fortunately it only introduced about 30 lines of code to the 4000-line parser/scanner, because most of the coloring happens in the scanner, at the token level. Go figure.

Unfortunately, my parser is asynchronous. It "sort of" happens on another thread, although what's really happening is that it waits for Emacs to become idle and parses until you hit a key or use the mouse. I wanted it to be synchronous, boy howdy I did, but it just wasn't quite fast enough. It can parse about 5000 lines a second, give or take, but for any file longer than 1000 lines or so, the parsing was happening every time you typed a key (that's what synchronous means, obviously), and the 0.2+ second delay became painfully noticeable.

I had two options: incremental parsing, or asynchrous parsing. Clearly, since I'm a badass programmer who can't recognize my own incompetence, I chose to do incremental parsing. I mentioned this plan a few months ago to Brendan Eich, who said: "Let me know how the incremental parsing goes." Brendan is an amazingly polite guy, so at the time I didn't realize this was a code-phrase for: "Let me know when you give up on it, loser."

The basic idea behind incremental parsing (at least, my version of it) was that I already have these little functions that know how to parse functions, statements, try-statements, for-statements, expressions, plus-expressions, and so on down the line. That's how a recursive-descent parser works. So I figured I'd use heuristics to back up to some coarse level of granularity — say, the current enclosing function – and parse exactly one function. Then I'd splice the generated syntax tree fragment into my main AST, and go through all the function's siblings and update their start-positions.

Seems easy enough, right? Especially since I wasn't doing full-blown incremental parsing: I was just doing it at the function level. Well, it's not easy. It's "nontrivial", a word they use in academia whenever they're talking about the Halting Problem or problems of equivalent decidability. Actually it's quite doable, but it's a huge amount of work that I finally gave up on after a couple of weeks of effort. There are just too many edge-cases to worry about. And I had this nagging fear that even if I got it working, it would totally break down if you had a 5,000 line function, so I was kinda wasting my time anyway.

So, without telling Brendan (and don't you dare mention it to him), I switched to asynchronous parsing. Actually, first I went around to my Eclipse- and IntelliJ-using friends, and I forced them to give me live demonstrations of Java editing on large files. This is why I have so few friends. It turns out that Eclipse and IntelliJ both use asynchronous parsing as well, which made me feel better about the basic approach.

Asynchronous parsing is pretty simple in principle: when the user is typing, don't do anything. Just let 'em type. When they stop, start a timer for, say, a 200 to 500 millisecond delay, and when the timer expires, start parsing. Every once in a while, see if they typed anything. If so, stop parsing and let them type.

The main downside of this approach is that for some programmers, the 500-ms timer fires between every keystroke, so the file never actually finishes parsing. (Yes, that was a mean joke. I have a blog on this subject coming up; I'm declaring war on people too lazy to learn to type.)

Actually, now that I think about it, I did mention my change of heart (and asynchronous approach) to Brendan a week or two ago, and he jumped immediately to the smart-guy conclusion: I need continuations. Fortunately I'd thought of this, albeit not in the 200 milliseconds it took him to arrive at that conclusion (over wine, no less!), so I was able to retort: "um, yeah... it's in my to-do list. Right now I hack it."

And hack it I do! I rely on the fact that my parser does 5000 lines a second, so if the parse gets interrupted, at some point even the fastest, most dedicated typist will have to pause for a second, and I'll finish the parse (which in turn finishes the highlighting and error/warning reporting – see below).

Unfortunately (as Brendan instantaneously concluded), this means that if the parse gets 99.9% complete, and you hit the up-arrow, it abandons the entire parse (and parse tree built so far), starting from scratch again when Emacs goes idle. So if you open a big file (like prototype.js) and start navigating around it, you may not see any results until you stop typing or scrolling.

The proper fix will be to record where I'm at, and pick up where I left off when I restart the parse. That's what nxml-mode does, but I'm forced to concede that James Clark is way cooler than I am. If you have a multi-threaded system, then it's trivial, and if your system supports continuations, it's also trivial. But Emacs has neither of these.

Instead, I pause every 100 statements or so (this is a lame heuristic, I agree) and check for user input. Since I'm pausing at the top level of the parser, in the loop where it consumes whole statements, I really don't need to store that much information to fake a continuation, so this problem is eminently fixable.

But I had to release this thing eventually, which meant drawing the line somewhere. So for now it has asynchronous full-restart parsing. This means that as you edit the file, just like in Eclipse and IntelliJ, it can take a second or two for the parser to catch up with you after you pause.

It doesn't (or shouldn't) interfere with your editing, though, so hopefully this isn't a big issue.

Missing highlighting

It's on my js2-mode TODO list to highlight E4X literals. E4X is a JavaScript language extension (an official Ecma standard, in fact) that allows you to embed XML literals in your JavaScript code and provides various XML operators and functions that let you do DOM-style manipulations and XPath-style queries, but with JavaScript-style syntax and semantics.

I parse these properly, but don't highlight them yet. The Rhino parser just parses them as strings, so to get more accuracy I'll need to make my own little XML parser. It must (I think) be my own little parser because E4X permits embedding arbitrary JavaScript expressions in curly-braces as a form of templating. This complicates the XML parsing because you can find one or more {javascript-expr} expressions in the middle of any XML element name, attribute name, attribute value, text node, or just about anywhere else that doesn't cross a quote or angle-bracket boundary.

I'll get around to it eventually.

Indentation

I would have been publishing this article at least a month ago if it weren't for indentation. No, six weeks, mininum.

See, I thought that since I had gone to all the thousands of lines of effort to produce a strongly-typed AST (abstract syntax tree) for JavaScript, it should therefore be really easy to do indentation. The AST tells me exactly what the syntax is at any given point in the buffer, so how hard could it be?

It turns out to be, oh, about fifty times harder than incremental parsing. Surprise!

Just to give you a feel for the size of the problem, the package cc-engine (including its cc-* helper packages) bundled with GNU Emacs 22 is approximately 27,000 lines of lisp code, and it's all dedicated to indentation. There's a teeny tiny smattering of maybe 500 lines dedicated to filling, and sure, it supports several C-like languages, but let's face it: 25k lines for indenting? 27k lines of Lisp code? (Meaning it would be, like, five times that much Java?)

What the hell is so hard about indentation?

For starters, in order to provide user-configurable indentation for every possible syntactic context, you need to name all the syntactic contexts. cc-engine defines about 70 syntactic positions in a data structure called c-offsets-alist. This is a map of {context-name : indent-level}, where indent-level can be a number (a multiple of the variable c-basic-offset), or a symbol specifying some multiple of c-basic-offset, or even a function to call to figure out how to indent.

It's pretty darn flexible. And people still complain about it! Apparently 70 different syntactic contexts isn't enough to let you specify your indentation exactly the way you like it.

Anyhoo, most existing JavaScript editing modes for Emacs use cc-engine and try to coerce it into indenting JavaScript properly. This usually meets with lackluster results, since JavaScript is gradually drifting further and further from C. So is Java, but someone actually bothers to try to keep cc-engine up to date for Java.

Here's the deal: the cc-engine code for interpreting that c-offsets-alist data structure (with all the indentation configuration options) is pretty small. Most of the code goes to parsing and trying to figure out the current syntactic context.

You can probably guess what I tried to do. I wanted to let people customize their js2-mode indentation much the same way they can customize their c-mode or java-mode indentation, using c-offsets-alist. So I figured I'd use the exact same configuration data structure, and use my parse tree to replace c-guess-basic-syntax (and the 25k lines of lisp code for implementing it!)

(time passes...)

Approximately one month later, I threw in the towel. I renamed my js2-indent.el to doomed-indent.el, and my js2-indent-test.el unit-test file to doomed-indent-test.el, and gave up on this approach for the forseeable future. 1500 lines of painfully crafted lisp code down the drain.

Ugh. Sure, it was only a few hours a week, but it still felt like a lot of work. And it was a lot of calendar time.

Amazingly, surprisingly, counterintuitively, the indentation problem is almost totally orthogonal to parsing and syntax validation. I'd never have guessed it. But for indentation you care about totally different things that don't matter at all to parsers. Say you have a JavaScript argument list: it's just (blah, blah, blah): a paren-delimited, comma-separated, possibly empty list of identifiers. Parsing that is pretty easy. But for indentation purposes, that list is rife with possibility! You might want to indent it like this:

(blah,
  blah, blah)

or this:

(
  blah,
  blah,
  blah)

or this:

(blah,
      blah,
      blah)

or this:

(
      blah,
      blah, blah)

Let's face it: you could be a total lunatic, and Emacs has to make you happy. So instead of simply parsing a plain argument list, you need to determine and capture the (a) the fact that it looks like an argument list, (b) the position and indentation of the open-paren, (c) whether the cursor is before or after the open-paren, (d) whether the arg list is nonempty, (e) whether the cursor is before the first list element, (f) whether the cursor is on the line containing the closing paren, (g) whether there are any block or single-line comments interspersed between any of the list elements or parentheses, (h) whether the AAAAUGH, I can't stand it anymore!

The problem is, this explosion of "one case to arbitrarily many cases" occurs for every single grammatical construct in your language. So if you have 70-ish such constructs (as JavaScript does - Java has almost double that, because of the type system), and each one expands to 5 to 10 possible indentation situations, well, you've got an awful lot of edge cases to deal with.

Worse, having a rich AST doesn't help you much. You can figure out that it's an argument list, and possibly where the cursor is in the list, but you still have to grope around in the buffer looking for other contextual cues that matter for indentation but which the parser threw away. So each syntactic case in the 700-odd scenarios I had to handle expanded to anywhere from 2 to 10 lines of lisp code.

I was about 1500 lines into my doomed-indent.el (plus unit tests), and maybe (optimistically) 35% finished, when it occurred to me: "is there a better way?"

Karl Angalsdkjfadslkfj to the rescue

I remembered that there are several javascript editing modes out there already, and none of them does a very good job (or I wouldn't be working on js2-mode). But one of them, "javascript.el", I remembered as being pretty good at indentation. It wasn't perfect, and I'd had to write some custom hacks for it here and there, but it was actually pretty decent. How did it work?

I went and looked at it. It's written by a guy named, according to the comment header, Karl Landström. I'd always assumed that this was just some my-font-doesn't-support-Unicode gobbledygook, and that his name was actually something more reasonable like Karl Landstr\301^HB^P\302\301!\204^0^@. But upon closer inspection, I think he may be a fan of the artist formerly known as the artist formerly known as Prince, aka "Prince", because the "ö" in his name shows up pretty consistently across platforms and fonts. So it may be intentional. Perhaps his parents were ardent mathematicians.

In any case, Karl Landstrlaksjdflaksjd is an amazingly clever guy, because his indenter, which beats the pants off all the JavaScript modes based on cc-engine, is only about 200 lines of elisp. 200!? How does he do it?

Well, in a nutshell, he makes the inspired assumption that indentation is almost always a function of brace/paren/curly nesting level, and he uses a little-known built-in Emacs function called parse-partial-sexp, written in C, which tells you the current nesting level of not only braces, parens and curlies, but also of c-style block comments, and whether you're inside a single- or double-quoted string. How useful! Good thing JavaScript uses C-like syntax, or that function would have been far less relevant.

The rest of his code handles cases where you have a JavaScript keyword such as if, while or finally (a "possibly braceless keyword"), where you can optionally leave off the curly-brace, and it should still indent one basic step for the nested statement.

The results are actually pretty darn good, and assuming you're reasonably flexible about where you position your parens and curly-braces, you can exert at least some control over the indentation. (E.g. you can move a curly down to its own line and manually indent it, and subsequent lines will indent from that curly.)

Go Karl!

Unfortunately, it's not perfect (no solution so elegant could ever be, at least for a language based on the inelegant syntax of C), so I was faced with a dilemma: should I pile hack upon hack until it becomes the new cc-engine? Or is there another way?

Well, I've always been vaguely admiring of python-mode's Emacs indentation, which chooses among various likely indentation points when you press TAB repeatedly. Why not use that approach for JavaScript?

So that's what I wound up doing. I put a few tweaks into Karl's original indenter code to handle JavaScript 1.7 situations such as array comprehensions, and then wrote a "bounce indenter" that cycles among N precomputed indentation points.

For any given line, there are some obvious possible indentation points:

- whatever position Karl's guesser wants to use
- the beginning of the line
- after the '=' if the previous line is an assignment
- same indentation as the previous line
- first preceding line with less indentation than the preceding line

I wrote a function that computes all these positions, based on heuristic parsing (NOT on my AST, which might not even be available yet if the parse is taking a while), and the TAB key cycles among them.

This moved the accuracy, at least for my own JavaScript editing, from 90% accurate with Karl's mode up to 99.x% accurate, assuming you're willing to hit TAB multiple times for certain syntactic contexts.

There are still plenty of user-defined situations (e.g. parts of Google's internal JavaScript style guide) that my guesser doesn't compute. You don't want to compute every possible indentation point, or the TAB key degenerates into the space key modulo the line length, so at some point I'll add a customization hook that lets you write a function to help decide the right indentation.

Anyway, where was I. Oh yeah. Indentation is a real pain in the b-hind. I'm glad to be (mostly) done with it. At least hopefully you now understand why my mode isn't configurable the way other C-like modes are, and you sympathize with me. Next time I have time to write ten thousand lines of indentation-related guessing, I'll fix it.

Meanwhile, if you find points where it doesn't do what you want, let me know (or post them on the Wiki), and I'll either hack them in or write that customization hook.

Other Stuff

I didn't expect to spend so long on just syntax highlighting and indentation. It's just the beginning! Unfortunately I'm out of patience, and I'm guessing you are too. So here's a short list of other features.

Code folding

I support hiding function bodies and /*...*/ block comments as {...}. It's in the menu. Turn on menu-bar-mode, or right-click in the buffer, to invoke these functions.

At some point I'll generalize it to hiding any curly-brace construct, the way Eclipse does. This was just an experiment to see how easy it would be. (Answer: pretty easy! Emacs has good built-in support for this kind of thing.)

Comment and string filling

One neat trick I stole from Eclipse: if you hit <Enter> inside a string literal, it will autoamtically turn it into a multi-line string concatenation.

You can also hit Alt-q (fill-paragraph) inside a comment or a string to see hopefully useful things happen. Let me know if it doesn't do what you expect.

Syntax errors

The mode highlights syntax errors in red. This can be annoying as you type, but I'm told (by Eclipse/IntelliJ users) that you get used to it.

You can control this behavior via a customization variable.

Strict warnings

JavaScript defines a whole bunch of strict-mode warnings: things like "don't have a trailing comma in an Array or Object literal", or "your variable name conflicts with one of the function parameters". I've implemented some of them, with more to come. They get underlined in orange.

I actually found some bugs in live code I'd written with this feature. Pretty cool!

jsdoc highlighting

There's a program similar to javadoc called "jsdoc" that lets you do documentation comments for your JavaScript functions and other declarations. It defines a similar set of @whatever tags. We use it at Google, albeit with limited success because it's a Perl program that core-dumps on most of our JavaScript code base. My mode highlights the various tags in jsdoc comments, if you happen to use them.

It's possible that you'll notice it highlighting curly-brace constructs inside jsdoc comments, such as:

@return {SomeType} my return value

Googler Bob Jervis has written a type-inferencing engine for our JSCompiler, in his 20% time, that uses the type-tags we've defined in an enhanced version of jsdoc comments. It's still pretty new, and we're planning to open-source it and integrate it with Mozilla Rhino at some point, but since it's 20% time, there's no telling when it'll be released. But hopefully that'll explain the bizarre highlighting you might sometimes see.

If this isn't good enough for you...

Well, you have three options.

First, you can whine about it. If you whine in the appropriate places, such as the Wiki, then I'll eventually notice and try to fix whatever it is that's bothering you.

Next, you can offer to help. I haven't uploaded the original source code, but I can certainly start doing so. (The file js2-<datestamp>.el is generated from a little build script I wrote, to make installation easier.) If you're a good Emacs-Lisp programmer, and you want to help make this mode better, let me know and we can get you hooked up!

Finally, if you can afford it (or if your company can afford it), consider using IntellIJ IDEA. Yes, it's commercial, but if you spend even 30 seconds on their site it becomes apparent that "commercial" means "better". Their JavaScript support is way better than mine, and is as far as I can tell the gold standard for JavaScript editing today.

Eventually I hope to be able to reach feature parity with IntelliJ, and it's certainly possible, but it'll be some work. In the meantime, if you can't wait, give them a try!

Wrap-Up

At this point I have to go to the bathroom so bad that I don't care what other features I've added. You can look at the Wiki!

If you habitually (or even occasionally) use GNU Emacs to edit JavaScript, please give this mode a try! It's probably got a fair number of bugs and usability issues, since it's brand-new, but it'll improve more quickly if you play guinea pig for a while.

Feel free to email me directly with comments, suggestions, or bug reports, or you can go to the Wiki and add your comments there.

Enjoy!

Four console games you might like...

I only play a handful of games a year, so I haven't written a game review since my post on Oblivion a year ago. But since then I've played a few unusually good games, including one awesome PS/3 title last weekend, so I figured it's time for another review.

First, here's my gamer profile, so you can decide now whether reading any further is worth your time. I'm a console guy. I don't play games on a PC because I want the whole big-screen, comfy-couch immersion experience. Some of my favorite games in the past include Final Fantasy X, the Zelda franchise, the Mario franchise, Morrowind and Oblivion, Fable, Doom and Doom II (but not Quake or Unreal), and Donkey Kong 64. So there ya go. That's the kind of game I like. Adventure and RPG games, mostly, and FPS types only if they have sufficient atmosphere.

Here's the memorable stuff I've played lately.

Portal

Everyone's been buzzing about this Xbox-360 game: they all say you've gotta play it, really cool gameplay, blah blah blah, and to be honest it sounded boring as hell. Plus it's only available through a 3-game title called The Orange Box, and the other games on it don't interest me.

A friend of mine finally bought me the game, came over, and sat there and glared at me until I played it. That's one way to do it!

Summary: it rocks. Great gameplay, new game dynamics, genuinely funny storyline, and an unexpectedly cool ending song that's easy to play, if you happen to be a guitarist.

I stayed up all night and finished the game in one sitting, so it's not very long at all. Only takes about 90 minutes the second time through, maybe. I recommend playing it through a second time with the developer commentary turned on, especially if you're a programmer or designer, since it was all really interesting stuff.

The plot summary is pretty simple. You have to take a series of increasingly complex tests using a "portal gun" that can shoot linked orange and blue portals onto horizontal surfaces. Jumping through either portal shoots you out the other one, maintaining your momentum, which makes for some really cool suicide-jump situations and a whole lot of different puzzle types. A female computer voice messes with you throughout the tests. At the end of the last test, things go south, and you have to escape into the guts of the test facility, crawling through ducts and messy industrial back-rooms, to find the computer and destroy it. It's really the second half of the game that's the fun part; you have to use everything you learned during the testing phase and solve some tricky puzzles while not getting shot, falling into toxic waste, or dying in any number of other exciting ways.

The game is more or less flawless in its execution: it was smooth, well-designed, bug-free, and it stayed interesting without ever getting frustrating. It was a little masterpiece. Can't wait for the sequel.

Mario Galaxy

I asked my friend Andrew Wilson if he has a Wii yet, and he retorted: "NO, because I'm a grown-up!" Funny stuff. I'm assuming his wife won't let him buy one.

If you don't have a Wii, well, you're missing out. It's far from perfect – in fact the device itself is pretty weak, and is missing HD output, bluetooth and a number of other pretty important things. But its controllers really blow conventional controllers away. I've played one FPS on the Wii (Metroid Prime 3), and although the game itself was IMO a bit borderline, the controls were amazing. Going back to the XBox 360 or Playstation controllers feels totally rinky-dink, like I've traveled back to the 1980s and I'm using an Atari Joystick.

Plus it's actually true that non-gamers like the Wii, and the multiplayer party games wind up being a lot more fun than they are on other consoles. You can work up quite a sweat trying to beat the crap out of people in boxing matches or outrun them in olympic games. Fun stuff.

Anyway, I'd been kind of reluctant to play Super Mario Galaxy. Every time I saw someone playing it in a game store, they'd be running around teeny tiny planets like the ones in that book The Little Prince, and it looked like it was going to be absolutely nauseating. And I mean literally nauseating, in the motion-sickness sense. It just didn't look anywhere near as fun as previous classic Mario titles (Mario 64 comes to mind – I just replayed that on my Nintendo DS and loved it just as much as ten years ago.)

But I figured I'd give it a try, and boy, was I wrong about it. Mario Galaxy is arguably the best Mario title since the original Super Mario Bros. arcade game. Nintendo just nailed it, across the board: well-balanced gameplay with lots of variety, superb level design, gorgeous sets, and probably the best music ever from a Mario franchise game – check out this orchestra recording the Gusty Garden Galaxy Theme, for instance. It's just one of several equally awesome pieces written for the game. (I also particularly liked the Good Egg Galaxy theme, the "Teresa Waltz" in the Ghostly Galaxy, the Bowser Battle music, the Buoy Base theme, and the Disney-esque Observatory waltz. But almost all the music was worth listening to, and I can't wait until the soundtrack is available.)

The game has oodles of atmosphere. You can practically feel the wind in the Gusty Garden Galaxy. You can almost smell the honey in the Honeyhive Galaxy. In the Beach Bowl you feel the sun on your back and smell the surf. It's really weird, actually – I've never played a game before that made it feel like all five senses were in play the way this game does.

I experienced none of the motion-sickness or discomfort I had been dreading. You get used to the gravity surprisingly fast, and before long it doesn't matter what combination of camera angle and orientation you happen to have active – you just keep on running, jumping, and smashing things, upside-down and backwards. It's the most truly three-dimensional game environment I've ever played.

My favorite part of the game, which I played over and over just for the effect, was probably the first Battlerock level. The music is reminiscent of Mars from Holst's The Planets, and builds up steadily while you make your way towards this huge rock in the distance. As you get closer you realize it's sort of like the Death Star, and it's shooting at you like mad as the music builds to a climax. Great level!

One of the big turn-offs for me in the Mario and Zelda franchises has been overly-tough boss battles. I think Twilight Princess and Mario Galaxy have both finally dialed it right: the boss fights can be challenging but are achievable without having to take a two-hour time-out from the plotline just to practice some crazy move, as has been the case in so many past titles.

Anyway, the game made a fanboy out of me, so, you know, take all this with a grain of salt. You might like it, you might not. I thought it was great.

Zelda Twilight Princess

I played Twilight Princess last year – I can't remember exactly when, but it feels like a long time ago. Great game, though; if you haven't played it and you like the genre, you need to get your hands on a GameCube or a Wii. I played TP on my old GameCube, since it was before I owned a Wii, and I was highly skeptical of the Wii controls for that kind of game, at the time. I couldn't imagine holding my arm out for ten minutes trying to keep my bow steady. (This was long before I learned that the Wii controls often work best when your wrists and elbows are on the couch and you're just flicking the Wiimotes around like laser pointers.)

I originally wasn't going to write a long review of this game, since it's not exactly making news headlines anymore. I did think it was just as good as Ocarina of Time and Wind Waker, but not any better. In fact, I think I might have enjoyed Wind Waker a little more than Twilight Princess. That said, TP was one of the best games of the past ten years, and had some truly groundbreaking gameplay and atmospheric elements.

The more I think about it, the more I'm remembering how much fun I had with it. So it gets a spot in my most-recommended list for the past year.

A few scenes still stand out after nearly a year. Flying the big Nazgul-mount-ish monster upriver while getting shot at from the banks played like a scene out of Peter Jackson's Lord of the Rings. The minigame in the canoe coming back downriver was loads of fun. The burning bridge and fall into Lake Hylia were really cool. Searching for bugs for that wacked-out little girl was... weird, but fun. The horseback riding and combat were both completely new and exciting. And I just about died laughing when I wrecked my first wild boar.

The game has an eerie and heartrending central climax, "Midna's Desperate Hour." You're stuck in wolf form, carrying your dying friend Midna to the castle to try to save her while some really sad music plays, and it just goes from bad to worse. You start off having to run through town in broad daylight as a wolf for the first time, and the townspeople are all running from you screaming in horror, which doesn't make you feel any better about the situation. Then you have to make your way across the most bleak, windswept rooftops imaginable, buffeted by this sort of ash-storm, and then, well, let's just say they're setting you up to stab your heart out when you get to the castle. It's pretty agonizing. The mood does eventually pick up, though, and eventually you do beat the bad guy and save the day.

If you haven't played it, you should give it a try. In some sense it's just another Zelda game with all the expected elements, including lonely temples filled with puzzles, little towns filled with bizarre characters, the usual power-ups and mini-games, and the classic heart-container scheme. But it gets major points for having a dramatic sweep and story-arc not really present in previous Zelda titles. It's also got much more achievable boss battles, so you can finish the game without ever getting insanely frustrated.

Now I'm making myself want to go back and play it again, so I'll shut up about it.

Uncharted: Drake's Fortune

I just played Drake's Fortune last weekend. It's the reason I wrote this blog entry, actually. In my humble and totally biased fanboy opinion, you should run out and buy it right now, along with a PS/3 and a bigger TV.

I saw a commercial for the game last year and thought: "Hey, that almost looks like a game that could induce me to buy a Playstation 3. Almost." But I was worried about the whole Blu-Ray vs. HD-DVD thing, and PS/3s used to be kind of steep (they were, what, like six hundred bucks initially?), and I just kinda dragged my feet on the whole issue forever, as I suspect most of you have been doing.

Then Blu-Ray won the war a couple weeks ago, all rather suddenly and unexpectedly, and I thought, hey, this might be a good time to replace my ancient TV and get myself a PS/3, so I can finally drag myself out of the non-HD dark ages. So I went big-screen shopping, and unlike for every other TV I've bought in the past, I decided not to cheap out this time. I wound up buying a Panasonic 58" 1080p plasma HDTV, which after lots of research and staring at screens in stores, narrowly beat out the Sony Bravia XBR4 52" 1080p LCD HDTV. They're both great products, but the plasma still beats the LCD for gaming.

The 58-inch plasma is jaw-droppingly awesome. I replaced my Comcast box with one of their HD-DVRs, and it works great but has almost no space for recording shows, so at some point I'll probably have to pick up an HD Tivo. It's too bad, really, since I have the lifetime-membership Tivo, and I'll almost certainly have to switch to paying a monthly fee if I upgrade to the HD version, since I missed the promotion window when they came out. But you really do need the extra space, so the Comcast one is going to have to go. In the meantime, the HD channels look great, and they only cost me about ten bucks more than the package I already had, so it was well worth it.

Let me tell you: nothing, nothing I've seen so far on my new screen, not Blu-Ray discs, not HD channels, not Oblivion on the XBox 360, nothing can compare to the visual feast provided by Drake's Fortune. It's reportedly only 720p, but it looks like it's 1080p and then some. I took a bunch of pictures of it while I was playing, cheesy ones on my iphone that I'm embarrassed to upload, but it had so many stop-and-stare areas that I just kept taking pics.

Anyway, visuals aside, the game itself is sort of a cross between Tomb Raider (the original, which was pretty fun) and Gears of War, which I've never played, but people say Drake's Fortune has similar combat mechanics. And it's a bit like the recent horror movie The Descent towards the end. Yeah. I didn't see that element coming, but it was pretty darn cool. And scary.

The game is short and linear: an interactive movie, essentially. I took my time with it and still finished in about 13 hours. There are some puzzles, but not too many, and none of them are even remotely difficult to figure out. Which is good, I suppose; in my old age I don't like to spend too long on any one puzzle, so I'm pretty quick to go look online for hints if I get stuck. Didn't have to do that for this game, which helped increase the immersiveness.

The game starts off a little slow, to be honest, and after the first hour I was starting to worry that it would suck. You have to stick it out until you parachute onto the second island, after which it gradually picks up the pace until it feels like it's a flat-out race to the finish.

Most of the game, especially the latter half, revolves around the combat, nearly all of which is against modern-day pirates. You have to get good at ducking behind walls and fast aiming to have a hope of surviving (although trust me on this one, if a non-FPS gamer like me can master it in a few hours, you can too). I found the combat to be loads of fun, and I'm getting ready to play the game through again just for that. You run across a good selection of weapons, including a nifty Dragon Sniper rifle, and you have to make tough decisions about what to carry with you since you've got limited inventory space: one handgun and one rifle or shotgun, basically, plus a little ammo.

The voice acting is really good, much better than it was in Oblivion, although I'm sure it was easier since the game is shorter and there are fewer characters. The lines are a little cheesy at first, but either the writing got better as the game progressed, or I just got used to it. Either way, by mid-game it felt pretty believable. In fact I laughed a lot at the characters' reactions. The main character, uh, mumble Drake, I forget his first name, says exactly what I would have said, the first time a grenade lands next to him. It's not repeatable here. The swearing/profanity in the game isn't over-the-top, but they use it effectively now and then for humor value.

The AIs are great, and for a lot of the game you've got at least one friend following you around and helping you fight stuff or solve puzzles. They almost feel like real people, and they're nowhere near the nuisances NPC helpers have been in hundreds of games in the past.

The generator-room sequence is just plain scary. I've played scarier games, sure – Fatal Frame comes to mind – but this one really had my pulse going towards the end of the game. For an hour, at least, until I finally made it out of there. I'm lucky I didn't keel over.

There are a few fast-paced movie-like combat sequences thrown in. There's one especially memorable scene where you're riding shotgun in a Jeep, and you have to shoot at bad guys coming after you while you're racing through the jungle. Cool stuff. The whole feel of the game is very Indiana Jones, actually. Naughty Dog did a great job with it across the board.

And the visuals – well, they simply defy any possibility of describing them here. Steaming tropical jungles, crumbling Spanish fortresses, foamy waves crashing against the rocks a hundred feet below you, realistic character motion and rendering – the game is sumptuous, no better word for it.

You really have to play this game. You only need to set aside one day for it, so you might as well check it out!

Some final thoughts

I pretty much bought my XBox 360 for Oblivion, although it wound up being my DVD player for a couple years after my Sony player died. It didn't matter, though, since Oblivion was good enough to warrant the purchase of an XBox 360. And I did find one or two other 360 titles that were fun (e.g. Kameo: Elements of Power, a fun but short romp from ex-Rareware, my ex-favorite game studio.) I'm hanging on to my 360 specifically so I can play Fable 2 this holiday season. The original Fable was lots of fun, and had a cool werewolf scene I'll remember to my dying day. I hope the sequel is every bit as good.

But I'm clearly someone who doesn't need much incentive to buy a game console.

I pretty much bought my PS/3 for Drake's Fortune, hoping it would be worth it, although it's also nice to have a Blu-Ray player. I'd have to say Drake's Fortune doesn't singlehandedly justify the purchase of a PS/3 for gaming purposes, but it does illustrate the potential of the platform, and I think there are tons of great titles to come. For a while most of the good games are likely to be ports that are also available on the 360, but they say the PS/3 has a lot more parallel-processing power, so as game developers learn to take advantage of it I'm guessing the PS/3 eventually gets the edge.

It's still early-adopter material, though, so if you already own a Blu-Ray player, a PS/3 may not be worth it this year. Drake's Fortune will still be a fun game next year, and will be a lot cheaper than its current $60 price tag.

And with that, it's a wrap! Looking forward to seeing your game suggestions in the comments.

Get that job at Google

I've been meaning to write up some tips on interviewing at Google for a good long time now. I keep putting it off, though, because it's going to make you mad. Probably. For some statistical definition of "you", it's very likely to upset you.

Why? Because... well, here, I wrote a little ditty about it:

Hey man, I don't know that stuff
Stevey's talking aboooooout
If my boss thinks it's important
I'm gonna get fiiiiiiiiiired
Oooh yeah baaaby baaaay-beeeeee....

I didn't realize this was such a typical reaction back when I first started writing about interviewing, way back at other companies. Boy-o-howdy did I find out in a hurry.

See, it goes like this:

Me: blah blah blah, I like asking question X in interviews, blah blah blah...

You: Question X? Oh man, I haven't heard about X since college! I've never needed it for my job! He asks that in interviews? But that means someone out there thinks it's important to know, and, and... I don't know it! If they detect my ignorance, not only will I be summarily fired for incompetence without so much as a thank-you, I will also be unemployable by people who ask question X! If people listen to Stevey, that will be everyone! I will become homeless and destitute! For not knowing something I've never needed before! This is horrible! I would attack X itself, except that I do not want to pick up a book and figure enough out about it to discredit it. Clearly I must yell a lot about how stupid Stevey is so that nobody will listen to him!

Me: So in conclusion, blah blah... huh? Did you say "fired"? "Destitute?" What are you talking about?

You: Aaaaaaauuuggh!!! *stab* *stab* *stab*

Me: That's it. I'm never talking about interviewing again.

It doesn't matter what X is, either. It's arbitrary. I could say: "I really enjoy asking the candidate (their name) in interviews", and people would still freak out, on account of insecurity about either interviewing in general or their knowledge of their own name, hopefully the former.

But THEN, time passes, and interview candidates come and go, and we always wind up saying: "Gosh, we sure wish that obviously smart person had prepared a little better for his or her interviews. Is there any way we can help future candidates out with some tips?"

And then nobody actually does anything, because we're all afraid of getting stabbed violently by People Who Don't Know X.

I considered giving out a set of tips in which I actually use variable names like X, rather than real subjects, but decided that in the resultant vacuum, everyone would get upset. Otherwise that approach seemed pretty good, as long as I published under a pseudonym.

In the end, people really need the tips, regardless of how many feelings get hurt along the way. So rather than skirt around the issues, I'm going to give you a few mandatory substitutions for X along with a fair amount of general interview-prep information.

Caveats and Disclaimers

This blog is not endorsed by Google. Google doesn't know I'm publishing these tips. It's just between you and me, OK? Don't tell them I prepped you. Just go kick ass on your interviews and we'll be square.

I'm only talking about general software engineering positions, and interviews for those positions.

These tips are actually generic; there's nothing specific to Google vs. any other software company. I could have been writing these tips about my first software job 20 years ago. That implies that these tips are also timeless, at least for the span of our careers.

These tips obviously won't get you a job on their own. My hope is that by following them you will perform your very best during the interviews.

Oh, and um, why Google?

Oho! Why Google, you ask? Well let's just have that dialog right up front, shall we?

You: Should I work at Google? Is it all they say it is, and more? Will I be serenely happy there? Should I apply immediately?

Me: Yes.

You: To which ques... wait, what do you mean by "Yes?" I didn't even say who I am!

Me: Dude, the answer is Yes. (You may be a woman, but I'm still calling you Dude.)

You: But... but... I am paralyzed by inertia! And I feel a certain comfort level at my current company, or at least I have become relatively inured to the discomfort. I know people here and nobody at Google! I would have to learn Google's build system and technology and stuff! I have no credibility, no reputation there – I would have to start over virtually from scratch! I waited too long, there's no upside! I'm afraaaaaaid!

Me: DUDE. The answer is Yes already, OK? It's an invariant. Everyone else who came to Google was in the exact same position as you are, modulo a handful of famous people with beards that put Gandalf's to shame, but they're a very tiny minority. Everyone who applied had the same reasons for not applying as you do. And everyone here says: "GOSH, I SURE AM HAPPY I CAME HERE!" So just apply already. But prep first.

You: But what if I get a mistrial? I might be smart and qualified, but for some random reason I may do poorly in the interviews and not get an offer! That would be a huge blow to my ego! I would rather pass up the opportunity altogether than have a chance of failure!

Me: Yeah, that's at least partly true. Heck, I kinda didn't make it in on my first attempt, but I begged like a street dog until they gave me a second round of interviews. I caught them in a weak moment. And the second time around, I prepared, and did much better.

The thing is, Google has a well-known false negative rate, which means we sometimes turn away qualified people, because that's considered better than sometimes hiring unqualified people. This is actually an industry-wide thing, but the dial gets turned differently at different companies. At Google the false-negative rate is pretty high. I don't know what it is, but I do know a lot of smart, qualified people who've not made it through our interviews. It's a bummer.

But the really important takeaway is this: if you don't get an offer, you may still be qualified to work here. So it needn't be a blow to your ego at all!

As far as anyone I know can tell, false negatives are completely random, and are unrelated to your skills or qualifications. They can happen from a variety of factors, including but not limited to:

1. you're having an off day
2. one or more of your interviewers is having an off day
3. there were communication issues invisible to you and/or one or more of the interviewers
4. you got unlucky and got an Interview Anti-Loop

Oh no, not the Interview Anti-Loop!

Yes, I'm afraid you have to worry about this.

What is it, you ask? Well, back when I was at Amazon, we did (and they undoubtedly still do) a LOT of soul-searching about this exact problem. We eventually concluded that every single employee E at Amazon has at least one "Interview Anti-Loop": a set of other employees S who would not hire E. The root cause is important for you to understand when you're going into interviews, so I'll tell you a little about what I've found over the years.

First, you can't tell interviewers what's important. Not at any company. Not unless they're specifically asking you for advice. You have a very narrow window of perhaps one year after an engineer graduates from college to inculcate them in the art of interviewing, after which the window closes and they believe they are a "good interviewer" and they don't need to change their questions, their question styles, their interviewing style, or their feedback style, ever again.

It's a problem. But I've had my hand bitten enough times that I just don't try anymore.

Second problem: every "experienced" interviewer has a set of pet subjects and possibly specific questions that he or she feels is an accurate gauge of a candidate's abilities. The question sets for any two interviewers can be widely different and even entirely non-overlapping.

A classic example found everywhere is: Interviewer A always asks about C++ trivia, filesystems, network protocols and discrete math. Interviewer B always asks about Java trivia, design patterns, unit testing, web frameworks, and software project management. For any given candidate with both A and B on the interview loop, A and B are likely to give very different votes. A and B would probably not even hire each other, given a chance, but they both happened to go through interviewer C, who asked them both about data structures, unix utilities, and processes versus threads, and A and B both happened to squeak by.

That's almost always what happens when you get an offer from a tech company. You just happened to squeak by. Because of the inherently flawed nature of the interviewing process, it's highly likely that someone on the loop will be unimpressed with you, even if you are Alan Turing. Especially if you're Alan Turing, in fact, since it means you obviously don't know C++.

The bottom line is, if you go to an interview at any software company, you should plan for the contingency that you might get genuinely unlucky, and wind up with one or more people from your Interview Anti-Loop on your interview loop. If this happens, you will struggle, then be told that you were not a fit at this time, and then you will feel bad. Just as long as you don't feel meta-bad, everything is OK. You should feel good that you feel bad after this happens, because hey, it means you're human.

And then you should wait 6-12 months and re-apply. That's pretty much the best solution we (or anyone else I know of) could come up with for the false-negative problem. We wipe the slate clean and start over again. There are lots of people here who got in on their second or third attempt, and they're kicking butt.

You can too.

OK, I feel better about potentially not getting hired

Good! So let's get on to those tips, then.

If you've been following along very closely, you'll have realized that I'm interviewer D. Meaning that my personal set of pet questions and topics is just my own, and it's no better or worse than anyone else's. So I can't tell you what it is, no matter how much I'd like to, because I'll offend interviewers A through X who have slightly different working sets.

Instead, I want to prep you for some general topics that I believe are shared by the majority of tech interviewers at Google-like companies. Roughly speaking, this means the company builds a lot of their own software and does a lot of distributed computing. There are other tech-company footprints, the opposite end of the spectrum being companies that outsource everything to consultants and try to use as much third-party software as possible. My tips will be useful only to the extent that the company resembles Google.

So you might as well make it Google, eh?

First, let's talk about non-technical prep.

The Warm-Up

Nobody goes into a boxing match cold. Lesson: you should bring your boxing gloves to the interview. No, wait, sorry, I mean: warm up beforehand!

How do you warm up? Basically there is short-term and long-term warming up, and you should do both.

Long-term warming up means: study and practice for a week or two before the interview. You want your mind to be in the general "mode" of problem solving on whiteboards. If you can do it on a whiteboard, every other medium (laptop, shared network document, whatever) is a cakewalk. So plan for the whiteboard.

Short-term warming up means: get lots of rest the night before, and then do intense, fast-paced warm-ups the morning of the interview.

The two best long-term warm-ups I know of are:

1) Study a data-structures and algorithms book. Why? Because it is the most likely to help you beef up on problem identification. Many interviewers are happy when you understand the broad class of question they're asking without explanation. For instance, if they ask you about coloring U.S. states in different colors, you get major bonus points if you recognize it as a graph-coloring problem, even if you don't actually remember exactly how graph-coloring works.

And if you do remember how it works, then you can probably whip through the answer pretty quickly. So your best bet, interview-prep wise, is to practice the art of recognizing that certain problem classes are best solved with certain algorithms and data structures.

My absolute favorite for this kind of interview preparation is Steven Skiena's The Algorithm Design Manual. More than any other book it helped me understand just how astonishingly commonplace (and important) graph problems are – they should be part of every working programmer's toolkit. The book also covers basic data structures and sorting algorithms, which is a nice bonus. But the gold mine is the second half of the book, which is a sort of encyclopedia of 1-pagers on zillions of useful problems and various ways to solve them, without too much detail. Almost every 1-pager has a simple picture, making it easy to remember. This is a great way to learn how to identify hundreds of problem types.

Other interviewers I know recommend Introduction to Algorithms. It's a true classic and an invaluable resource, but it will probably take you more than 2 weeks to get through it. But if you want to come into your interviews prepped, then consider deferring your application until you've made your way through that book.

2) Have a friend interview you. The friend should ask you a random interview question, and you should go write it on the board. You should keep going until it is complete, no matter how tired or lazy you feel. Do this as much as you can possibly tolerate.

I didn't do these two types of preparation before my first Google interview, and I was absolutely shocked at how bad at whiteboard coding I had become since I had last interviewed seven years prior. It's hard! And I also had forgotten a bunch of algorithms and data structures that I used to know, or at least had heard of.

Going through these exercises for a week prepped me mightily for my second round of Google interviews, and I did way, way better. It made all the difference.

As for short-term preparation, all you can really do is make sure you are as alert and warmed up as possible. Don't go in cold. Solve a few problems and read through your study books. Drink some coffee: it actually helps you think faster, believe it or not. Make sure you spend at least an hour practicing immediately before you walk into the interview. Treat it like a sports game or a music recital, or heck, an exam: if you go in warmed up you'll give your best performance.

Mental Prep

So! You're a hotshot programmer with a long list of accomplishments. Time to forget about all that and focus on interview survival.

You should go in humble, open-minded, and focused.

If you come across as arrogant, then people will question whether they want to work with you. The best way to appear arrogant is to question the validity of the interviewer's question – it really ticks them off, as I pointed out earlier on. Remember how I said you can't tell an interviewer how to interview? Well, that's especially true if you're a candidate.

So don't ask: "gosh, are algorithms really all that important? do you ever need to do that kind of thing in real life? I've never had to do that kind of stuff." You'll just get rejected, so don't say that kind of thing. Treat every question as legitimate, even if you are frustrated that you don't know the answer.

Feel free to ask for help or hints if you're stuck. Some interviewers take points off for that, but occasionally it will get you past some hurdle and give you a good performance on what would have otherwise been a horrible stony half-hour silence.

Don't say "choo choo choo" when you're "thinking".

Don't try to change the subject and answer a different question. Don't try to divert the interviewer from asking you a question by telling war stories. Don't try to bluff your interviewer. You should focus on each problem they're giving you and make your best effort to answer it fully.

Some interviewers will not ask you to write code, but they will expect you to start writing code on the whiteboard at some point during your answer. They will give you hints but won't necessarily come right out and say: "I want you to write some code on the board now." If in doubt, you should ask them if they would like to see code.

Interviewers have vastly different expectations about code. I personally don't care about syntax (unless you write something that could obviously never work in any programming language, at which point I will dive in and verify that you are not, in fact, a circus clown and that it was an honest mistake). But some interviewers are really picky about syntax, and some will even silently mark you down for missing a semicolon or a curly brace, without telling you. I think of these interviewers as – well, it's a technical term that rhymes with "bass soles", but they think of themselves as brilliant technical evaluators, and there's no way to tell them otherwise.

So ask. Ask if they care about syntax, and if they do, try to get it right. Look over your code carefully from different angles and distances. Pretend it's someone else's code and you're tasked with finding bugs in it. You'd be amazed at what you can miss when you're standing 2 feet from a whiteboard with an interviewer staring at your shoulder blades.

It's OK (and highly encouraged) to ask a few clarifying questions, and occasionally verify with the interviewer that you're on the track they want you to be on. Some interviewers will mark you down if you just jump up and start coding, even if you get the code right. They'll say you didn't think carefully first, and you're one of those "let's not do any design" type cowboys. So even if you think you know the answer to the problem, ask some questions and talk about the approach you'll take a little before diving in.

On the flip side, don't take too long before actually solving the problem, or some interviewers will give you a delay-of-game penalty. Try to move (and write) quickly, since often interviewers want to get through more than one question during the interview, and if you solve the first one too slowly then they'll be out of time. They'll mark you down because they couldn't get a full picture of your skills. The benefit of the doubt is rarely given in interviewing.

One last non-technical tip: bring your own whiteboard dry-erase markers. They sell pencil-thin ones at office supply stores, whereas most companies (including Google) tend to stock the fat kind. The thin ones turn your whiteboard from a 480i standard-definition tube into a 58-inch 1080p HD plasma screen. You need all the help you can get, and free whiteboard space is a real blessing.

You should also practice whiteboard space-management skills, such as not starting on the right and coding down into the lower-right corner in Teeny Unreadable Font. Your interviewer will not be impressed. Amusingly, although it always irks me when people do this, I did it during my interviews, too. Just be aware of it!

Oh, and don't let the marker dry out while you're standing there waving it. I'm tellin' ya: you want minimal distractions during the interview, and that one is surprisingly common.

OK, that should be good for non-tech tips. On to X, for some value of X! Don't stab me!

Tech Prep Tips

The best tip is: go get a computer science degree. The more computer science you have, the better. You don't have to have a CS degree, but it helps. It doesn't have to be an advanced degree, but that helps too.

However, you're probably thinking of applying to Google a little sooner than 2 to 8 years from now, so here are some shorter-term tips for you.

Algorithm Complexity: you need to know Big-O. It's a must. If you struggle with basic big-O complexity analysis, then you are almost guaranteed not to get hired. It's, like, one chapter in the beginning of one theory of computation book, so just go read it. You can do it.

Sorting: know how to sort. Don't do bubble-sort. You should know the details of at least one n*log(n) sorting algorithm, preferably two (say, quicksort and merge sort). Merge sort can be highly useful in situations where quicksort is impractical, so take a look at it.

For God's sake, don't try sorting a linked list during the interview.

Hashtables: hashtables are arguably the single most important data structure known to mankind. You absolutely have to know how they work. Again, it's like one chapter in one data structures book, so just go read about them. You should be able to implement one using only arrays in your favorite language, in about the space of one interview.

Trees: you should know about trees. I'm tellin' ya: this is basic stuff, and it's embarrassing to bring it up, but some of you out there don't know basic tree construction, traversal and manipulation algorithms. You should be familiar with binary trees, n-ary trees, and trie-trees at the very very least. Trees are probably the best source of practice problems for your long-term warmup exercises.

You should be familiar with at least one flavor of balanced binary tree, whether it's a red/black tree, a splay tree or an AVL tree. You should actually know how it's implemented.

You should know about tree traversal algorithms: BFS and DFS, and know the difference between inorder, postorder and preorder.

You might not use trees much day-to-day, but if so, it's because you're avoiding tree problems. You won't need to do that anymore once you know how they work. Study up!

Graphs

Graphs are, like, really really important. More than you think. Even if you already think they're important, it's probably more than you think.

There are three basic ways to represent a graph in memory (objects and pointers, matrix, and adjacency list), and you should familiarize yourself with each representation and its pros and cons.

You should know the basic graph traversal algorithms: breadth-first search and depth-first search. You should know their computational complexity, their tradeoffs, and how to implement them in real code.

You should try to study up on fancier algorithms, such as Dijkstra and A*, if you get a chance. They're really great for just about anything, from game programming to distributed computing to you name it. You should know them.

Whenever someone gives you a problem, think graphs. They are the most fundamental and flexible way of representing any kind of a relationship, so it's about a 50-50 shot that any interesting design problem has a graph involved in it. Make absolutely sure you can't think of a way to solve it using graphs before moving on to other solution types. This tip is important!

Other data structures

You should study up on as many other data structures and algorithms as you can fit in that big noggin of yours. You should especially know about the most famous classes of NP-complete problems, such as traveling salesman and the knapsack problem, and be able to recognize them when an interviewer asks you them in disguise.

You should find out what NP-complete means.

Basically, hit that data structures book hard, and try to retain as much of it as you can, and you can't go wrong.

Math

Some interviewers ask basic discrete math questions. This is more prevalent at Google than at other places I've been, and I consider it a Good Thing, even though I'm not particularly good at discrete math. We're surrounded by counting problems, probability problems, and other Discrete Math 101 situations, and those innumerate among us blithely hack around them without knowing what we're doing.

Don't get mad if the interviewer asks math questions. Do your best. Your best will be a heck of a lot better if you spend some time before the interview refreshing your memory on (or teaching yourself) the essentials of combinatorics and probability. You should be familiar with n-choose-k problems and their ilk – the more the better.

I know, I know, you're short on time. But this tip can really help make the difference between a "we're not sure" and a "let's hire her". And it's actually not all that bad – discrete math doesn't use much of the high-school math you studied and forgot. It starts back with elementary-school math and builds up from there, so you can probably pick up what you need for interviews in a couple of days of intense study.

Sadly, I don't have a good recommendation for a Discrete Math book, so if you do, please mention it in the comments. Thanks.

Operating Systems

This is just a plug, from me, for you to know about processes, threads and concurrency issues. A lot of interviewers ask about that stuff, and it's pretty fundamental, so you should know it. Know about locks and mutexes and semaphores and monitors and how they work. Know about deadlock and livelock and how to avoid them. Know what resources a processes needs, and a thread needs, and how context switching works, and how it's initiated by the operating system and underlying hardware. Know a little about scheduling. The world is rapidly moving towards multi-core, and you'll be a dinosaur in a real hurry if you don't understand the fundamentals of "modern" (which is to say, "kinda broken") concurrency constructs.

The best, most practical book I've ever personally read on the subject is Doug Lea's Concurrent Programming in Java. It got me the most bang per page. There are obviously lots of other books on concurrency. I'd avoid the academic ones and focus on the practical stuff, since it's most likely to get asked in interviews.

Coding

You should know at least one programming language really well, and it should preferably be C++ or Java. C# is OK too, since it's pretty similar to Java. You will be expected to write some code in at least some of your interviews. You will be expected to know a fair amount of detail about your favorite programming language.

Other Stuff

Because of the rules I outlined above, it's still possible that you'll get Interviewer A, and none of the stuff you've studied from these tips will be directly useful (except being warmed up.) If so, just do your best. Worst case, you can always come back in 6-12 months, right? Might seem like a long time, but I assure you it will go by in a flash.

The stuff I've covered is actually mostly red-flags: stuff that really worries people if you don't know it. The discrete math is potentially optional, but somewhat risky if you don't know the first thing about it. Everything else I've mentioned you should know cold, and then you'll at least be prepped for the baseline interview level. It could be a lot harder than that, depending on the interviewer, or it could be easy.

It just depends on how lucky you are. Are you feeling lucky? Then give it a try!

Send me your resume

I'll probably batch up any resume submissions people send me and submit them weekly. In the meantime, study up! You have a lot of warming up to do. Real-world work makes you rusty.

I hope this was helpful. Let the flames begin, etc. Yawn.