LateNightHacking Louis Journal

Auth

I was listening to the radio this morning, and they were playing Martina McBride's "This One's For The Girls". It has the line about girls at 25, living on dreams and Spaghetti-o's. I thought, "you know, Spaghetti-o's sound like bachelor food!" - like ramen and canned chili, something that single guys eat because it's as simple as can be and they don't care enough to seek out anything better. I didn't think girls ever lowered themselves down to bachelor food level. :)

˜ ™

Ahh! After two weeks, it's good to be home!

˜ ™

OK, so after asking all these interview candidates to analyze algorithms, I realized I ought to do a little of that myself, considering I whole-heartedly believe in it! I've been experimenting with a new price update data structure. I've settled upon having an enumeration of fields (ask size, ask price, etc.) and having a method

Object getField(FieldId fieldId)

Object getFieldMetadata(FieldId fieldId, MetadataId metadataId)

I got smart about it, and decided to actually try to write down all the vague ideas I had and calculate which is best when. When evaluating, I used these criteria: I expected lots of sparse updates. The PriceUpdate objects are immutable, and they are likely to be cached. Therefore, I was concerned about creating lots of garbage (object count) and using lots of memory for cached objects (byte count). The result (which surprised me) was that the array format blows all the others out of the water. Clearly an array will win on object count, but I figured it would lose on byte count. Memory usage of TreeSet and HashMap are both proportional to the number of fields with values (as opposed to array, whose memory usage is proportional to the number of possible fields) but the memory usage slopes for TreeSet and HashMap are so steep that both fall behind an array of twenty possible fields at less than three fields with values! Wow! Since I expect to set three fields in even the sparsest update, array wins hands down.

I also had a small problem to solve that was brought up by today's interview. Given a game board of n by n, build a quad tree over it. What is the order of the number of nodes in the quad tree? Well, after messing around with sums of series of logs and exponents, I convinced my self of the answer (and that a simpler approach to the analysis would have yielded the same result :). I think it's O(n2). What do you think?

˜ ™

Just so you don't think I'm shirking my duties, I've also been thinking about the planning problem that Dan and I have been working on. However, I don't think it's appropriate for a public journal, so I can't say anything more.