Skip to content

Code Kata 3: My Solution

4 February 2008

Kata 3 has to do with estimation. The full questions are on Dave’s blog.

How Big?

  • Roughly how many binary digits (bit) are required for the unsigned representation of:
    • 1,000 : 10
    • 1,000,000 : 14
    • 1,000,000,000 : 18  
    • 1,000,000,000,000 : 22 
    • 8,000,000,000,000 : 25
  • My town has approximately 20,000 residences…. Let’s allow 100 characters for a name, 150 for an address, and 15 characters for a phone number. 165 * 20000 = 310000 characters 
  • I’m storing 1,000,000 integers in a binary tree…. I don’t know much about binary trees, but I would expect it to have ln 1,000,000 levels. Based on my answer above, that’d be about 14, yielding 2^14 nodes. As for space, each number could be stored in 14 bytes, which would be 14 MB for a million numbers.

How Fast?

  • My copy of Meyer’s Object Oriented Software Construction… I’m going to guess about 120,000 words. Let’s say the average word in a technical text is 5 characters long, so that’s 600,000 letters. With formatting, I’d budget 900kb for plain text. This jives with my recollections of Project Gutenburg novels.
  • My binary search algorithm… It should go exponentially, so a hundredfold increase in entries caused a 1.5ms increase. The next one is another hundredfold, so that would be 1.5ms x 1.5 ms, or 2.25mS. So, I say 7.75ms.
  • Unix passwords are stored using a one-way hash function… Well, that would be 96! / (96 – 16)!, which is 96 * 95 * … * 80, or about 88^16, or about 7700^8, or about 670000^4, or about 44×10^8 ^2, or about 176×10^16 ms. There’s 1.5×10^9 seconds per year, so it would take millions of years to crack the algorithm. My answer is no. 🙂

See also my previous Kata posts: Kata 1, Kata 2

No comments yet

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: