Interview Code Snippets for 10/2009

Today’s potential interview question is to reverse a linked list, without recursion. This one can be rather tough on the brain if you don’t think visually, but the basic idea here is to keep a pointer to:

• Keep a pointer to the next node so that you don’t lose a way to access it once you reverse the direction of the prior node’s ‘next’ pointer.
• Keep a pointer to the last node so that you have a way of pointing the current node back (the above is required so that you don’t lose where it formerly pointed.)
• ‘Inchworm’ your way forward in this manner until you’ve hit everything, and at the end repoint the head to be where you’re at.

Here’s the code (Note that NodePtr is simply a typedef of a boost::shared_ptr – it’s a ‘smart’ pointer.):

void LinkedList::reverse()
{
	if((_head == NULL) || (_length == 1))
	{
		return;
	}
	else
	{
		NodePtr previous = NodePtr();
		NodePtr current = _head;
		NodePtr next = NodePtr();
		while(current)
		{
			next = current->next;
			current->next = previous;
			previous = current;
			current = next;
		}
 
		_head = previous;
 
	}
}

C++

Nursing memory management wound caused by blasting leg off with a C++ shotgun. It’s OK C++, I don’t hate you, I just wish you would retire.

Coffee and See Plus Plus

Do you remember the first time you had coffee? A lot of people relate their first experience as a bad one, and that coffee is an acquired taste. I can’t relate to that because I’ve always loved coffee, from my very first taste, but I understand the notion, and I want to relate that idea to C++ for a minute. C++ is a language that by all modern standards is an awful mess, but one that is arguably most important to learn and understand due to the manual management of the heap and stack.

Ok, so lets say you dive into C++ because you’re interested in knowing everything there is to know about programming. You discover it’s like your coffee experience; It’s bitter, it smells funny, and gives you jitters, but you keep on sipping it because you know it will give you benefits. Fast forward 6 months, and you’re practically hooking it up to your arm with an IV needle. Now you feel very comfortable with it, and you’ve learned a significant amount of other related knowledge as a result of your endeavours. You’re ready to move on to new things, satisfied that you used it as a learning tool, but are you really done with it? Ohh no.

And in that sense, it’s more like cocaine than coffee.

The gaming industry, or any industry that possesses an interest in high-performance computing applications, is addicted to C++. Regardless of how far managed code and garbage collection has come, or how good virtualization abstractions have gotten, they cling to it proclaiming “JUST ONE MORE HIT MAN, JUST ONE MORE HIT”. I sympathize on the one hand because C++ ought to be mandatory learning material for computer science students (because it does teach you about how things work under the covers), but at the same time, haven’t we come far enough with the performance of other languages that we can just go ahead and take C++ out back of the shed?

Networking

Today I take another paragraph from one of Joel Spolsky‘s posts and quote it here for emphasis on something I find very important:

“When a programmer complains about “politics”, they mean—very precisely—any situation in which personal considerations outweigh technical considerations. Nothing is more infuriating than when a developer is told to use a certain programming language, not the best one for the task at hand, because the boss likes it. Nothing is more maddening than when people are promoted because of their ability to network rather than being promoted strictly on merit. Nothing is more aggravating to a developer than being forced to do something that is technically inferior because someone higher than them in the organization, or someone better-connected, insists on it.”

“You do have to pay competitively, but all said, of all the things that programmers look at in deciding where to work, as long as the salaries are basically fair, they will be surprisingly low on their list of considerations, and offering high salaries is a surprisingly ineffective tool in overcoming problems like the fact that programmers get 15″ monitors and salespeople yell at them all the time and the job involves making nuclear weapons out of baby seals.”

Vision

“If somebody tells you that the job of a bricklayer is to lay bricks on bricks then you will probably not want to be a bricklayer. But what if somebody told you about building a cathedral? It is the same with programming. You need a vision to make it meaningful.”

Abstractions

Today I went back and re-read Joel Spolsky’s advice The Law of Leaky Abstractions and it hits a nail on the head:

“Learn how to do it manually first, then use abstractions to save time. Code generation tools which pretend to abstract out something, like all abstractions, leak, and the only way to deal with the leaks competently is to learn about how the abstractions work and what they are abstracting. So the abstractions save us time working, but they don’t save us time learning. And all this means that paradoxically, even as we have higher and higher level programming tools with better and better abstractions, becoming a proficient programmer is getting harder and harder.”