Code Kata 3: How Big, How Fast?

This one helps you quickly estimate sizes and speed.
http://codekata.pragprog.com/2007/01/kata_three_how_.html

How Big?

How many bits?

For this one, the way I thought about it is that 10 bits is roughly 1000 (2^10).

11 bits gives you roughly 2000 (2^11).

A pattern emerges as such: 2000 = 1000 * 2 ~ 2^10 * 2^1 = 2^(10+1).

Hence, you can quickly figure out a rough approximation by seeing how many multiples of 1000 there are and then figure out the leftovers.

• 1,000 ~ 2^10
• 1,000,000 ~ 2^20
• 1,000,000,000 ~ 2^30
• 1,000,000,000,000 ~ 2^40
• 8,000,000,000,000 = 1,000,000,000,000 * 8 ~ 2^40 * 2^3 = 2^43

How much space?

For a town of 20,000 residences, to store their names, addresses, and phone numbers, we can assume that we need about 200 characters per resident. This gives us 20,000 * 200 which is 4,000,000 characters. If each character takes up a byte, then we end up with roughly 4MB of data.

Binary trees!

Storing 1,000,000 integers in a binary tree will require 1,000,000 nodes. In the best case (balanced), the number of levels will be log2(1,000,000). Using our approximation technique from above, that would be roughly 20 levels. Any worse then a balanced tree would have more levels up to 1,000,000 levels. The space required to hold a tree like this would be calculated by noticing what data each node needs to hold. Each node needs to hold its own value, a pointer to the left child, and a pointer to the right child. If each piece of data requires 32 bits (4 bytes), then each node requires 12 bytes. This totals 12,000,000 bytes or 12MB of data.

How fast?

How long?

Assuming that each page in the book has roughly 200 characters. Each character takes up a byte. This means we have roughly 240,000 bytes to send. A 56kb/s modem translates to a 7,000B/s modem. This means it would take roughly 350 seconds which is roughly 6 minutes.

Binary search!

It takes 4.5mS to search 10,000 entries and 6mS to search 100,000. There is 10x more to search and it was done in 1.5mS more time. Hence, for 10,000,000, it should take roughly 9mS.

Brute force

There are 96^16 possible passwords.

A rough estimation would be 100^16 = (10^2)^16 = 10^32.

Since we can do 1000 searches per second, this would take 10^32 / 10^3 = 10^29 seconds to perform.

There are 86,400 seconds in a day which is roughly 100,000 seconds. This gives us 10^24 days.

Dividing by 365 is a little hard to do but dividing by 1000 is "close enough". This gives us 10^21 years.

Brute force is definitely not a viable approach.

Code Kata 2: Karate Chop

This kata challenges you to implement binary search in 5 different ways and to document things you had trouble with, like "off by one errors" and fencepost errors.
http://codekata.pragprog.com/2007/01/kata_two_karate.html

Here are my attempts in Ruby.
https://gist.github.com/wmwong/6662429

Got any other ideas on how else to solve this? Or feedback for my code? Let me know down below in the comments!

Rusty

Over the years, I've been working on several different products, all of which has allowed me to practice building products and shipping code. However, I haven't had much time to experiment and play. I feel I've lost many things that I've learnt from my CS degree.

So starting from today, I will start practising and learning again.

To start off, I'm going to work my way through Code Kata. I'll be posting my solutions on Gist.

I also plan on going through my Introduction to Algorithms book again. I'll try to summarize what I learn as I go.

Well, time to get started!

Ubuntu: Out of Disk Space

Problem

When I first installed Ubuntu on my desktop, I had decided I would like to partition my /home directory from the rest of my filesystem. This way, if an Ubuntu upgrade fails, I can always perform a clean install without having to backup my data. Or, theoretically, I could install another OS and my data would all still be there. When I partitioned the / directory, I decided that 10 GB should be enough.

Well, recently, I've been hitting up against that 10 GB limit. Every day when I boot up my computer, I get a warning that I only have a few hundred MB of space left. Well, today, I'm at 100% usage. I couldn't even send an email out from Thunderbird.

So, I tried clearing space. I tried running

sudo apt-get autoremove

Unfortunately, there was nothing left to autoremove.

I then browsed through /usr/local as that's where I store any applications I need to compile and run. Again, nothing extra to remove.

My last resort was heading to /tmp to clear anything there. However, it didn't make much of a difference.

I was still stuck.

Solution

Suddenly, a thought came to me. I've gone through several Ubuntu updates where it installed Linux kernel headers. Maybe that's what was taking up space. After a quick Google search, I came upon a post that would delete all unused Linux headers.

Just to be safe, before running this, restart your machine.

dpkg -l 'linux-*' | sed '/^ii/!d;/'"$(uname -r | sed "s/\(.*\)-\([^0-9]\+\)/\1/")"'/d;s/^[^ ]* [^ ]* \([^ ]*\).*/\1/;/[0-9]/!d' | xargs sudo apt-get -y purge

This ran in the terminal for some time while it cleaned out all my unused Linux kernel headers. I ended up getting rid of 3 GB of data.

I was free again!

So next time you're running out of room, make sure it isn't some old Linux headers taking up space.

References

