Classificação das perguntas da entrevista FizzBuzz (1), implementando malloc (10) [fechado]

Gostaria de ter sua opinião sobre a dificuldade da seguinte pergunta da entrevista:

Encontre a sub-matriz contígua com soma máxima em uma matriz de números inteiros em O (n) tempo.

Esse problema de som trivial ficou famoso por Jon Bentley em seu Programming Pearls, onde ele o usa para demonstrar técnicas de design de algoritmos.

Em uma escala de 1 a 10, sendo 1 o teste FizzBuzz (ou HoppityHop ) e 10 implementando a função C stdlib malloc (), como você classificaria o problema acima?

Acho que as pessoas que podem responder melhor a essa pergunta são aquelas que leram Programming Pearls e tentaram resolver esse problema por conta própria. Para motivar aqueles que não o fizeram, 'Programming Pearls' é apresentado muitas vezes na lista dos 10 principais livros de programação.

Alguns comentários podem ajudar a obter uma classificação melhor:

• A implementação do malloc () não é tão formidável quanto parece. Veja a linguagem de programação C da K&R, por exemplo. Às vezes, é perguntado na Microsoft .

• Observação do CLRS sobre a solução de problemas: geralmente é mais difícil resolver um problema do zero do que verificar uma solução claramente apresentada, especialmente quando se trabalha com restrições de tempo .

Isso realmente depende do desenvolvedor.

Se malloc tivesse 10 anos, eu classificaria esse problema como 20. Mas, novamente, eu já fiz malloc antes e provavelmente poderia fazê-lo novamente.

Alguém que cometeu esse problema ou conhece o algoritmo apropriado da parte superior da cabeça fará com que seja 5 e malloc () seja 10.

O problema com esse tipo de pergunta é que, se você as tiver feito antes que elas sejam fáceis, é um teste para saber se você já viu esse algoritmo antes. Portanto, não gosto deles para entrevistas.

Agora, para testes em que você dá ao desenvolvedor alguns dias, é um teste perfeitamente bom, porque se ele não conhece o algoritmo, você tem a chance de fazer a pesquisa e se atualizar, e é um teste não apenas seu conhecimento, mas sua capacidade de adquirir novos conhecimentos.

Eu acho que a classificação deve ser bidimensional, pelo menos. FizzBuzz- mallocdescreve a faixa em um eixo, eu chamaria de "complexidade tecnológica". Mas essa dimensão única certamente não é suficiente para descrever o problema. Para resolver o problema em questão, o desenvolvedor deve pensar mais do que o código , enquanto a implementação mallocexige mais disciplina de codificação do que criação de algoritmos complexos.

Então, aqui está como eu organizaria esses problemas:

Para ilustrar meu argumento, eu adicionei a classificação de mesclagem paralela ao gráfico, pois, eu acho, é um bom exemplo de tarefa sofisticada tecnologicamente e algoritmicamente.

Eu acho que é consideravelmente mais difícil que o FizzBuzz ou o HoppityHop - esses dois nada mais são do que um simples if-else ou switch-case em um loop.

O sub-array máximo exigirá uma análise mais profunda do problema subjacente - não é algo que você esperaria ver em uma aula de programação para iniciantes, pois requer habilidades matemáticas mais altas do que um problema do tipo FizzBuzz. Esse problema tem uma aparência semelhante ao problema de caminho mais curto, resolvido pelo algoritmo de Dijkstra - talvez seja uma especialização do problema de caminho mais longo .

Na sua escala de 1 a 10, eu provavelmente classificaria entre 3 e 5.

* Enquanto o servidor estava inoperante, descobri que o problema máximo do subarray tem sua própria página na wikipedia.

Dou um 3. Além da maioria dos programadores que entrevistei, mas é um problema fácil para os que recomendei.