Nota do tradutor: O artigo original foi publicado em uma série de tweets.Você provavelmente já leu várias explicações sobre como lidar com listas vinculadas é uma má pergunta para uma entrevista. Antes de tudo, quero explicar de onde ele veio. Clipe em todos, mergulhe na
teoria dos
jogos HISTÓRIA!
Embora a indústria de software tenha prosperado nos anos 80, ela realmente decolou nos anos 90. Nesta década, o número de trabalhadores da indústria nos Estados Unidos triplicou e
superou um milhão de pessoas . Com o crescimento explosivo, surgiu a necessidade de contratar muitos funcionários e avaliá-los.
O que precisa ser avaliado? Bem, antes de tudo, o conhecimento das línguas. Segundo o TIOBE, em 1986-2006, o C era a linguagem mais popular do mundo, seguida pelo C ++. Em 2006, Java entrou em primeiro lugar, mas C ficou por perto.
C trabalhou próximo ao ferro sem abstrações desnecessárias. Um dicionário Python vazio consome até 288 bytes, ou seja, 5% da memória total da Apple II de primeira geração. Abstrações são muito caras, muito sobrecarga. Se você precisar de uma estrutura de dados complexa, deve construí-la usando matrizes, estruturas e ponteiros.
(O C ++ acabou sendo melhor nesse aspecto, uma vez que uma biblioteca padrão de modelos apareceu lá, mas foi adotada oficialmente apenas em 1998 e começou a ser usada em qualquer lugar muito mais tarde. Lembro-me de ler os argumentos sobre sobrecarga, mesmo em 2005).
Listas vinculadas são uma estrutura de dados necessária que permite alocação dinâmica de memória com menos risco de estouros de buffer. E você teve que escrever essas listas vinculadas manualmente. Isso significa que você tinha que manipular manualmente os ponteiros nas listas vinculadas.
Em outras palavras, nos anos 90, a pergunta "Como expandir uma lista vinculada" não é um teste de pensamento algorítmico ou conhecimento de estruturas de dados, é uma pergunta "Você programou em C?". Nesse caso, a resposta é trivial para você. Caso contrário, é impossível responder (idealmente).
Atualmente, a maioria de nós não programa em C. Mas a pergunta obsoleta não desapareceu, mas foi modificada. Eu suspeito que o motivo é que um grande número de programadores continuou a perguntar e perguntar, sem entender o contexto histórico e as razões pelas quais essa pergunta apareceu.
A situação provavelmente foi ajudada cimentando o best-seller
"Hacking a Programming Interview" . A autora Gail Luckman MacDowell trabalhou na especialidade entre 2000 e 2008 e provavelmente escreveu um livro com base em sua própria experiência. O livro tornou-se uma referência de mesa para entrevistar empresas - e listas vinculadas foram estabelecidas na lista de perguntas padrão.
Sem um contexto histórico, as listas vinculadas foram apresentadas como "habilidades de resolução de problemas" como uma pergunta. Mas isso contradiz completamente o objetivo original: se você testar seu conhecimento do idioma, não deseja que pessoas que não estejam familiarizadas com esse idioma respondam à pergunta (ou seja, "resolva o problema").
Por exemplo, a pergunta "Determine se existe um loop na lista vinculada". O candidato deve apresentar uma solução como "tartaruga e a lebre", publicada em um
artigo científico de 1967 . Você pede ao candidato para repetir a pesquisa em 30 minutos!
Talvez quando passamos a questões como “resolução de problemas”, calibramos a complexidade, tomando como guia as listas vinculadas. O que distorce completamente a escala.
(A propósito: mais um argumento para listas vinculadas é “verificar o conhecimento fundamental da ciência da computação”. Bem, se sim, por que todo mundo não pergunta sobre máquinas de estados finitos determinísticos? Teorema de Rice? Como o compilador funciona? As estruturas de dados são uma parte muito pequena da ciência da computação não representativo).
Para resumir, a questão de uma lista vinculada foi um bom teste da capacidade de escrever em C e agora se tornou um teste ruim de "Você pode resolver problemas?"
Moral: pense novamente em fazer perguntas sobre listas vinculadas em uma entrevista.
Outra moral: muito pode ser aprendido da história.
(Terceira moral: se você vir um artigo pela metade e pensar: "Oh, é mais fácil lançar um projeto em uma série de tweets", isso é uma armadilha, não caia nela)