http://ubuntugenius.wordpress.com/2011/01/08/ubuntu-cleanup-how-to-remove-all-unused-linux-kernel-headers-images-and-modules/

Ubuntu 12.04: No Root File System Is Defined

Problem

I got this error when trying to do a fresh install of Ubuntu 12.04 from USB. I get past the screen that asks if you want to download updates and install third party software, then I get stuck on the "Installation Type" screen.

The installer only sees /dev/sdb which is my USB and shows nothing in the partitions table. All the buttons are disabled. Clicking continue gives me the error "No root file system is defined".

Instead of installing, I went to "Try Ubuntu". This loaded up the Ubuntu desktop. Checking gparted and fdisk, I was able to find /dev/sda. Great! Unfortunately, trying to install gives me the exact same problem.

Solution

When you "Try Ubuntu", open up a terminal and type

sudo apt-get remove dmraid -y

It gave me some errors, but I ignored them. I ran the installer from the desktop and voila! The installer sees /dev/sda and I could install Ubuntu 12.04

References

http://askubuntu.com/questions/111926/installation-stuck-on-installation-type-screen

Ubuntu: Automating Locking and Suspending

Locking and Suspending from the Terminal

The first thing to note is that suspending the computer does not lock the computer. They are separate actions.

To lock the screen.

gnome-screensaver-command --lock

To suspend the computer, check out this article on How To Suspend Ubuntu from the Terminal. If you're simply running this from the terminal either by typing or using a script, I would suggest method 3 as it does not require sudo.

gnome-screensaver-command --lock
dbus-send --print-reply --system --dest=org.freedesktop.UPower /org/freedesktop/UPower org.freedesktop.UPower.Suspend

Locking and Suspending from cron (Problems)

Note: If you don't care about the problems and just want the solution, skip down to the next section.

If you had the above in a script that you could run from the terminal, it follows that you could run this script from a cron. Perhaps the scenario is that you wanted to lock down and suspend a particular computer at work every day at 5pm.

The script would look like this.

#!/bin/sh
gnome-screensaver-command --lock
dbus-send --print-reply --system --dest=org.freedesktop.UPower /org/freedesktop/UPower org.freedesktop.UPower.Suspend

Let's say it was stored in ~/bin/lock-suspend.sh. Remember to make sure that it's executable.

chmod +x ~/bin/lock-suspend.sh

When you run this in the terminal, your computer locks and suspends. Everything is fine.

Next, you would edit your crontab.

crontab -e

And place the following in it. The output from standard out and error is logged to a log file.

0 5 * * * /home/user/bin/lock-suspend.sh > /home/user/logs/lock-suspend.log 2>&1

You then wait for 5pm to come around and lo-and-behold, nothing happens.

Knowing that cron logs to /var/syslog/log, you go and check it and find that the cron job ran, but an error occurred.

Since the script was logged to /home/user/log/lock-suspend.log, you check it out and find the following errors.

** Message: Failed to get session bus: Command line `dbus-launch --autolaunch=364dc0936e296ffa0881a3e90000000a --binary-syntax --close-stderr' exited with non-zero exit status 1: Autolaunch error: X11 initialization failed.\n
Error org.freedesktop.UPower.GeneralError: not authorized

What does this mean?

After much Googling, I came across this thread. It explained that the first message came about because cron does not have access to the same environment as the terminal. More specifically, it is missing the environment variable DBUS_SESSION_BUS_ADDRESS.

I did not look much further into the second error though. I assume it is because cron does not have access to the dbus. This was easily solvable though as there are several methods to suspend, for instance method 2.

sudo pm-suspend

Locking and Suspend from cron (Solution)

In order to solve the first problem, we need to figure out what should go into the environment variable DBUS_SESSION_BUS_ADDRESS.

When you first login, DBUS_SESSION_BUS_ADDRESS is set for you. We can grab this and write it to file. Add the following to your .bashrc file.

set | grep DBUS_SESSION_BUS_ADDRESS > ~/.DBUS_temp

Now we need to modify the lock-suspend.sh script. However, before we do that, we need to think about the solution to the second problem. Since we'll be using sudo to run pm-suspend, the cron job must be run as root instead of as the current user. We will need to modify the script expecting root to be running the script.

Note that in order to set the DBUS_SESSION_BUS_ADDRESS environment variable, we use source. However, in order to use source, we must use bash instead of sh.

The full script.

#!/bin/bash
source /home/user/.DBUS_temp
export DBUS_SESSION_BUS_ADDRESS
su -c "gnome-screensaver-command --lock" user
/usr/sbin/pm-suspend

Now modify the root's crontab.

sudo crontab -e

And add the following.

0 5 * * * /home/user/bin/lock-suspend.sh > /home/user/log/lock-suspend.log 2>&1

Come 5pm, the computer locks and suspends gracefully and you can relax knowing that your data is safe and you're saving the planet by reducing power usage.

SSH Key Fingerprinting

After GitHub got hacked, I received an email informing me that my SSH keys may have been compromised. I needed to login to GitHub and confirm each SSH key.

The thing is, the SSH keys were being shown using their fingerprints. I've seen this before when logging into a server through SSH, but I've never actually had to generate one before.

Thank goodness for Google. Here's how.

ssh-keygen -lf 

References

• SSH fingerprinting