FreeBSD Update build code

Simon Nielsen (the FreeBSD Deputy Security Officer) reminded me yesterday that I should be making more posts here about my progress on my FreeBSD summer of coding. A few days ago I finished writing the FreeBSD Update 2.0 build code; I'm now working on the FreeBSD Update 2.0 client code.

While the build code took me about two weeks longer than I had expected -- in the past two months I've really come to realize how much I rely upon receiving rapid feedback when my code is broken (feedback which isn't nearly as rapid when testing means waiting an hour or more for a buildworld+buildkernel) -- I still expect to finish all the work I had planned for this summer. In particular, the FreeBSD Update client code should be very quick to complete now, since I'll be reusing code from both the portsnap client and my 6.0 to 6.1 upgrade script. Once I have the client written and cross-tested against the build code, I will be committing the build code to the FreeBSD projects repository; I don't want to commit anything yet since I'm sure there are at least one or two bugs waiting to be found when I start running the client.

Posted at 2006-07-20 06:45 | Permanent link | Comments

Google humour

Based on input from an increasingly large number of people who work at Google, I decided a few weeks ago to send in my CV. This is essentially a fishing expedition: I don't yet know if I want to work for Google, because they carefully avoid putting any useful details onto their jobs website; but the hiring process itself will provide me with at least some such information. Until now I hadn't wanted to spend my time on such expeditions, but the aforementioned input has slowly tipped the balance between "wasting time" and "potentially interesting work" in favour of going through the hiring process, by increasing the probability I assign to the word "potentially". (There are some other factors involved, including a hesitation about working in GeorgeBushia, and my stringent requirements for academic and intellectual freedom, but I'm willing to waive the prior and I expect Google would negotiate on the latter.)

After talking to a member of Google Staffing yesterday, I received an email advising me when I would be called for a technical interview (by someone whose name was unfortunately misspelt). The email went on to say that

"You will be asked questions on previous work experience and some questions on coding, algorithms, and data structures. Here's a link to look through that will give you a better sense of what the phone screen may cover: http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=alg_index ."
That link is, to say the least, rather amusing. It has content written in a style which I last saw when reading demo coding guides in the early 1990s --- a style which shouts "blind leading the blind" --- and even the substance isn't of a quality which would lead me to recommend it to anyone. The article about "Using Regular Expressions", for example, was clearly written by people who don't actually know what regular expressions are --- they mention back-references without pointing out that regardless of what POSIX claims, expressions including back-references are not regular (or put another way, cannot be matched by a FSM) --- while the article about binary searching suggests using "a few hundred iterations" when searching for a real number --- completely ignoring the detail that IEEE double precision floating-point values have only 53 bits of mantissa. (Side note: If you want to perform a binary search on floating-point values, perform the midpoint-selection while treating the values as integers of the same length stored in sign-magnitude format. This ensures that you complete within one iteration per bit of floating-point storage, even if the value you end up with is very close to zero. If you compute midpoints using floating-point arithmetic, you'll need O(n) iterations to "find" 2^(-n).)

Even more amusing, however, is the notion that I should review this material prior to my interview. I learned this material in grade 10; since then I have been finding new algorithms (polynomial GCDs over algebraic number fields, rapid multiplication modulo the sum and difference of highly composite numbers, matching with mismatches, naive delta compression of executable code, feedback-free file synchronization, and an improved Quadratic Sieve, to name a few) more than learning about existing algorithms. I wrote my doctoral thesis about three of these algorithms; and while I have forgotten a great deal of what I was doing at age 14, I doubt I'll ever forget about something as simple as single-processor in-core sorting.

Maybe I'm being unfair. After all, the choice of an expert in programming languages and compilers for a first technical interview suggests that they're not planning on quizzing me about undergraduate material, and the paragraph I quoted is probably sent to everybody applying for technical positions. Still, mindless application of form letters is a bad idea (mindless anything is a bad idea, but form letters are particularly pernicious); and somebody must have passed a note to Google Staffing suggesting that they point people at TopCoder's tutorials. As far as I'm concerned, those are two mistakes which should never have been made.

Posted at 2006-07-19 09:00 | Permanent link | Comments

Recent posts

Monthly Archives

Yearly Archives


RSS