interview - data structures and algorithms pdf
Algoritmo/Estructura de datos Preguntas de la entrevista de diseño (11)
¿Cuáles son algunos problemas simples de algoritmo o de estructura de datos relacionados con el "abordaje blanco" que considera eficaces durante el proceso de selección de candidatos?
Tengo algunos simples que uso para validar las habilidades de resolución de problemas y que se pueden expresar simplemente, pero tienen alguna oportunidad para la aplicación de algunas heurísticas.
Una de las cosas básicas que uso para desarrolladores junior es:
Escriba un método C # que tome una cadena que contiene un conjunto de palabras (una oración) y gira esas palabras X cantidad de lugares a la derecha. Cuando una palabra en la última posición de la oración se gira, debe aparecer al frente de la cadena resultante.
Cuando un candidato responde esta pregunta, veo que estén disponibles las estructuras de datos .NET y los métodos (cadena.Enlazar, secuencia.Split, Lista, etc ...) para resolver el problema. También busco que identifiquen casos especiales para la optimización. Al igual que la cantidad de veces que las palabras deben rotarse no es realmente X, es un X% de palabras.
¿Cuáles son algunos de los problemas de pizarra que utiliza para entrevistar a un candidato y cuáles son algunas de las cosas que busca en una respuesta (no es necesario que publique la respuesta real).
- Escriba un método que tome una cadena y devuelva verdadero si esa cadena es un número. (Cualquier cosa con expresiones regulares como la respuesta más efectiva para una entrevista)
- Por favor, escriba un método de fábrica abstracto, que no contenga un interruptor y devuelva tipos con el tipo base de "X". (Buscando patrones, buscando la reflexión, buscándolos para no dar un paso al costado y usar un if else si)
- Divida la cadena "every; thing |; | else |; | in |; | he; re" por el token "|; |". (Los tokens de múltiples caracteres no están permitidos al menos en .net, por lo que busca creatividad, la mejor solución es un truco total)
Al entrevistarme recientemente, a menudo me pidieron que implementara una estructura de datos, generalmente LinkedList o HashMap. Ambos son lo suficientemente fáciles de hacer en poco tiempo y lo suficientemente difíciles como para eliminar a los desorientados.
Esto no afecta necesariamente a las capacidades de OOP, pero en nuestra última serie de entrevistas utilizamos una selección de código erróneo de la lista del error del mes . Ver a los candidatos encontrar que los errores muestran sus capacidades analíticas, muestra el saber cómo interpretar el código de otras personas
Haga un seguimiento de cualquier pregunta como esta con: "¿Cómo podría mejorar este código para que el desarrollador que lo mantiene pueda descubrir cómo funciona fácilmente?"
Implemente una función que, dada una lista vinculada que puede ser circular, intercambia los dos primeros elementos, el tercero con el cuarto, etc.
Los gráficos son difíciles, porque la mayoría de los problemas de gráficos no triviales tienden a requerir una buena cantidad de código real para implementar, si se requiere más que un boceto de un algoritmo. Mucho de esto tiende a reducirse a si el candidato conoce o no los algoritmos de recorrido transversal y gráfico más cortos, está familiarizado con los tipos de ciclos y la detección, y si conoce los límites de la complejidad. Creo que muchas preguntas sobre estas cosas se reducen a trivialidades más que a la habilidad de pensar creativamente.
Creo que los problemas relacionados con los árboles tienden a cubrir la mayoría de las dificultades de las preguntas gráficas, pero sin tanta complejidad del código.
Me gusta el problema de Project Euler que pide encontrar el camino más caro en un árbol (16/67); antepasado común es un buen calentamiento, pero mucha gente lo ha visto. Pedirle a alguien que diseñe una clase de árbol, realizar recorridos y luego averiguar de qué cruces podrían reconstruir un árbol también da una idea de la estructura de datos y la implementación de algoritmos. El desafío de programación de Stern-Brocot también es interesante y rápido de desarrollar en un foro ( http://online-judge.uva.es/p/v100/10077.html ).
Me gusta el clásico "¿cuál es la diferencia entre una lista enlazada y una lista de arreglos (o entre una lista vinculada y una matriz / vector) y por qué elegirías una u otra?"
El tipo de respuesta que espero es una que incluye discusión de:
- desempeño de inserción
- rendimiento de iteración
- asignación de memoria / impacto de reasignación
- impacto de eliminar elementos desde el principio / medio / final
- cómo saber (o no saber) el tamaño máximo de la lista puede afectar la decisión
Me gusta revisar un código que la persona realmente escribió y que me lo expliquen.
Pidiéndoles que escriban un algoritmo recursivo para una solución iterativa conocida (es decir, Fibonacci, etc., les damos una función iterativa, si es necesario) y luego pídales que calculen el tiempo de ejecución para ello.
Muchas veces la función recursiva implica una estructura de datos de árbol. La cantidad de veces que la persona no ha podido reconocer eso me desconcierta. Se vuelve un poco difícil calcular el tiempo de ejecución hasta que puedas ver que es una estructura de árbol ...
Encuentro que este problema cubre muchas áreas. A saber, su capacidad de lectura de códigos (si se les otorga una función iterativa), la capacidad de escritura de códigos (ya que escriben una función recursiva), el algoritmo, la estructura de datos (para el tiempo de ejecución) ...
Una cosa trivial es pedirles que codifiquen una búsqueda de un árbol desde cero desde el principio. Sí, si sabes lo que estás haciendo, es trivial. Pero muchos programadores no saben cómo abordarlo.
Uno que me parece más útil todavía es el siguiente. Lo he dado en varios idiomas, aquí hay una versión de Perl. Primero les doy el siguiente ejemplo de código:
# @a and @b are two arrays which are already populated.
my @int;
OUTER: for my $x (@a) {
for my $y (@b) {
if ($x eq $y) {
push @int, $x;
next OUTER;
}
}
}
Luego les hago las siguientes preguntas. Les pregunto lentamente, les doy a las personas tiempo para pensar, y estoy dispuesto a darles codazos:
- ¿Qué hay en @int cuando se hace este código?
- Este código se pone en producción y hay un problema de rendimiento que se rastrea de nuevo a este código. Explica el potencial problema de rendimiento. (Si tienen dificultades, preguntaré cuántas comparaciones se necesitan si @a y @b tienen 100.000 elementos. No busco una terminología específica, solo un reverso de la estimación del sobre).
- Sin código, sugiera que esto sea más rápido. (Si proponen una dirección que sea fácil de codificar, les pediré que la codifiquen. Si piensan en una solución que resultará en que @int se modifique de alguna manera (p. Ej. Orden común), presionaré para ver si se dan cuenta de que no deben codificar la solución antes de comprobar si eso importa).
Si presentan una solución leve (o muy) incorrecta, el siguiente conjunto de datos tontos encontrará la mayoría de los errores que encuentre:
@a = qw(
hello
world
hello
goodbye
earthlings
);
@b = qw(
earthlings
say
hello
earthlings
);
Supongo que aproximadamente 2/3 de los candidatos no responden esta pregunta. Todavía tengo que encontrarme con un programador competente que tenga problemas con él. Descubrí que a las personas con buen sentido común y muy poca experiencia en programación les va mejor que a los programadores promedio con pocos años de experiencia.
Sugeriría usar estas preguntas como filtros. No contrate a alguien porque puede responder esto. Pero si no pueden responder a esto, entonces no los contrate.
Una vez, cuando estaba entrevistando a Microsoft en la universidad, el tipo me preguntó cómo detectar un ciclo en una lista vinculada.
Habiendo discutido en clase la semana anterior la solución óptima al problema, comencé a contarle.
Me dijo: "No, no, todos me dan esa solución. Dame otra".
Argumenté que mi solución era óptima. Él dijo: "Sé que es óptimo. Dame uno subóptimo".
Al mismo tiempo, es un problema bastante bueno.