Programming Puzzles

Prepping for programming interviews can be a challenging, especially if you're over worked, and don't have a lot of time to study, because of family commitments.  The following is list of problems I studied and solved recently to get ready for interviews.

Problem 1

1) Implement a breadth first search non-recursively
2) Implement a depth first search non-recursively
3) Implement a breadth first search recursively
4) Implement a depth first search recursively

Code:

---

Output:

Currently searching level = 1, index = 0
Currently searching level = 2, index = 1
Currently searching level = 2, index = 2
Currently searching level = 3, index = 3
Currently searching level = 3, index = 4
Currently searching level = 3, index = 5
Currently searching level = 3, index = 6
Found = 7, index = 6, level = 3
Currently searching level = 1, index = 0
Currently searching level = 2, index = 1
Currently searching level = 3, index = 3
Currently searching level = 3, index = 4
Currently searching level = 2, index = 2
Currently searching level = 3, index = 5
Currently searching level = 3, index = 6
Found = 7, index = 6, level = 3
Currently searching level = 1, index = 0
Currently searching level = 2, index = 1
Currently searching level = 3, index = 3
Currently searching level = 3, index = 4
Currently searching level = 2, index = 2
Currently searching level = 3, index = 5
Currently searching level = 3, index = 6
Found = 7, index = 6, level = 3
Currently searching level = 1, index = 0
Currently searching level = 2, index = 1
Currently searching level = 2, index = 2
Currently searching level = 3, index = 3
Currently searching level = 3, index = 4
Currently searching level = 3, index = 5
Currently searching level = 3, index = 6
Found = 7, index = 6, level = 3

Problem 2

Given a binary tree return the level with maximum number of nodes

        1
       / \
      2   3
      /\  /\
     4 5 6 7
    /       \
   8         9 

Code:

---

Output:

• result: success     time: 0.07s    memory: 380160 kB     returned value: 0
  input: no
  output:
  

  2
  

Question 1

What are the uses of a b-tree, avl-tree and rb-tree?

When would you use a b-tree over an avl-tree?

Which one, out of the balanced BSTs is most the efficient?

Why don't we always use a b-tree?

Answer:
A b-tree is a generalization of a binary search tree in which nodes can have more than 2 children.  B-trees are used for applications such as databases and file systems.  B-trees are ideals for systems that need to store large blocks of data.  An avl-tree and an rb-tree are two types of automatically balanced tree structures that guarantee O(log n) for all operations (lookup, insertion, removal).

You would use a b-tree when something is disk backed, because b-trees group large blocks of data they can reduce HD seek time to improve performance of retrieving large data blocks from disk.

Efficiency depends on usage.  Avl-trees have stricter (more frequent) rebalancing, but faster retrieval time because of this.  Rb-trees rebalance less often, so they are faster for insertions and deletions, but slower for retrieval.

You could always use a b-tree or b+tree, but avl-trees and rb-tree provide other advantages, such as less tree maintenance, and memory flexibility.  In an avl-tree and rb-tree, nodes in memory can be easily detached from the tree structure, not so in a b-tree.  Avl-trees and rb-trees can be easily converted to linked lists without additional memory usage (which can allow you perform other operations easily with the tree, such as merging).

Problem 3

Crete a method hasUniqueChars(String a), do not use any type of built-in collection.

result: success     time: 0.07s    memory: 380160 kB     returned value: 0

input: no

output:

  hasUniqueChars("abc")
! hasUniqueChars("abcc")
  hasUniqueChars("abcdefhi")
! hasUniqueChars("abcdefhiabcdefhi")
! hasUniqueChars("ccc")
! hasUniqueChars("xxxkjsdfkjqqqdkjfd")
  hasUniqueChars("abcdefghijklmnopqrstuvwxyz")

Problem 4

Convert an infix expression to postfix.

result: success     time: 0.07s    memory: 380160 kB     returned value: 0

input: no

output:

1 2 3 + +
1 2 + 3 +
1 2 + 3 4 + + 3 +

Problem 5

Given a Tuple for eg. (a, b, c)..

Output : (*, *, *), (*, *, c), (*, b, *), (*, b, c), (a, *, *), (a, *, c), (a, b, *), (a, b, c) 

The core of the problem involves generating ordered permutations of the indexes

  to replace with '*' ...

