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

58

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

Cuando intenté dar sentido a la implementación de QuickSort y MergeSort, se me ocurrió que aunque programo para vivir y me considero decente en lo que hago, no tengo ni la memoria fotográfica ni la capacidad intelectual para implementar esos algoritmos sin confiando en mis notas. Todo lo que recuerdo es que algunos de esos algoritmos son estables y otros no. Algunos tardan O (nlog (n)) u O (n ^ 2) en completarse. 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 que no sea el que se encuentra en las API estándar. Quiero decir, ¿cuántos de ustedes tienen una posición de programación donde realmente es esencial que puedan recordar o crear este tipo de cosas por su cuenta?

algorithms John Smith
fuente
13
Debe recordar que existe una solución y cuándo usarla. Luego vaya a los documentos e impleméntelo. Si no hubiera sabido acerca de quicksort o mergesort, aún estaría usando Bubblesort y vería cómo su programa realiza un rastreo y encuentra soluciones deficientes cuando aumentan los datos.
Pieter B
1
Además de las buenas respuestas que se mencionan a continuación, tenga en cuenta también que muchas compañías requieren (1) conocer la complejidad de tales algoritmos, (2) tener fluidez para implementarlos en una pizarra.
sakisk
3
Estoy seguro de que es importante memorizar estos algos por la frecuente aparición de Google sin conexión. : o
Lee James
Necesita conocer su desempeño, casos de uso, etc. Saber cómo implementarlos de memoria es algo que solo requieren las empresas de tecnología en las entrevistas.
sakisk
@PieterB, no estoy de acuerdo. Uno no necesita saber sobre 'mergesort' y 'quicksort' para el 'algoritmo de clasificación de mejor rendimiento' de Google
hyankov

Respuestas:

117

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

"No necesito saberlo todo, solo necesito saber dónde encontrarlo, cuándo lo necesito"

- Albert Einstein , parafraseado

Amén, hermano Albert, amén.

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

Peter Rowell
fuente
55
Esta cita es dudosa: soy "incapaz de encontrar ninguna evidencia sustancial que conecte el dicho con Einstein" .
Wok
99
¿Cómo responde eso a la pregunta? Él dijo: "No necesito saberlo todo", no dijo "No necesito saber nada". Algunas habilidades son fundamentales, y toda la cuestión era si una determinada información pertenecía a la categoría de habilidades fundamentales o no.
Konrad Rudolph el
1
Pensar que el objetivo es memorizar la clasificación rápida es perder el punto de la pregunta. Por supuesto, en el mundo real, si necesitaras una clasificación rápida genérica, usarías la rutina de la biblioteca o buscarías el código y lo copiarías. La prueba es para ver si comprende la recursividad, los invariantes de bucle, etc., y pedirle que apunte rápidamente un algoritmo de clasificación es solo una demostración realmente simple de ese conocimiento. Si no eres capaz de derivar una clasificación rápida de 20 líneas en el acto, ¿cuántas cosas haces rutinariamente de manera ineficiente o incorrecta sin siquiera saberlo?
Larry Gritz
3
@Larry: Creo que he olvidado más de lo que muchos programadores saben sobre los detalles de los algoritmos, y la clasificación rápida desde cero es uno de ellos, por una muy buena razón, he elegido leer sobre cosas de alto nivel y usar lenguajes de alto nivel. que permanecer en cuencos con detalles de implementación de bajo nivel. Francamente, no me importa qué tipo de rutina de biblioteca estoy usando, puede usar polvo de hadas y hadas en lo que a mí respecta. Los doctores le dirán a la O () por tamaño, eso es todo lo que necesito saber.
mattnz
2
@mattnz: un seguimiento algo tardío de su "tamaño O ()". Una cosa que aprendí por las malas fue que con un gran conjunto de datos, una mala localidad de referencia puede abrumar por completo el O (). Es posible que tenga un problema O(n log n), pero si obtiene una gran cantidad de errores de caché o (Dios no lo quiera) golpea el disco, entonces eso n log nserá solo un buen recuerdo.
Peter Rowell el
49

  1. No es realmente una cuestión de memorización. Se trata de comprender profundamente las clases generales de algoritmos como dividir y conquistar. Si realmente comprende dividir y conquistar, entonces no necesita memorizar la clasificación rápida. Puede volver a derivarlo en el acto según sea necesario. Además, la verdadera recompensa ni siquiera es poder derivar la clasificación rápida por su cuenta, es que puede reconocer cuándo un nuevo problema es susceptible de una solución de divide y vencerás.

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

