Reverse! Reverse!

A long time in another career I was invited to go for an interview by the research lab of a very prestigious company whose name I can't remember. I think it might have sounded something like BiteProLost. It's a long story as to exactly why, but they asked me to reverse a linked list in the interview and I cocked it up. I couldn't do it. It was very embarrassing.

For a while I was playing with the idea of improving my coding skills by improving my visualisation skills. I had this idea that people who were good coders (and I have known a few) are good visualisers. Note, this is very different from thinking that you can make programming easier by making it easier because you have to able to manipulate these visual images in programmatic ways that are very hard to do visually.

So, on the train yesterday, on the way to London, I sat down and tried to imagine what the answer to the reversed linked list problem might be (yes, after a few years, it's still smarting). I was surprised that the answer that I came up with was a recursive one. I'll try to explain what I was thinking. See if it works for you.

OK, first of all, you have to understand what a linked list is. A link list is a set of storage places, each of which has an address - like a phone number. The way you deal with a list is that you're given a pointer to its head which is like being given the first storage space. In my head I image each item on the list to be a barrel that has it's address embossed into the wood (that can't change) next to the embossed address is the address of the next item in the list - you can change that so it's written on a post-it note pad. If you follow the addresses written on the post-it notes the trail will lead you from barrel to barrel until finally you reach a barrel which has the post-it note with "NULL" written on it. That's the end of the list. Each of the barrels - the items in the list - have contents. If I bent over I could see what was in the barrel (each barrel is cut away on one side) but for this exercise, I don't need to know what's inside. So how do I reverse this list?

Well, I look at the address that I've been given for the first barrel. I know because this is the first barrel that in the final, reversed list, it will have to be the last, so the first thing I need to do is write "NULL" on the post-it pad on the first barrel. But hang on, before I do that, I need the address of the next barrel which is already written there. I take the post-it off the top of the pad and stick it to my clipboard. I don't know where I got my clipboard from, but I've got one. Now I write "NULL" on the pristine post-it pad.

Now I know where I'm going and I'm just about to set off when I realise that when I get to the next barrel, I'm going to need the address of this one. So I write the number of this barrel - the embossed number that can't be changed on a piece of paper on my clipboard. And off we go, comparing the number on the barrels with the number on my clipboard.

Now I'm starting to get the hang of this. I know that I'm going to need the number on the post-it pad on the new barrel. So I screw up the old post-it and stick the new one on my clipboard. I write the address I've just come from - the address on the paper on my clipboard - onto the pristine post-it pad. Then I cross that address out and write the address embossed on the barrel. And off we go to the next barrel.

I keep doing the manoeuvres outlined in the last paragraph until I get to a barrel where the post pad has "NULL" written on it. Now I know I'm at the end of the list. I remove the post it note with NULL written on it, write the address from my clipboard on the pristine pad and then write the embossed address from the barrel onto my clipboard. I take this number back to the start (some cloud that I emerged from into these forest of barrels). This is the address of my new reversed linked list.

Oof - is that any help? I'm not sure. After I'd sat and thought that all through on the train, I wrote some pseudo-code and today I wrote it in C. All of that too-ing and fro-ing turns out to only be these 10 lines in C:

List_Pointer reverse_list(List_Pointer next_ptr,List_Pointer list)
{
 List_Pointer temp = (List_Pointer) list->next;
 list->next = next_ptr;
 if(temp == NULL)
 {
  return list;
 }
 return reverse_list(list, temp);
}

This post was influenced by some reading I've been doing recently about ways of improving your memory. I read "How to Develop a Super Power Memory" by Harry Lorayne which is very interesting but doesn't mention "Memory Palaces" which are mentioned in Derren Brown's Trick of the Mind Book. I think you might be able to use some of these methods to get a much better visualisation of the inner workings of a computer programme.

There's some support for this from a quote of Charles Simonyi quoted in Robert X. Cringely's Accidental Empires: "I have to really concentrate, and I might even get a headache just trying to imagine something clearly and distinctly with twenty or thirty components" says Simonyi "When I was young I could easily imagine a castle with twenty rooms with each room having ten different objects in it. I can't do that anymore." Could improving your memory using memory techniques drastically improve your performance as a computer programmer? I don't know, but it's worth trying to find out.

Here comes everybody (part 3)

"Professional self-conception and self-defense, so valuable in ordinary times, become a disadvantage in revolutionary ones, because professionals are always concerned with threats to the profession." Academics for example?

Here comes everybody (part 2)

When a profession has been created as a result of some scarcity, as with librarians or television programmers, the professionals are often the last ones to see it when that scarcity goes away. It is easier to understand that you face competition than obsolescence.

Here comes everybody

I'm reading "Here Comes Everybody" by Clay Shirky in preparation for a meeting of the Digital Futures reading group next Monday. I'm not sure whether this is for my work with Agile Lab or for my work with Sodurga

Disparate Measures

Somniscapes - a Live Installation Performance by Marina Tsartsara
Degree show, University of Brighton Dance Studio 16 April 2008.

We had to take our shoes off. And for the first few moments, we were completely in the dark. What was that noise? Something else beside the sounds of the traffic passing and the ever present Brighton sound of pigeons and seagulls.

When the lights came up we finally saw what the trickling sound was that had made us slightly uncomfortable. Each of the three figures in olive drab and brown, in their own spotlights, were covered in uncooked rice (my guess would be American Easy Cook). Each figure was spread across, or lay in between a kind de-constructed four-pronged pommel horse. Each of the legs a different length.

Two of the figures began to move in their spots. The other lay apparently asleep. It was impossible to arrange yourself anywhere in the room so that you could see both dancers. We were told we could sit anywhere and walk around during the performance if we wanted, but of course most people clung to the edges. I placed myself as squarely as I could between the two moving dancers. Still it was hard to tell if they might be moving together, or reacting to each other.

What did emerge was the radically different styles of the two dancers. For one, as she moved, shifting her weight between the wooden pillars, each movement seemed to flow into the next. Even though there was no music, there was a musicality, a wish for music. With each change of direction, there seemed a muffling of a flourish.

The other dancer's movements were in contrast. She didn't yearn for any outside force. There was no need for flourish. She was self-contained, endlessly creative, self originating. She made things happen. No movement depended on nor anticipated another.

In the end, dancers slowed and fell between the pillars that they danced on. Angular postures, legs at odd angles suggested it wasn't a gentle finish. A fall or a crash maybe.

And then the third dancer stirred with yet another style of movement. Again slowly, but more hesitant, haltering and faltering than the other two. Before she managed to really get going, the lights were out and it was all over.

I don't know if the piece had an explicit, designed meaning, but, for me personally, a meaning was clear. Some parts of our life are poetic, lyrical, melodic and yearning. Some parts are stolid, dogged, self-sufficient and creative in the face of difficulties. The parts don't line up, they don't move in synch, they're too far apart. Some parts only start to stir when it's too late.