Qual a importância de um programador saber como implementar um algoritmo QuickSort / MergeSort a partir da memória? [fechadas]

Eu estava revisando minhas anotações e me deparei com a implementação de diferentes algoritmos de classificação.

Como tentei entender a implementação do QuickSort e MergeSort, ocorreu-me que, embora eu faça programação para viver e me considere decente no que faço, não tenho memória fotográfica nem capacidade intelectual suficiente para implementar esses algoritmos sem contando com minhas anotações. Tudo o que lembrei é que alguns desses algoritmos são estáveis ​​e outros não. Alguns levam tempo O (nlog (n)) ou O (n ^ 2) para serem concluídos. Alguns usam mais memória que outros ...

Eu sentiria que não mereço esse tipo de trabalho se não fosse porque minha posição não exige que eu use qualquer algoritmo de classificação além dos encontrados nas APIs padrão. Quero dizer, quantos de vocês têm uma posição de programação em que é realmente essencial que possam se lembrar ou criar esse tipo de coisa por conta própria?

Vamos perguntar a Albert e ver o que ele tem a dizer sobre o assunto:

"Não preciso saber tudo, só preciso saber onde encontrá-lo, quando precisar"

- Albert Einstein , parafraseado

Amém, irmão Albert, amém.

Depois de fazer uma boa pesquisa dos algoritmos essenciais em qualquer disciplina em particular (classificação, pesquisa, o que for), você poderá esquecer os detalhes da implementação até precisar do algo. Nesse caso, procure-o ou use um lib preexistente. Há 25 anos, criei um grande sistema de pesquisa usando árvores B *, mas hoje eu precisaria RTFM para usá-las bem.

1. Não é realmente uma questão de memorização. É uma questão de entender profundamente as classes gerais de algoritmos como dividir e conquistar. Se você realmente entende dividir e conquistar, não precisa memorizar o quicksort. Você pode derivá-lo no local, conforme necessário. Além disso, a verdadeira recompensa não é sequer conseguir derivar o quicksort por conta própria, é que você pode reconhecer quando um novo problema é passível de uma solução de divisão e conquista.

2. Nem todos os trabalhos de programação são iguais. Alguns trabalhos precisam de um conhecimento profundo de algoritmos, outros precisam de pessoas que entendam a teoria dos tipos e outros precisam de pessoas que possam extrair dados de um formulário da Web e movê-los para um banco de dados. Alguns trabalhos ainda precisam de todas essas habilidades ao mesmo tempo. Em que tipo de trabalho você quer trabalhar?

Acho que o único momento em que você precisa se lembrar de tudo é quando se candidata a um emprego, quando precisa encontrar respostas no local e não ter recursos externos.

Eu tive colegas de trabalho reescrevendo quicksort e outros enfeites, mas continuo dizendo para eles voltarem a usar as funções de classificação integradas que estão no idioma. Eu sei que, dependendo dos tipos de projetos em que trabalhamos, precisamos lembrar de outros algoritmos, pois eles geralmente não são incluídos nas bibliotecas padrão, mas a classificação não é uma que surge, pois geralmente é incorporada à linguagem.

Porém, quando precisamos lembrar desses algoritmos, geralmente recorremos ao google ou a um livro, e geralmente não está procurando uma implementação específica, mas qual seria a melhor implementação para o nosso problema.

Apenas lembrar que algoritmo é útil em quais cenários, seria mais do que suficiente para ajudar durante o seu trabalho. De fato, a maioria dos trabalhos de programação não exige a memorização da abordagem, mas eles estão interessados ​​no seu modo de reconhecer o padrão algorítmico quando confrontados com o problema .

De fato, há uma abundância de informações na maioria dos blogs / artigos sobre tópicos de algoritmos. Assim, memorizar a implementação exata não tem importância. As informações mais valiosas estariam obtendo uma idéia básica de quais tipos de algoritmos estão disponíveis e que problema específico eles são bons para resolver . Procurar a implementação exata depois que você souber o que está procurando é bem rápido.

Em resumo, é sempre melhor saber o que você procura e onde estão as referências - que o guiarão à fonte.

A implementação exata não é muito importante. Mas o princípio por trás do mergesort / quicksort - recursão, particionamento etc - é muito básico e todo programador deve entender. Na verdade, esses algoritmos são muito simples de descrever em palavras quando você entende.

Não é realmente um problema se você pode procurar ou pesquisar no Google, é se o programador entende essas técnicas de resolução de problemas e é capaz de aplicar a outras situações.

Eu tenho duas mentes sobre esse assunto. Conheço muitos programadores que não sabem o que é um algoritmo de classificação, mas fazem seu trabalho razoavelmente bem. Eu também acredito na compreensão dos princípios, a fim de realmente entender o domínio.

É difícil para mim ter uma resposta imparcial sobre esse assunto, pois estou programando há tanto tempo que provavelmente esqueci mais algoritmos que atualmente conheço - mas ainda conheço os métodos de classificação mencionados nesta pergunta. Eu acho que os líderes de pensamento em Agile (por exemplo, Ron Jeffries, Alistair Cockburn) têm algumas boas idéias próximas a essa idéia (por exemplo, Shu-Ha-Ri).

Em resumo para esta resposta desmedida: Definitivamente use a API (NIH é um sinal de imaturidade do desenvolvedor), mas sempre entenda os princípios subjacentes. Eu espero que isso ajude.

A classificação e a pesquisa são incrivelmente importantes, se você é fã de Donald Knuth ou deseja ser a próxima página de Larry. Dependendo do negócio em que atua e do nível de concorrência que você pode comandar entre seus candidatos, eu recomendaria que você incluísse alguns dos seguintes conceitos na entrevista.

Ordenação

• Esboço de algum tipo de algoritmo de classificação.
• Liste alguns exemplos de algoritmos de classificação.
• Compare / contraste dois tipos com diferentes características de desempenho.
• Se eles não mencionarem o uso da memória, pergunte sobre isso.

Procurando

• Nomeie o maior número possível de algoritmos de pesquisa.
• Comparar / contrastar dois algoritmos de pesquisa.
• Esboce qualquer pesquisa que não seja linear.

Alguns podem dizer que exigir o código para esses algoritmos é um exagero, a menos que o trabalho esteja em uma ilha deserta sem conexão à Internet. Outra consideração é que, se você tiver 30 minutos e quiser perguntar sobre qualquer outra coisa, para muitos candidatos, implementar o tipo pode levar uma grande parte do seu tempo.