result: success     time: 0.08s    memory: 381184 kB     returned value: 0

input: no

output:

a,b,c
*,b,c
a,*,c
a,b,*
*,*,c
*,b,*
a,*,*
*,*,*
a,b,c,d
*,b,c,d
a,*,c,d
a,b,*,d
a,b,c,*
*,*,c,d
*,b,*,d
*,b,c,*
a,*,*,d
a,*,c,*
a,b,*,*
*,*,*,d
*,*,c,*
*,b,*,*
a,*,*,*
*,*,*,*

EOT

Convert OSStatus to a human readable string

It's actually fairly easy to get something useful / readable out of an OSStatus code. This is a simple no-compilation Python script to convert an error code to it's description.  It uses "two poorly documented but very usefull functions" — GetMacOSStatusErrorString and GetMacOSStatusCommentString.

Example output:


And the script:

Naïve Swype Implementation (& How It Works)

How does Swype work? I don't know for sure, but I came up with a fairly simple approximation of Swype's behavior on Android phones. Which with a little bit of tweaking (maybe some more math and a better set of dictionaries) it could probably get a lot closer to approximating Swype.

This is implemented using Proce55ing which will export Proce55ing code to a Java applet (full source listing).

As for how the implementation works, I started with a word set which holds a collection of words and word prefixes.  The classify operation serves to tell me if the string I am holding is a complete word, a partial word, an incomplete word, or both.

A returned classification is also able to communicate it's frequency (ranking in frequency of usage in common english text).  These frequencies were acquired from Project Gutenburg.  The frequency list is a frequency count from Usenet postings, so it's a bit odd and doesn't include some common words (most notably some connecting words).  The other dictionary is a list of the 3000 most common English words.

Keep this in mind when you play with the sample, the dictionaries aren't perfect.  The naïve implementation along with the poor dictionaries give the demonstration some peculiarities.

Regargless, the populate operation of the word set loads these words, their frequencies, and all prefixes leading up to the word in a dictionary.  For example the word THEY is loaded in as T (stored as incomplete), TH (incomplete), THE (complete & incomplete) and THEY (complete) along with the corresponding word frequencies.


Next is all the connecting glue for Proce55ing. The SwypeState class maintains the keyboard hit collector, the word set, and the bits that draw the keyboard and the pen.  The keyboard logic and the keyboard hit collector are fairly boring, but suffice to say, they draw the keyboard and accurately collect what keys where hit when drawing over the keyboard.


Probably the most interesting part of the implementation is figuring out what words where Swyped.  The system passes an event to the key hit collector when a word is finished, this initiates a seach through the word set for potential words.  For a given word like "THEY" the actual keys swiped can vary widely.

Here are some examples (these all map to "THEY"):

  T, Y, H, G, F, E, R, T, Y

  T, G, H, N, C, D, S, E, R, F, C, X, S, W, T, G, V, C, S, E, Y

  T, Y, H, J, K, K, J, H, G, F, D, S, A, Q, W, E, R, T, Y

So, you have some things that don't really look like words at all.  However, the word set loaded with all the word prefixes sorts this out.  It does this using a simple search that slowly builds up a set of prefixes that map to partial words, or complete words (which get recorded), while throwing away things that map to nothing.  As a new letter is examined from the list of hit keys it is added to each of the previously collected prefixes.

In this manner words like OR, OUR, OUT that require one vertical swipe can be detected.  This word overlap presents another problem though: which word has priority?

The first strategy used to resolve overlapping words is a sort based on match length.  With the idea that the longest match is probably the word the user was trying to spell.  For example, a word like THERE will come up with THE as a complete prefix when THERE was then intended swipe because of the swipe length.

The second strategy is where the word frequencies come in to play, they attempt to sort the list of hit words by their frequency.  Words with a higher frequency in the English language should bubble to the top.

Improvements:

• Better dictionaries: Possibly one that lists all forms of a word with the same frequency (e.g. be, being, been).
• Fat finger search: extend and trim each swipe path so that less accuracy is needed.  That is, a what's around you operation could be added to each key to get many more paths to search that could lead to the desired word.
• Spell checking: for people that don't know how to spell, predictive text can be frustrating.  A misspelling dictionary could be really using to help with this.
• Markov chain: I don't know how effective this would be but since Markov Chains can be used to generate English text it seems like they could be used to select a more likely next word.

