Pregunta técnica de la entrevista: ¿Mi enfoque es correcto?

Question

Recientemente, fui entrevistado por una empresa de software. No pasé la primera ronda.

Tal vez era demasiado lento en la formación de las ideas o resolver problemas y no era lo suficientemente bueno para la empresa que entrevisté para. me gustaría tener una segunda opinión acerca de mi entrevista y no puedo encontrar a nadie mejor que la comunidad stackoverflow.

Así que esta entrevista fue un básico de un

1. Introducción
2. Por qué usted ha solicitado para esta posición?
3. One Techincal Pregunta (detalles a continuación)
4. ¿Cuál es el peor software que ha utilizado? ¿Por qué? Mejore
5. ¿Cuál es el mejor software que ha utilizado? ¿Por qué mejorar?

Pregunta técnica Original (Como preguntó por el entrevistador)

da un rango de números M ..... M + N-1 I contruct una matriz de tamaño N y reemplazar uno de los elemento en esa matriz con un número. ¿Cómo va a encontrar qué elemento se reemplaza?

le preguntó a repetir la pregunta una vez más, como pensaba la entrada no era suficiente para resolver el problema. Repitió la declaración ídem

P. Luego, le pregunté: ¿Es la matriz que obtuvo del rango de número en orden ordenado?
Entrevistador: no es necesario

Q ¿Conocemos la matriz antes de reemplazar un elemento?
Entrevistador: No

Luego, comencé a escribir un pseudo código (mientras pensaba en voz alta). Inmediatamente me di cuenta de que no funcionaría si la matriz original tuviera duplicados. Así que estuve estudiando por un tiempo pensando cómo diablos voy a resolver esto. Entonces finalmente hice preguntas que importaban

Q ¿Cómo se eligen los elementos del rango para formar la matriz?
Entrevistador: Tengo un rango de número M, M + 1, M + 2 .... M + N-1. Un número se escoge solo una vez. Y formo una matriz de tamaño N. (que significa en esencia no hay duplicados y todos los elementos en el rango get escogidas)

Q ¿Qué pasa con el número que se sustituya? ¿Está en el mismo rango?
Entrevistador: Sí lo hace.

Entonces todo quedó claro

Esto era lo que quería decir:
QI tiene un rango de números a partir de H, como M, M + 1, M + 2, 3 + M ... M + N. Formo una matriz de Tamaño N, de manera que cada elemento se selecciona solo una vez y la matriz original no tiene ningún duplicado. Sustituyo uno de los elementos en la matriz con un número en el mismo rango. Averigüe lo que elegí de la gama para reemplazar?

Esto es equivalente a encontrar duplicados en la matriz.Aquí, después del reemplazo, solo habrá un par de duplicados. Podemos encontrarlo fácilmente en O (N^2) tiempo o O (nlogn). Le di los dos algoritmos.

Al final no pude resistir preguntarle "¿Cómo llevo a cabo en esa pregunta? Él Bien dicho que tomó mucho tiempo en responder.

Es evidente que no estaba satisfecho con mi acercamiento a esta pregunta.
¿Qué le parece que debería haber hecho de manera diferente al responder a esta pregunta?

Answer 1

Esta es una entrevista clásica "RID dle ". De hecho, es bastante fácil de resolver en O (n) usando el truco ralu descrito.

Una de las cosas que enseñamos en Data Estructuras 1, es que cuando su dominio es limitado, es posible usarlo para una función mejor que O (nlogn) [obviamente, ordenar un dominio sin ningún conocimiento adicional no puede hacerse en menos de eso]. Entonces, cuando conozca su dominio, debe encender una pequeña bombilla roja en su cabeza en alguna parte :-)

Creo que debería haber señalado inmediatamente la pregunta sobre los duplicados. Dejaría en claro que la pregunta no está bien formada. De lo contrario, solo pensó que eres lento (aunque en realidad es su culpa ...).