Charles E. Grant
fuente
55
No creo que sea posible entender QuickSort sin recordar QuickSort. No es una cosa complicada y arcana, son solo dos ideas genéricas combinadas. Lo mismo se aplica al tipo de fusión, pero allí solo tiene una idea: P
drxzcl
No estoy de acuerdo con el segundo punto. todos los trabajos son iguales, solo el entrevistador cambia. éste sabe ordenar muy bien y piensa que todo buen programador debe saber ordenar, porque eso es todo lo que sabe y le importa.
IAdapter
2
@IAdapter, seguramente bromeas! Sé por experiencia propia que el conocimiento y las habilidades que necesitaba para mi primer trabajo escribiendo macros TROFF para una compañía de software retráctil son muy diferentes de los que necesito para mi trabajo actual en un laboratorio de biología computacional.
Charles E. Grant
@ CharlesE. La mayoría de las veces, Interviwer no comprueba si tienes las habilidades que necesitas para hacer tu trabajo (no recuerdo la última pregunta de JavaScript / CSS que me hicieron y hago webapps).
IAdapter
10

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

He tenido compañeros de trabajo que reescriben quicksort y otras cosas, pero sigo diciéndoles que vuelvan a usar las funciones de clasificación integradas que están en el idioma. Sé que, dependiendo de los tipos de proyectos en los que trabajemos, debemos recordar otros algoritmos, ya que generalmente no se incluyen en las bibliotecas estándar, pero la clasificación no surge porque generalmente está integrada en el lenguaje.

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

scaryrawr
fuente
6

Solo recordar qué algoritmo es útil en qué escenarios sería más que suficiente para ayudarlo durante su 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 al problema .

De hecho, hay abundante 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 una implementación exacta una vez que sabe 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.

EL Yusubov
fuente
5

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

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

hgh
fuente
3

Soy de 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 comprender verdaderamente 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 actualmente, pero todavía sé los que se mencionan en esta pregunta. Creo que los líderes de pensamiento en 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 inestable: definitivamente use la API (NIH es un signo de inmadurez del desarrollador), pero siempre comprenda los principios subyacentes. Espero que esto ayude.

Mike Polen
fuente
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 tener entre sus candidatos, le recomendaría que incluya algunos de los siguientes conceptos en la entrevista.

Clasificación

  • Bosquejo de algún tipo de algoritmo de clasificación.
  • Enumere algunos ejemplos de algoritmos de clasificación.
  • Compare / contraste dos tipos con diferentes características de rendimiento.
  • Si no mencionan el uso de memoria, pregunte al respecto.

buscando

  • Nombra tantos algoritmos de búsqueda como puedas.
  • Comparar / contrastar dos algoritmos de búsqueda.
  • Dibuje cualquier búsqueda que no sea la búsqueda lineal.

Algunos podrían decir que exigir el código para estos algoritmos es excesivo a menos que el trabajo esté 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.

DesarrolladorDon
fuente
Solía ​​pensar que pedirle a la gente que programara entrevistas era una tontería, pero no creerías la cantidad de personas con currículums aparentemente fantásticos y que responden las preguntas "sociales" con gran éxito, pero que, por la vida de ellos, no pueden anote una implementación correcta de 'strcat' o alguna otra función simple. Varias veces esto me ha salvado de contratar a alguien que, si no hubiera sido por la tonta pregunta de codificación, podría haber causado un dolor interminable y arrastrar al equipo con incompetencia.
Larry Gritz