So Tycho said this was just about the most fascinating thing he'd read lately, and I have to agree.
Jack Thompson would both love and hate Reiser; he's a case study for both sides of the argument that violent videogames create violent people. I'd definitely be interested in seeing where the kid, Rory Reiser ends up in 10 years.
I'm at work and it is boring me stupid.
It has Uma Thurman in it. I was waiting for her to flip out and go on a crazed killing spree. Apparently the future will be just like the present, only cars will have green headlights.
Smoking pays a fairly big part in the proceedings, which I guess symbolises that these guys aren't perfect - one of them is Sky Captain in a wheelchair (action figure available from Mattel). Apparently, Titan is just like tobacco smoke in a red wine glass. Sounds awesome.
The film, released in 1997 and set in the 'not too distant future', mentions laws that ban discrimination on the basis of genome. In April this year, such laws were actually passed. The Genetic Information Nondiscrimination Act makes genoism illegal in the US. Holy crap! I guess that means that, in twenty years time, all hallways will be as funky as this one:
My father was right. It didn't matter how much I lied on my resume. My real resume was in my cells. Why should anybody invest all that money to train me when there were a thousand other applicants with a far cleaner profile? Of course, it's illegal to discriminate, 'genoism' it's called. But no one takes the law seriously. If you refuse to disclose, they can always take a sample from a door handle or a handshake, even the saliva on your application form. If in doubt, a legal drug test can just as easily become an illegal peek at your future in the company.
I'm away skiing until Saturday evening. Hopefully the bad weather will have moved far enough south for me to get some runs in tomorrow. Wish me luck.
Lucifer, I've been so fucking bad,
And you're the best excuse I've ever had.
Just a note
To say hello
While I watch
The garden grow
And here's a weed
And here's a thorn
And here's a welcome
I've outworn
Just spilling ink
Upon a page
Green for envy
Red for rage
Blue is something
I can't hide
And black is just
Too beautiful to keep inside
North Western motorway is quiet tonight
A blue green flicker from the windows
Of every house that we pass by
Is it because of my mould farm? Is it because of aspergillus fillius? Is it something from a while ago? From when we're at school, and you said you got a hickey from Judy Bailey, and I told everyone it was from a vacuum cleaner? It it because I drank all the orange juice? Is it because I drank all the apple juice? Is it something subtle? Is it because I eat too loudly?
It's business, it's business time!
Business hours are over!
It's common for programmers to be given interview questions about programming. Usually, these questions involve implementing quick, small algorithms - for example, you might be asked to write a function that reverses its (string) input.
Today, I heard an interesting question to do with linked lists. A linked list is a data structure consisting of a number of nodes, each of which has (in this case) a single link to another node. Mathematicians: think 'directed graph'.
Here's an example of a simple linked list:
+------+
head ----> | Node |
|------|
| +data| +------+
| +next| ----> | Node |
+------+ |------|
| +data|
| +next| ----> NULL
+------+
To traverse the list, we'd start at 'head', a pointer to the first node. We'd then grab successive nodes, by using the 'next' property of whatever node we're up to. Finally, we'd reach NULL, the end of our list.
The advantage of a linked list is that it's quick (O(1)) to add items to (and remove them from) one end of the list, which makes the linked list very helpful for implementing a stack. For those interested, retrieving a particular node from a linked list is a O(n) task, because the list must be traversed until the node is found.
Anyway, there's a class of linked list we can call cyclic. A perfectly cyclic list is one where the nth node's 'next' pointer points to the same place as 'head':
+--------------------+
| |
v |
+------+ |
head ----> | Node | |
|------| |
| +data| +------+ |
| +next| ----> | Node | |
+------+ |------| |
| +data| |
| +next| -+
+------+
But, consider that a cyclic list need not be perfectly cyclic. Instead, the cycle could involve any subset of the list. Here's an example of a very small cycle:
+---+And a larger one:
v |
-> [ ] -> [ ] -> [ ] -+
+-----------------+
v |
-> [ ] -> [ ] -> [ ] -> [ ] -+
The question was: write a (good) algorithm that checks if a linked list is cyclic. The algorithm should be optimised for memory usage.
At first, that doesn't seem too hard. Here's a naïve solution:
Solution 1: For each node, if the node's next pointer is NULL, then the list is not cyclic.
This idea is perfectly correct, and we'll use it in all our solutions; if we ever come across a NULL pointer, our job is done.
But there's a major problem with this idea: we can't implement it as an algorithm to find cyclic lists. To see why, consider that, in a cyclic list, we don't know when we've reached the end of the list and started looping back round. Which is a major problem: if we can't tell when we've finished traversing the list, and we don't come across a NULL, this decision method won't finish.
If our linked list is perfectly cyclic then it's not a worry. We simply need to check if we've reached 'head' - if we have, we've checked all the nodes without coming across a NULL, and the list is not (perfectly) cyclic. But consider a non-perfect cyclic linked list, like the one I gave above. In this case, we can only tell if we've looped back upon ourselves by checking against every node we've visited. And that brings us to:
Solution 2: For each node, store the node's location. As we traverse the list looking for a NULL pointer, compare the current node with the list of previously visited locations. If the current node is there, we've finished traversing the list, and it is cyclic.
This is a working solution. The problem is that it is inefficient, both in terms of space (memory) and time (CPU cycles).
To see why it's slow, consider a list of a hundred items. As well as traversing the list (an O(n) operation), you'd be doing a number of comparisons (0 < x <= n) at each node. This works out to be something like n2 (= 10,000) operations.
More pertinently, we're storing a pointer to each node in memory. So, we're using n * [the size of a pointer] units of space. The question didn't specify CPU time as a constraint. So, let's try optimising the memory we're using.
Solution 3: For each node, iterate from the head node to the current node, checking if the node points to any of the nodes between the two.
This solution uses two pointers that keep track of where in the list we are up to. The first, the 'outside' pointer, just goes through the list. The second, the 'inside' pointer, checks that none of the nodes between the start of the list and the 'outside' node are pointed to by the 'outside' node.
So, in effect, this algorithm targets the right-most node in the diagrams above - the node with the long pointer. Here's another way to think about it: instead of storing the nodes visited, this method uses the fact that the list has already stored them. We only need remember our position.
While this algorithm is very efficient in memory, it's about as slow as solution 2. The number of comparisons done at worst case is something like n2 / 2 (triangular), which means it's still O(n2).
This is a correct answer to the question. It's as efficient in memory as you can get. But it's a little unsatisfying. There is another solution - I found it fairly remarkable. It uses the same amount of memory, and is O(n):
Solution 4: Start with two pointers to the first element of the list. Now, move the first pointer one node ahead of its current position. Move the second pointer two nodes ahead of its current position. If the first pointer equals the second, the list is cyclic. Repeat.
This algorithm is, to my mind, not very intuitive. I call it the racing pointers method. It works because:
If the list is perfectly cyclic, then the faster pointer will catch the slower one exactly half way through the list. I think the worst performance you could wring out of the algorithm would be n. I think it's fairly clear that the fast pointer can be at most min(size of cycle, n/2) nodes behind the slow pointer.
In any case, I think it's a beautiful method, because it's so different from the others.