También creo que las preguntas 4,5 son buenas preguntas. Muestran qué experiencia tiene un solicitante y cómo piensa el solicitante. Entonces, es posible que hayas fallado en la entrevista por algo que dijiste allí.

Answer 2

Si me pregunta correctamente puede resolver esta vez en O (n).

1. encontrar dos mismos elementos el uso de "control" de tamaño N
2. establecer uno de estos elementos a 0.
3. maquillaje suma de elementos y restar de la suma calculada y usted tiene el elemento que falta/reemplazado (suma de los elementos es (2M + N-1) * (N)/2

EDIT:

Explicación de 1. punto de (encontrar dos mismos elementos uso de "control" de tamaño N)

1. Si no no sabe M encontrarlo (encontrando elemento más pequeño es O (n), sólo un bucle)
2. Alocate serie h de tamaño N y fijar los elementos a 0 (puede ser de tipo BOOL) a través
3. ir tabla 1 y comprobar en la ubicación adecuada exploración off h
4. si es 1, entonces usted tiene colission, de lo establecido código 1.

para la última parte:

for(i=0;i<N;i++) 
{ 
    if(h[a[i]-M] == 1) return i; 
    h[a[i]-M] == 1; 
} 

Answer 3

Dado que no se especifican límites en la cantidad de memoria que puede usar, hay una solución O (N): inicialice una matriz A de tamaño N a cero. Mire cada elemento b en la lista y marque A [b - M] = 1. Luego recorra A y devuelva c si A [c] == 0.

Answer 4

Es absolutamente imposible que alguien responda su pregunta correctamente.Está escribiendo esto después del hecho de una manera clara.

• quizás divagó en su entrevista o no se expresó tan claramente como en esta pregunta!
• tal vez no hacer las preguntas correctas con la suficiente rapidez
• tal vez no eran tan rápido en la captación después de ser dado punteros (o no tan rápido como sus competidores)
• quizás el entrevistador no lo hizo como el hecho de que inició la escritura de código antes de pensar en el problema

he dado entrevistas incontables donde he sentido que la persona que estoy entrevistando sabe la respuesta a la pregunta que estoy haciendo. Simplemente no pueden decirme: están nerviosos o confundidos en sus pensamientos. Los procesos de pensamiento de algunas personas claramente se adelantan a sus bocas y saltan confusamente. Apuesto a que algunos de ellos se van y construyen respuestas perfectas como la tuya ...

No puedo decirte si hiciste estas cosas; quizás su entrevistador estaba siendo irrazonable. Sé que tuve entrevistas que no fueron tan bien para lo que sentí que no era culpa mía. Pero en este momento, me encuentro pensando cosas como:

• ¿Podría poner a esta persona en frente de un usuario?
• está (s) uniendo los puntos de esto lo suficientemente rápido?
• ¿han entrado sin pensarlo dos veces?
• ¿cómo se comparan con la persona que vi hace una hora?

Answer 5

O (nlogn) Solución El uso de árboles B: ..

Suponiendo que construimos un árbol binario como la matriz se hace demasiado ... ya que la complejidad de construir un árbol de bin es O (n) . Otra suposición es que cualquier elemento igual o menor que se coloca a la izquierda del árbol binario.

Aquí verificamos que cada elemento de la matriz para su nodo izquierdo sea el mismo que el nodo primario para cada subárbol. Para atravesar el árbol toma un tiempo de O (logn). Tratamos de encontrar un duplicado para cada uno de los n elementos. Por lo tanto, el tiempo total es O (nlogn).

O (n) Solución usando árboles B y recursión:

podemos construir una btree como se mencionó anteriormente y utilizando los mismos supuestos. Verifique que cada hijo izquierdo sea igual que el padre. Haz lo mismo con los dos niños. La condición de detención para la recursión es si child es NULL. Por lo tanto, cada nodo se comprueba una vez. Entonces el tiempo total tomado es O (n).