Daniel Martin

Okay, haven't posted in two whole months, I haven't told you what it's like working at Google since the first day, etc. I will say that my lack of blogging here has absolutely nothing to do with my internal-to-Google blog, since I haven't actually signed up for that either.

And this post isn't going to interest most of you who have me on your friends list, but if I waited for that, it'll be another two months or more before I post anything again. So here's a post on something I was thinking about this morning.

I was reading through some of Steve Yegge's old blog ("who is he?", you ask? He's just this guy that used to work at Amazon, now works for Google, and had an Amazon-internal blog that he made mostly public after leaving Amazon. Some of it's interesting) about interviewing programmers and he gave this as an example of the naive solution to the problem "find the nth Fibbonacci number":

static long fib(int n) {
  return n <= 1 ? n : fib(n-1) + fib(n-2);
}

One of the comments noted that they'd expect any candidate to be able to tell that that implementation as it stands is O(2ⁿ).

That didn't feel right to me - I mean, clearly it is O(2ⁿ) in the sense that big O provides an upper bound, but it's not a tight bound - that is, it isn't ϴ(2ⁿ). So what is a tight bound?

It turns out that this algorithm is actually ϴ(fib(n)), which is to say that it's ϴ(φⁿ), where φ is the golden ratio (1 + √5)/2.

Why is this? Well, I think I'll leave that as an exercise for the reader, or maybe I'll add it later to this post underneath a cut tag. Suffice it to say that there's a nice recurrence relation that defines the number of invocations of fib necessary to calculate the nth Fibbonacci number, and that it requires a bit of fiddling after that, but not too much.

Anyway, that's something I was thinking about this morning.

Dear NJTransit: (written at 6:53)

I appreciate that train scheduling is a hard problem, and that real-life train scheduling is complicated by factors beyond your control.

I also realize that it is not in any way your fault that I live a brisk fifteen minutes' walk away or that I'm functioning on very little sleep. It is, I suppose, also not your fault that I aimed to catch the 6:19 train this morning. The fact that the 6:19, 6:28, and 6:43 trains are all MIA, though, is going to have to be your fault.

I would very much like to get on a RiverLine train now.

Dear AT&T: (at 7:31)

You know what would have been cool? To be able to post that last bit before the insanely overcrowded (packed standing room only) RiverLine arrived. Unfortunately, a wireless internet connection that I get dropped from every minute and a half, and get anemic rates with at best, isn't really that useful there. It would be nice if I got more than one bar throughout Burlington.

Dear Firefox Team: (at 7:34)

You know what would be nice? If having your wireless connection crap out on you didn't cause your web browser to lock up and become completely unresponsive.

Kthx, bye

Update: Total door-to-desk time? 3:02. Ugh.

Sorry that there's not been any detailed post about getting the Google job. The short version is that they didn't hire me back in August, but then in early June a different Google recruiter said, "I found you in our database; would you be interested in this other job?" And this time, after another phone screen and on-site interview (this time in NYC), they offered me the job.

The long version is that, plus lots of reflection and angsting about "why am I doing this?" and "how am I going to tell my boss?" and "how is jmartin2 going to handle me being in New York five days a week?" Maybe I'll post some of that later.

Anyway, that's not what prompted me to get off my virtual duff and post. What prompted that was finishing Flowers for Algernon this morning, and then sitting down this afternoon to watch one of the weekly syndication Simpsons episodes and having it be the episode Lisa the Simpson.

Some people might deduce from my posts this past month that either I have abandoned livejournal or that nothing happened during June. The latter is not true, and I don't think that the former is either, but I still can't get into the regular blogging habit.

#include <std/apologies/long_journal_update_lag.h>

So now for something completely different; namely, a rant about a particular instance of idiocy common as dirt on the web:

---

Dear web page designers:

See all the hits this search generates? Almost without exception, every result there is either telling you how to do something that's a bad idea or asking about details of how to implement a bad idea. What I'm talking about is this: most of the time when you need to type in actual physical address online, there will be a text box for your name, one for your street address, one for your city, one for your zipcode, and a drop-down box for your state.

Now, every state has this convenient little two-letter abbreviation, and anyone typing in an address in a particular state already has the abbreviation quite literally at their fingertips. Why is it that I can't type "NJ" into the state box? Why do I need to type in "NNNN" or "NNNNN" or "NNNNNN" to get my state? (Depending on whether the creator of the box has included Canadian provinces in the drop-down or not, and on whether they sorted the options in the dropdown by abbreviation or by state/province name) I can't even get a standard bunch of keypresses memorized to type my state!

This is not a new issue; there was a use-it.com article about this in 2000. The big boys (aka amazon) do this correctly, with a text box. And yet still, you'll find advice like this (from a page supposedly made in 2005):

Sometimes you may want to replace text fields with drop-down menus. This might be because selecting from a menu is easier than typing. But it could also be because the script that handles the form can't interpret just any text entry.
For example, you will often be asked to choose your state from a drop-down menu. This might be because picking it from the menu is easier than typing the name of the state.
Along the same line, you may often asked to enter the 2 letter initials of your state from a drop-down menu as well.
This could prevent confusion for the script that handles the form input. If, say, the script was programmed to only accept capital letters, then a drop-down menu would secure that no invalid entries were made.