The full source code is available at github.com.

What happens when your email "unsubscribe" button doesn't work...

What happens when your email "unsubscribe" button doesn't work? You get marked as spam. I'm looking at you HP.

"6 months and a million dollars"

...a common saying from a fellow co-worker and previous HP employee... well, 6 months and million dollars later HP, your unsubscribe button doesn't work and I'm about to start clicking the mark as spam button.

I have reservations about clicking this button since it's not technically spam-- and I don't want to pollute Google's cache of data of what's considered spam. Really, I need a "I don't want these emails sent to me anymore, figure out how to get rid of them" button.

Alas, that doesn't exist. Instead I have to resort to click on a damn "unsubscribe" button that's squirreled away at the bottom of the email. Then, two weeks later, I get to figure out that HP really doesn't want to forget about me.

I'm like that one girlfriend you wish you'd never dumped, except, for HP, it's really best if we don't see each other again.

(Maybe I'll go in to my filters and kill file them, but that'll result in even more annoyance.)

Buzz Bookmarklet

I found it odd that I couldn't easily find a "bookmarlet" for Buzz that I could easily drag into my bookmarks bar.

Maybe I'm blind, or wasn't looking in the right places... so I wrote one. It's probably broken in some cases, and is fairly rudimentary, but here it is:

Post to Buzz (drag to bookmarks bar)

If interested, here's the code:

This is a more fancy (shorter) version that uses querySelector:

Silly Space Optimization on Google's Home Page?

According to @chrisskelton and @wkvong, Google leaves off the ending </html> and </body> tags from their home page to optimize for space:

1. chrisskelton Today I learned that Google excludes the </body> and </html> tags from their main page to save 18 bytes. 09 Feb 2010 from web
2. wkvong You know Google is crazy because Google's home page doesn't close its <body> or <html> tags for performance 10 Feb 2010 from web

-- this quote was brought to you by quoteurl

Indeed, if you check out the source code for the Google home page it's not there:

