Algoritmo/Estructura de datos Preguntas de entrevista de diseño

Question

¿Cuáles son algunos problemas simples de algoritmo o de estructura de datos relacionados con el "abordaje blanco" que encuentra eficaces durante el proceso de selección de candidatos?

Tengo algunas ideas simples que yo uso para validar habilidades para resolver problemas y que puede expresarse simplemente, pero que tienen alguna oportunidad para la aplicación de algunas heurísticas.

Uno de los conceptos básicos que utilizo para los desarrolladores Junior es:

escribir un método de C# que toma una cadena que contiene un conjunto de palabras (una frase) y gira esas palabras X número de lugares a la derecho. 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 mesa blancos que se utilizan para entrevistar a un candidato y cuáles son algunas de las cosas que usted busca en una respuesta (no es necesario para publicar la respuesta real).

Answer 1

1. Escriba un método que toma una cadena, y devuelve verdadero si esa cadena es un número. (Cualquier cosa con expresiones regulares como la respuesta más eficaz para una entrevista)
2. por favor escriba un método de fábrica abstracta, que doesn' t contiene un interruptor y devuelve tipos con el tipo base de "X". (La búsqueda de patrones, en busca de reflexión, en busca de ellos para que no paso lateral y usar un if else if)
3. favor dividir la cadena "todos; cosa |; | demás |; | en |; | él; re" por el token "|; |". (los tokens de varios caracteres no están permitidos al menos en .net, así que buscando creatividad, la mejor solución es un hack total)

Answer 2

Me gusta el clásico "¿cuál es la diferencia entre un LinkedList y ArrayList (o entre una lista vinculada y una matriz/vector) y ¿por qué elegirías una u otra? "

El tipo de respuesta que espero es uno que incluye la discusión de:

• rendimiento inserción
• iteración rendimiento
• memoria impacto de asignación/reasignación
• impacto de los elementos de la eliminación desde el principio/mediados/finales
• cómo saber (o no saber) el tamaño máximo de la lista puede afectar la decisión

Answer 3

Una vez, cuando estaba entrevistando para 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, empecé a decirle.

Me dijo, "No, no, todo el mundo me da esa solución. Dame una diferente."

Argumenté que mi solución era óptima. Dijo:" Sé que es óptima. Dame una sub-óptima."

Al mismo tiempo, es un buen problema.

Answer 4

me gusta ir a lo largo de un código de la persona que realmente escribió y hacer que me lo explique.

Answer 5

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 un corto tiempo, y lo suficientemente difíciles para eliminarlos.

Answer 6

Responde cualquier pregunta como este con: "¿Cómo podría mejorar este código para que el desarrollador que lo mantiene pueda descubrir cómo funciona fácilmente?"

Answer 7

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 de gráfico, pero sin tanta complejidad de código.

Me gusta el problema Project Euler que pide encontrar la ruta más cara de 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 tablero (http://online-judge.uva.es/p/v100/10077.html).

Answer 8

Una trivial es pedirles que codifiquen una búsqueda de un árbol desde cero desde cero. 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 daré el ejemplo de código siguiente:

# @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; 
    } 
    } 
} 

Entonces les haga las siguientes preguntas. Los pido lentamente, le doy a la gente tiempo para pensar y estoy dispuesto a darles codazos:

1. ¿Qué es en @int cuando se hace este código?
2. 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. Tengo y no estoy buscando buscando una terminología específica, solo un reverso de la estimación de sobre)
3. Sin código, sugiero hacer esto 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 ellos vienen con una solución equivocada poco (o muy), el siguiente conjunto de datos tonta encontrará la mayoría de los errores se ejecuta a través de:

@a = qw(
    hello 
    world 
    hello 
    goodbye 
    earthlings 
); 
@b = qw(
    earthlings 
    say 
    hello 
    earthlings 
); 

supongo que alrededor de 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.

Sugiero usar estas preguntas como filtros. No contrate a alguien porque puede responder esto. Pero si no pueden responder a esto, entonces no los contrate.

Answer 9

pidiéndoles que escriban un algoritmo recursivo para una solución iterativa conocida (es decir, de Fibonacci, etc - que les damos una función iterativa, si es necesario) y luego tener que calcular el tiempo de funcionamiento para él.

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. Resulta algo difícil calcular el tiempo de ejecución hasta que pueda ver que es una estructura en árbol ...

Me parece que este problema cubre muchas áreas. A saber, su, la escritura de código-habilidad capacidad (si se les da una función iterativa) de lectura de códigos (ya que escribir una función recursiva), algoritmo, estructura de datos (para el tiempo de ejecución) ...

Answer 10

Implementar una función que, dada una lista vinculada que puede ser circular, intercambia los dos primeros elementos, la tercera con la cuarta, etc. ...

Answer 11

Esto no afecta necesariamente a las capacidades OOP, pero en nuestro último conjunto de entrevistas utilizamos una selección de código erróneo de la lista Bug of the Month. Al observar que los candidatos encuentran que los errores muestran sus capacidades analíticas, muestra el conocimiento de cómo interpretar el código de otra persona