05 Jul 10 Algoritmos básicos são importantes, você consegue melhorar este?

Bom, este post é mais minha opinião do que qualquer outra coisa, mas o que motivou a escrita dele foi este post no dzone: Will the real programmers please stand up? automated edition, onde o autor diz que apenas 1 em 20 entrevistados por ele conseguiam resolver de forma satisfatória testes simples como:

Escreva em C um método que inverta uma lista encadeada.

Claro que algumas restrições eram aplicadas, a assinatura do método não deveria ser alterada e a estrutura que armazenaria a lista encadeada também não deveria ser alterada. Elas eram apresentadas como o código abaixo:

1
2
3
4
5
6

typedef struct nodetype {
  int value;
  struct nodetype *next;
} node;
 
node* reverselist(node*)

Tentando automatizar um pouco o processo, ele tentou apresentar o código pronto com um bug, para que o bug fosse encontrado, mas o candidato sempre poderia escolher reescrever o código do zero se seguisse as regras acima.
Bom, olhei o código e achei que a recursividade utilizada estava só piorando o algoritmo, ele precisa de duas iterações para inverter a lista, então eu pensei, por que não escrever uma versão sem recursividade e que faça o processo todo em apenas uma iteração?
Bom, a minha resposta para o problema foi esta que esta abaixo:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

	static class LinkedItem {
		int value;
		LinkedItem next;
 
		public LinkedItem(int value) {
			super();
			this.value = value;
		}
	}
 
	private static LinkedItem reverseLinkedList(LinkedItem currentHead) {
		LinkedItem nextHead = null, previousHead = null;
		while (currentHead != null) {
			nextHead = currentHead;
			currentHead = nextHead.next;
			nextHead.next = previousHead;
			previousHead = nextHead;
		}
		return nextHead;
	}

Eu escrevi em java, mas não faz diferença pois para o algoritmo que escrevi a unica diferença seria a sintaxe.
Para testar isto escrevi um programa simples que inicializa uma lista encadeada com números de 1 a 10 e imprime a lista antes e depois desta ser invertida. O código esta abaixo, se alguem quiser fazer uma versão melhor deste algoritmo por favor poste a sua resposta nos comentários.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

package test;
 
public class Main {
	static class LinkedItem {
		int value;
		LinkedItem next;
 
		public LinkedItem(int value) {
			super();
			this.value = value;
		}
	}
 
	private static LinkedItem reverseLinkedList(LinkedItem currentHead) {
		LinkedItem nextHead = null, previousHead = null;
		while (currentHead != null) {
			nextHead = currentHead;
			currentHead = nextHead.next;
			nextHead.next = previousHead;
			previousHead = nextHead;
		}
		return nextHead;
	}
 
	public static void main(String[] args) {
		LinkedItem head = initializeSampleList();
		printLinkedList(head);
		head = reverseLinkedList(head);
		printLinkedList(head);
	}
 
	private static LinkedItem initializeSampleList() {
		LinkedItem it = new LinkedItem(1), head = it;
		for (int i = 2; i < 10; i++) {
			LinkedItem it2 = new LinkedItem(i);
			it.next = it2;
			it = it2;
		}
		return head;
	}
 
	private static void printLinkedList(LinkedItem it) {
		while (it != null) {
			System.out.printf("%d ", it.value);
			it = it.next;
		}
		System.out.println();
	}
}

Eu achei espetacular a idéia deles de criar um site para automatizar este tipo de smoke test para entrevista de emprego de programadores, se o cara não consegue resolver isto deveria estudar um pouco mais antes de querer trabalhar com programação mesmo.
Mas se a idéia for testar a habilidade com algoritmos acredito que o candidato deveria poder escolher em que linguagem implementar, caso contrario, em alguns casos a habilidade com a linguagem estaria sendo testada, e acho que estas duas coisas deveriam ser testadas em separado.

E vocês o que acham sobre isto? Sobre este tipo de testes?
Já fizeram algum teste parecido com este em alguma entrevista de emprego?
E se você é o entrevistador, gostou da idéia deste tipo de teste? Acha util ou desnecessário?
Utiliza alguma técnica alternativa?
Olha o código produzido pelo candidato em projetos open source?

Bom, acho que por enquanto é isto

PS.: me decepcionei com a minha demora para implementar este algoritmo simples, levei uns 10 minutos, quando comecei a escrever achei que seria algo natural e funcionaria de primeira. Isto deve ter sido causado pela facilidade que temos hoje, como um Collections.reverse do java ou um [].reverse do ruby por exemplo. Raramente temos que lidar diretamente com este tipo de algoritmo básico, mas saber implementa-los é extremamente importante, pelo menos na minha opinião