Aaaaaaaaaaaaaaaah!

Look, if the script on the back end blows up when given input like that, then fix the script. Or make a wrapper around it to validate data first, representing the form to the user if they type in a bad state abbreviation. (Since for security reasons, you need to do that already anyway, and you know it)

Don't make me guess how many "N"s to press, and don't make me jump back to the mouse, especially when you lay out your form like a standard US postal address so that I'm jumping back to the keyboard for the zipcode anyway.

Is this a small annoyance? Absolutely. It's trivial in the grand scheme of things, and even fairly small in the world of web-based annoyances. But it's totally unnecessary. In fact, implementing the drop-down is probably more work than putting another text box there. Please - go play an extra minute or so solitaire instead of making yet another state drop-down box. Your time will be better spent.

From the quiz solution summary on http://rubyquiz.com/quiz122.html: (ellipses in the original)

You have shown me the light and it tells me... Daniel Martin is crazy. I'll leave it to him to explain his own solution, as punishment for the time it took me to puzzle it out. I had to print that Array inside of the inject() call during each iteration to see how it built up the answer.

Update: I did in fact accept my punishment and post an explanation of my twisted implementation of the Luhn algorithm.

Update: Sorry; anonymous comments aren't shown on this entry any more. Three spam deletions is my limit.

Continuing my pattern of occasional technical posts just that my journal won't be completely dormant, here's another one:

If you do much web development at all, you probably work with a template language of some kind. You know, the kind of thing where you write HTML with various placeholders in spots that get filled in by the web application - examples include jsp pages, Django's template system, Smarty templates, PHP pages, or HTML::Mason.

Anyway, the problem with virtually every HTML templating language out there is that they make it easier for the person writing HTML templates to add an XSS hole than to avoid it. This isn't a matter of making it possible for page writers to shoot themselves in the foot - that's always going to be possible, given any reasonable system - it's a matter of making it easier to do than to avoid.

( More for people who've ever worked in such environments )

So I've thought about several different journal entries I could write lately, but I somehow just don't feel I have the requisite will-to-type to write any of them. So here are some scattered thoughts I'm not journaling about:

• Katherine: ( 3 topics, 107 words )
• Personal: ( 4 topics; 418 words )
• Technical: ( 5 topics; 345 words )

So last night as I was giving Katherine her bath, I started singing the silly "Willoughby wallaby W____, an elephant sat on ____" song. (A Google search for those unfamiliar with this song)

Anyway, Katherine really got into it. I would start a line ("Willoughby wallaby Wommy, an elephant sat on ....") and she'd finish it ("Mommy!"). I got tired of this game long before she did; she kept asking me to do more, and occasionally pointing to things for me to have the elephant sit on. Occasionally she'd ask me to do something that began with "w", and I'd have to explain that that wouldn't work. ("Do the washcloth!")

After the bath, Katherine continued the song in her room by herself. Here's what I remember:

Willoughby wallaby winosaur, an elephant sat on Pinosaur.
(This is what she named the green toy she's using as a pillow here a few weeks ago)

Willoughby wallaby wocks, an elephant sat on my crocs;
Willoughby wallaby wora shoes, an elephant sat on my Dora shoes.

Willoughby wallaby wink, an elephant sat on my drink;
Willoughby wallaby wouse, an elephant sat on my house.

Willoughby wallaby wanties, an elephant sat on my panties;
Willoughby wallaby wattress, an elephant sat on my mattress.

And there was much more I don't remember. We continued this morning in the car on the way to day care, where the elephant sat on "wight"/"the light", "ween"/"the green", "wed"/"the red" (we go through several traffic lights in short succession); on several of the kids at her day care; on Dora, Boots, Backpack and Swiper (Swiper got sat on more than once); on "wee"/"the C", and "wetters"/"the letters".

Also, after she had asked me to do another word that began with "w", and I explained that it wouldn't work, she showed me that I was wrong:

Willoughby wallaby wonsin, an elephant sat on Wisconsin.

So, we need a new bank. Anyone have any suggestions?

We're currently banking with Wachovia, but starting in April they're going to be deducting a $6/month fee if you use Quicken to get transactions automatically and manage your accounts. As this would, over the course of a year, be a visible percentage of our average checking account balance, we're thinking of jumping ship.

Given my history with big banks, I was looking at this extremely local bank, but their web site does not, alas, fill me with great confidence. Also, as our main reason for jumping is the end of free Quicken support, it would make little sense to jump to a bank with no Quicken support. (the list of Quicken-supporting banks)

So what do other people use that you're happy with? Any place in particular that we should avoid?

It's been a long time since I posted, and I told jmartin2 that I'd make the next livejournal update of this kind since she's been doing a lot of that lately.

Anyway, if you've been reading her journal, you know that jmartin2 and I have been trying to get our daughter Katherine potty-trained. The basic way this works is that she gets all excited about wearing underwear, and then refuses to go sit on the potty and do anything while dancing around uncomfortably.
( Warning: explicit acts of parenting ahead )