¿Qué tan importante es para un programador saber cómo implementar un algoritmo QuickSort / MergeSort desde la memoria? [cerrado]

57

Estaba revisando mis notas y me topé con la implementación de diferentes algoritmos de clasificación.

Cuando intenté darle sentido a la implementación de QuickSort y MergeSort, se me ocurrió que aunque realizo la programación para la vida y me considero decente en lo que hago, no tengo la memoria fotográfica ni la capacidad intelectual para implementar Esos algoritmos sin depender de mis notas. Todo lo que recordé es que algunos de esos algoritmos son estables y otros no. Algunos toman O (nlog (n)) o O (n ^ 2) tiempo para completar. Algunos usan más memoria que otros ...

Sentiría que no merezco este tipo de trabajo si no fuera porque mi posición no requiere que use ningún algoritmo de clasificación distinto a los que se encuentran en las API estándar. Quiero decir, ¿cuántos de ustedes tienen una posición de programación en la que realmente es esencial que puedan recordar este tipo de cosas por su cuenta?

    
pregunta John Smith 07.10.2012 - 00:38

7 respuestas

117

Preguntemos a Albert y veamos qué tiene que decir sobre el tema:

  

"No necesito saber todo, solo necesito saber dónde encontrarlo, cuando lo necesito"

     

- Albert Einstein , parafraseado

Amén, hermano Albert, amen.

Una vez que haya realizado una buena encuesta de los algoritmos esenciales en cualquier disciplina en particular (ordenar, buscar, lo que sea), puede olvidarse de los detalles de la implementación hasta que realmente necesite el algo, en cuyo caso debe buscarlo. o usar un lib preexistente. Hace 25 años construí un sistema de búsqueda principal utilizando B *-tríos, pero hoy necesitaría RTFM para usarlos bien.

    
respondido por el Peter Rowell 07.10.2012 - 04:21
48
  1. No es realmente una cuestión de memorización. Es una cuestión de entender profundamente las clases generales de algoritmos como dividir y conquistar. Si realmente entiende dividir y conquistar, entonces no necesita memorizar el orden rápido. Puede volver a derivarlo en el lugar según sea necesario. Además, la verdadera recompensa ni siquiera es poder re-derivar de manera rápida por su cuenta, es que puede reconocer cuando un problema nuevo es susceptible de una solución de dividir y conquistar.

  2. No todos los trabajos de programación son iguales. Algunos trabajos necesitan un profundo conocimiento de los algoritmos, otros necesitan personas que entienden la teoría de tipos y otros solo necesitan personas que puedan eliminar datos de un formulario web y trasladarlos a una base de datos. Algunos trabajos incluso necesitan todas esas habilidades a la vez. ¿En qué tipo de trabajo quieres trabajar?

respondido por el Charles E. Grant 07.10.2012 - 03:16
10

Creo que la única vez que necesita recordar todo es cuando solicita un trabajo cuando tiene que encontrar respuestas en el momento y no tener recursos externos.

He tenido compañeros de trabajo que reescriben quicksort y todo eso, pero sigo diciéndoles que vuelvan a usar las funciones de clasificación incorporadas que están en el idioma. Sé que, dependiendo de los tipos de proyectos en los que trabajamos, tenemos que recordar otros algoritmos, ya que generalmente no se incluyen en las bibliotecas estándar, pero la clasificación no es una que surja, ya que generalmente está integrada en el lenguaje.

Sin embargo, cuando necesitamos recordar esos algoritmos, generalmente recurrimos a Google o a un libro, y generalmente no estamos buscando una implementación específica, sino cuál sería la mejor implementación para nuestro problema.

    
respondido por el scaryrawr 07.10.2012 - 01:02
6

Solo recordar qué algoritmo es útil en qué escenarios, sería más que suficiente para ayudarte durante tu trabajo. De hecho, la mayoría de los trabajos de programación no requieren la memorización del enfoque, sino que están interesados en su forma de reconocer el patrón algorítmico cuando se enfrentan con el problema .

De hecho, existe una gran cantidad de información en la mayoría de los blogs / artículos de programación sobre temas de algoritmos. Por lo tanto, memorizar la implementación exacta no tiene importancia. La información más valiosa sería obtener una idea básica sobre qué tipo de algoritmos están disponibles y qué problema específico son buenos para resolver . Buscar la implementación exacta una vez que sepa lo que está buscando es bastante rápido.

En resumen, siempre es mejor saber qué busca y dónde están las referencias , que lo guiarán a la fuente.

    
respondido por el EL Yusubov 07.10.2012 - 00:57
5

La implementación exacta no es muy importante. Pero el principio detrás de mergesort / quicksort - recursión, partición, etc., es muy básico y todo programador debería entenderlo. Estos algoritmos son realmente muy simples de describir en palabras una vez que los entiendes.

No es realmente un problema si puede buscarlo o si puede buscarlo en Google, es si el programador entiende estas técnicas de resolución de problemas y puede aplicar a otras situaciones.

    
respondido por el hgh 12.10.2012 - 18:25
3

Tengo dos mentes sobre este tema. Conozco a muchos programadores que no saben qué es un algoritmo de clasificación, pero hacen su trabajo bastante bien. También creo en la comprensión de los principios para entender realmente el dominio.

Es difícil para mí tener una respuesta imparcial sobre este tema, ya que he estado programando durante tanto tiempo que probablemente haya olvidado más algoritmos que conozco en la actualidad, pero aún sé los clasificadores mencionados en esta pregunta. Creo que los líderes de opinión de Agile (por ejemplo, Ron Jeffries, Alistair Cockburn) tienen algunas buenas ideas cerca de esta idea (por ejemplo, Shu-Ha-Ri).

En resumen a esta respuesta ambigua: definitivamente use la API (NIH es un signo de inmadurez del desarrollador), pero siempre entienda los principios subyacentes. Espero que esto ayude.

    
respondido por el Mike Polen 07.10.2012 - 17:27
2

La clasificación y la búsqueda son increíblemente importantes, tanto si eres fanático de Donald Knuth como si quieres ser el próximo Larry Page. Dependiendo del negocio en el que se encuentre y del nivel de competencia que pueda imponer entre sus candidatos, le recomendaría que incluya algunos de los siguientes conceptos en la entrevista.

Ordenar

  • Bosquejo de algún tipo de algoritmo de clasificación.
  • Listar algunos ejemplos de algoritmos de ordenación.
  • Compare / contraste dos clases con diferentes características de rendimiento.
  • Si no mencionan el uso de la memoria, pregúntalo.

Buscando

  • Nombra tantos algoritmos de búsqueda como puedas.
  • Compara / contrasta dos algoritmos de búsqueda.
  • Dibuje cualquier búsqueda que no sea una búsqueda lineal.

Algunos podrían decir que requerir el código para estos algoritmos es excesivo a menos que el trabajo se encuentre en una isla desierta sin conexión a Internet. Otra consideración es que si tiene 30 minutos y desea preguntar sobre cualquier otra cosa, para muchos candidatos, implementar el tipo podría tomar una gran parte de su tiempo.

    
respondido por el DeveloperDon 07.10.2012 - 04:35

Lea otras preguntas en las etiquetas