To put this in perspective: according to SearchEngineWatch.com Google gets about 91 million hits per day (in 2006). Assuming all those searches start on the home page (and there's no caching involved), that's:

18 bytes * 91,000,000 hits = 1638000000 bytes
                             1599609.38 kilobytes
                             1562.12    megabytes
                             1.53       gigabytes

If we go by monthly hits:

18 bytes * 2,733,000,000 hits = 49194000000 bytes
                                48041015.63 kilobytes
                                46915.05    megabytes
                                45.82       gigabytes

That's 1.5 gigabytes per-day (or 45.82 gigabytes per-month) that Google doesn't have to send, it doesn't pay for, and consumers don't pay for— all by leaving off a few useless tags. Not really that crazy.

Simple Errno Lookup with Python

Visual Studio has a tool [ERRLOOK] which looks up explanations of error codes. When you don't have the convenience of application code that automatically converts and reports this back to you it's nice to have.

I don't know of a similiar utility on Linux (or other Unix variants), but I know the library calls exist to write it (at least for well known system error codes).

Below is my first pass at writing this utility for Linux / Mac OS X using Python's CTypes.

The benifit of using python is that it doesn't need to be compiled (though this is a small benefit)— it's also an example of using CTypes to do FFI. Python also has the errno module which provides a mapping between a numeric error code and a symbolic name.

The calls to load libc.dylib or libc.so.1 might need to be tweaked depending on the system it's running on.

Example output:

[Source for this post in Markdown mark-up]

Using TwitterFeed to send certain del.icio.us bookmarks to Twitter

TwitterFeed is a really cool service. Using Twitter feed you can push any RSS feed to Twitter, which enables a super simple way to push pretty much any kind of syndicated data to Twitter (and now Facebook, Laconica, and HelloTxt).

I also use del.icio.us to save interesting bookmarks in a easily accessable persistent location.

The problem was several fold:

• Twitter is a great way to talk about things (including links)

• Twitter isn't so great at categorizing links and making them easy to find later

• I wanted to save links on del.icio.us but share them on Twitter

• Not everything I shared on del.icio.us was something I wanted to spam my Twitter followers with.

Turns out the solution is pretty simple. On del.icio.us you can create tags. These tags help oranize bookmarks.

For each tag you can get an RSS feed (see where this is going?). RSS feeds for tags look like this:

http://feeds.delicious.com/v2/rss/<username>/<tag-name>

You can also visit the tag's webpage and select the RSS feed button next to the URL bar (then record new link in the URL bar):

I selected the tag name tweet-this for this set-up.

The next step is to visit TwitterFeed and get set-up with an account. Once you've got your account you'll be at a Feed Dashboard, select Create a New Feed and enter the previously recorded URL:

Select test rss feed to make sure everything is working.

The rest is point and shoot with the TwitterFeed set-up process. Now, only bookmarks recorded on del.icio.us with the tweet-this tag will show up on Twitter.

[Source for this post in Markdown mark-up]

Exponential Visitor Graph (Ebay)

I thought this was fairly entertaining...

I wrote a simple page hit counter for a couple Ebay / Craigslist listing we were doing (using Google's AppEngine, and Yahoo's YUI).

Recently I added a feature to allow it to graph visitor counts over time (basically a cheesy analytics engine).

I guess one of the items was particularly desirable (a very complete, good codition SNES system with a lot of games) because it had what I image is probably a pretty typical graph of visits to an Ebay auction:

It's pretty obvious that the spike (a huge spike) in visitors is when the auction was about to close when everyone was manically hitting reload. Just eyeballing the graph, it looks like an exponential increase.

[Source for this post in Markdown mark-up]

Updated: Token Bucket Downloader

I've updated the rate limiting downloader (that uses token bucket algorithm) to be more user friendly out of the box. It attempts to use urllib2 by default so it can rate limit pretty much any url.

Previously the script required an http proxy and the only means of adjusting operating parameters was global variables in the script. A proxy server is no longer required and all operating parameters can be adjusted via script options.

If an http proxy is selected the python http library (httplib) is used, this is a more rudimentary library so not as many situations are handled. It's possible to install a proxy handler in urllib2 but I didn't do this.

This is more-or-less a "complete" rate limiting download manager. Option output:

   Usage: rlfetch.py [options] url

   Options:
     -h, --help            show this help message and exit
     -f FILE, --file=FILE  output filename
     -d DIR, --dest=DIR    destination directory
     -p SERVER:PORT, --proxy=SERVER:PORT
                           http proxy server
     -z BYTES, --buffer=BYTES
                           buffer size
     -l KBS, --limit=KBS   kbs limit
     -b KBS, --burst=KBS   burst limit
     -t SECONDS, --tick=SECONDS
                           tick interval

Current state of the code.

Basic Token Bucket Rate Limiter

In locations were you have limited internet resources it's sometimes necessary to implement rate limiting. I was curious exactly how this worked so I worked out a simple Token Bucket based rate limiting HTTP downloader.

This Python script does a couple things:

• Limits rate of data consumption in kilobytes per second
• Prints out the instantaneous KB/s and the overal/actual KB/s [this is done by monitoring the file size on disk]

Token bucket is a pretty simple algorithm. The basic algorithm is to create an artificial stream of tokens, which are generated as fast you want to allow the real stream to go. If tokens are not removed from the "bucket" then tokens are only generated up to a "burst limit", which is the maximum amount over the average limit that's desirable (this could change to help trend a stream toward the average limit).

In the Python implementation, 3 threads are used. Thread one monitors the rate of download. Thread two consumes tokens and downloads real data from an HTTP source. Thread three generates tokens and places them in a bucket, stopping when the burst limit has been reached.

The code is available below or at codepad.org.

# -*- python -*-

import os
import random
import time
import httplib
import urlparse
import sys

import threading

from pprint import pprint

###########################
# Tuning knobs
BUFSIZE = 8192
BPS_LIMIT = 50 * 1024
BURST_BPS_LIMIT = 70 * 1024
TICK = 0.01
###########################

g_usage = "%s <download directory> <target url>"

g_bucketTokens = 0
g_exit = False

def parseArgv(argv):
    if len(argv) < 3:
        return None
    directory = argv[1]
    if not os.path.isdir(directory):
        return None
    url = argv[2]
    s = urlparse.urlsplit(url)
    _, filename = os.path.split(s.path)
    return url, os.path.join(directory, filename)
     
def takeTokens(tokencount):
    global g_bucketTokens
    if g_bucketTokens >= tokencount:
        g_bucketTokens -= tokencount
        return True
    return False

def printKbs(filename):
    def _():
        start, end = None, None
        tot, num = 0, 0
        while True:
            if g_exit:
                print "KB/s monitor exiting..."
                break
            end = time.time()
            size = g_byteCount
            if start is not None:
                inst = ((size - old) / 1024.0) / (end - start)
                tot += inst
                num += 1
                print "I: %.02f kb/s, A: %.02f kb/s" % (inst, tot / num)
            start = time.time()
            old = size
            for x in xrange(int(2 / TICK)):
                if g_exit: break 
                time.sleep(TICK)
    return _

def feedBucketTokens():
    global g_bucketTokens
    tokens_per = int(BPS_LIMIT * TICK)
    print "Tokens per tick: %d" % (tokens_per,)
    while True:
        if g_exit:
            print "Token feeder exiting..."
            break
        if g_bucketTokens >= BURST_BPS_LIMIT:
            time.sleep(TICK)
            continue
        g_bucketTokens += tokens_per
        time.sleep(TICK)

class BucketReader (object):
    def __init__(self, fp):
        self.fp = fp
    def read(self, bufsize):
        while True:
            if takeTokens(bufsize):
                break
            time.sleep(TICK)
        return self.fp.read(bufsize)
        
def prepareFile(filename):
    fp = open(filename, 'ab+')
    fp.seek(0, 2)
    fsize = fp.tell()
    return fp, fsize

def startHttpReq(url, fsize):
    headers = { "Range" : ("bytes=%d-" % fsize), }
    pprint(headers)
    h = httplib.HTTPConnection("aproxyserver", 8080)
    h.request("GET", url, headers=headers)
    r = h.getresponse()
    pprint(r.getheaders())
    return r

g_byteCount = 0

def readLoop(fpIn, fpOut):
    global g_byteCount
    while True:
        d = fpIn.read(BUFSIZE)
        fpOut.write(d)
        fpOut.flush()
        g_byteCount += len(d)
        if len(d) < BUFSIZE:
            break

def main():
    global g_exit
    try:
        params = parseArgv(sys.argv)
        if params is None:
            print g_usage % (sys.argv[0],)
            raise SystemExit(1)
        url, filename = params
        threading.Thread(target=feedBucketTokens).start()
        threading.Thread(target=printKbs(filename)).start()
        fpOut, fsize = prepareFile(filename) 
        fpInput = startHttpReq(url, fsize)
        readLoop(BucketReader(fpInput), fpOut)
    except KeyboardInterrupt:
        pass
    finally:
        g_exit = True

if __name__ == '__main__':
    main()

# vim: et:sts=4:ts=4:sw=4:

IPython on Wx \ Windows

This is almost strictly for Google to index in hopes that it helps someone else trying to do what I was doing. Also, this was probably in the documentation somewhere, but I hate reading documentation.

IPython is an enhanced interactive shell for Python. Out of the box if you run the WxIPython program you may get the following error when attempting to do tab completion:

'InteractiveShell' object has no attribute 'Completer'

This just means that you didn't install PyReadline. IPython should really be smart enough to figure this out on its own — tab completion is part of the core functionality of IPython. Therefore, they could also bundle PyReadline with the default Windows installation package. Especially since it looks like PyReadline was developed by the same group.

Can you spot the social commentary?

I guess freeze framed like this it's pretty easy to spot. This is from American Dad season 4, episode 9, time index around 6 minutes (as the picture shows) -- captured from Hulu.

Parallax Scrolling in Android

A while ago I heard about something called parallax scrolling [1] being used on Google's Android platform (specifically on the G1). I had just gotten the G1 at that point and hadn't noticed that it was doing something special when scrolling between the three screens in the "home" application.

The idea is pretty simple, you have two surfaces that scroll at two different speeds, one is bigger or father away, depending on how you look at it.

On the G1 it allows the background of the home screen to be smaller than the total "viewable area" that the three home screens cover. This is useful since the size of the home screen areas can change drastically when the phone is flipped open. It also creates the illusion of depth.

Below is my implementation using Proce55ing (click and drag the light purple square).

Source code: parallax (plain text)

1 - Turns out I was probably reading a Qt developer blog. These posts support that conclusion.

Don't Irritate Small Company Hiring Managers

Where I work is a relatively small company. We don't have much the way of an Human Resource (HR) department. We've got one person that's in charge of general personnel related issues but the manager of the development group is the one that initially contacts prospective employees (candidates).

The manager of the development group is really just a glorified developer. Our development group is small enough that there's not enough management tasks to occupy all of his time. His time distribution is about 75% development and 25% management.

This time distribution is important because it means he's got disparate responsibilities, and in regards to contacting employment candidates that's not all he's doing — he's not sitting around all day talking to candidates. So if a candidates isn't courteous in his communication it leaves an impression — because he's dealing with a small number of candidates, and because he actually does other things.

This is why it surprises me when every once in a while I get a colleague that asks for a recommendation to start our (remember small company) hiring process, but they don't make every effort to remain in good standing!

One scenario went like this:

• A past schoolmate contacted me, said he might be unemployed soon
• I got him in contact with our company and recommended him
• He started talking with our development manager
• Promised to send us a resume, but never sent it
• Development manager and I talked about him, and his unresponsiveness a few times
• The development manager contacted him again (it should be the other way around)
• He got back to us and said he'd decided on a another position

The failure was that he didn't tell us that he'd found another position even when he'd previously agreed to send us a resume. This wasted my time and more importantly the development managers time, annoyed both of us, and thusly made us both think he's an idiot.

Our opinion of him was underscored by the fact that he got a mere consulting / contracting position. So it was a stupid decision on his part given the stability of our company and the fact that we're a development “oasis” in Albuquerque were there are few software companies that offer such a low stress environment.

So, I think there are a few guidelines when talking with small companies:

• Keep in mind that whoever you're talking to about getting hired probably has other responsibilities
• Don't assume that they are dealing with so many candidates that they don't care if you don't follow up with them
• Let them know when things change
• Try not to irritate them because they'll remember you

If you follow the above guidelines it's more likely that even if you find another position you'll remain in good standing with the small company. Small companies can be great but they have different dynamics than bigger companies. Throwing away opportunities is bad in general, so it's important to keep the above in mind when dealing with a small company.

The Annoying XM Dj and "That Song You Love"

I have a theory about those annoying XM Djs and XM devices that allow you to record that favorite song you like.
Those really popular, good songs, always seems to have a voice over in front of them, so if you record it you've got the annoying voiceover in the front (or the end) of the song... I think this is done on purpose, but that's a different theory.
The theory is that the voice over distracts you long enough for you to recognize the song and initiate a recording. Otherwise, without the voice over, you just go in to enjoying the song, enjoying the escapism, relishing in the feeling it evokes — totally not thinking about mudane trivialities like pressing the record button on the XM device.
At that point, why do I even care that it's coming from an XM device — I'm just listening to good music.
Consider the following scenario:

Hey, it's that song I really like (singing)
♪ ... Oh if I were a boy ... ♪ (song ends)
♪ ... Womanizer, womanizer ... ♪
Damn you Britney you don't deservce to follow Beyoncé!
Crap! Why didn't I record that!?

Remember, that's just a dramatization, and the scenario is necessarily reality... but it happens all too often.
If you manage to record the song with the Dj in the front you have to suffer through the Dj's blather everytime you want to enjoy the recorded song. The annoyance is particularly bad on songs with a long non-vocal intro. Dj's classically use this as a license to talk over the song.

Pioneer GEX-XMP3 Portable XM Satellite Radio Receiver w/ Home Kit

Speed Bumps / Humps

Interesting argument on speed bumps:

They don't really work and they're annoying, I just speed to the next one and slow down

In this case I was arguing for the addition of more speed bumps. We just bought a house not to long ago and didn't properly evaluate the irritation factor of our proximity to a main entrance of a large housing division.

I figure there's several points related to speeding in our neighborhood:

• The neighborhood was designed before they started designing housing divisions like mazes to add a kind of "natural traffic calming" — without the funky hardware like traffic circles and speed humps.

  From what I've seen these kind of divisions have no houses facing arterial streets (arterial on the scale of a housing development). All houses are facing a "capillary" street, the undesirable locations are the ones whose backyards face the arterial streets or whose backyards face the large city streets that bound the division.

• Because there are relatively few places to get out of the division people are frustrated and impatient when they are on the verge of exiting — thus the speeding to get out

• People are just jerks and don't care that it's a residential street!

There are other factors like the fact that there's a several speed bumps on the road in question, just none between my house (and about 14 other house) and the exit of the division -- which doesn't quite make sense. People seem to see the exit, notice that there's no speed bumps, and haul tail to the exit.

Regarding the above argument... if speed bumps don't work, I guess I don't really care, at least they're being annoyed by the speed bumps while they're speeding between them. This way there's mutual irritation between me the driver.

Testing

(post dated to reflect when material was discussed in class) Testing is hard... Reading the description of testing the space shuttle engines in Chapter 11 reminded me a great deal of how large software projects are debugged when one doesn't have much of and understanding of the system. You attach a debugger to the running program, try to reproduce the bug, maybe you have a break point set on an entry point that's likely a source of the bug and you follow potentially suspect data down to the point where it gets mangled incorrectly.

If you're lucky you have enough of an understanding of why the program decided to mangle the data that way and you can fix the bug. Otherwise you're left inserting probes and breakpoints in other suspect locations to give you a quick view of data as it moves around the system.

From my own experience top down debugging is tedious and time consuming. Once I've fixed a bug via a top down approach it's really nice if I can pinpoint the source of the problem well enough to test the fix "bottom up". If I can, putting a unit test in place to ensure the bug stays fix solidifies a bottom up test that identifies a failure point and ensures that future changes don't reintroduce the defect -- or, at the least, it identifies a place in the code that my need to be revisited if future changes make a bug fix obsolete.

Re: No Silver Bullet

When I initially started reading No Silver Bullet, by Frederick P Brooks, Jr I was unaware of its first publish date, and first few pages have little temporal evidence. But the farther I got in to the article a couple things show up ... such as referencing time-sharing systems, "high level" languages and unix. All of which have been around for the outset of my programming life and had already reached a more "mature" state long before I came in to the software world.

I suppose the relative agelessness of the first few pages wouldn't have been apparent if I had read the bits of text that dated the article beforehand. I think the agelessness of the text is important. Because it speaks to the fact that the problems Brooks initially defined haven't really changed all the that much in software engineering. I work in a totally different computing world than what was around when the article was written yet the problems he describes don't sound foreign at all to me.

Brooks introduces several things that promised to "solve" the software problem. Yet 20 years later, none of these solutions have broken through to the main stream. People are still getting things done with imperfect software and still making money. Granted, certain methodologies that may've fallen out of the utopia of "perfect software" are very applicable to certain domains.

For most people, software that's "good enough" is all that's needed. For me the most important point Brooks makes is that software is hard, and nothing is going to make software easy, hence the title No Silver Bullet ... pursuing infallible software is fine for academia but it is probably an expensive loosing battle for 80% of software projects. Anecdotally, I've experienced this in my own professional experience through writing my own fair share bugs. The anecdote follows the following premise: write a bug, ship it to customers for period of time, record the period of time that the bug was in wild until it was fixed and released again. If you look at that time period and you look at how much revenue the software generated in that time period you can come up with a rough estimate of the "cost index" of that bug. If you make 150k over a 2 month period selling the software with the imperfection it seems to show that the software was still delivering value, even though it may have an (innumerable) amount of imperfections.

Project Infrastructure Usage Requirements

I kind of see this class as "playing house" for doing more serious project management on bigger projects in a professional setting. One difference is that most of us won't have to set up all the project management goo, we'll just have to use it. Using the term "playing house" is a little demeaning but it communicates some of the vibes I'm sensing from my group members (which might not actually be there, my group members have lots of other classwork to worry about, and this is the only class I'm taking).

One of these "vibes" is that it seems a little artificial to build up all this project management stuff and then actually use it, because we haven't had use for this stuff previously are we aren't forced to use it in this class. We'd probably be better initiated in to using this stuff if we had a standard set of tools that the whole class could play with, along with assignments like Using a Ticket System, or Using a Revision Control System. In the meantime, I don't know how usage the project infrastructure will see since their don't seem to be many hard requirements in the class to do so.