Asistí a muchas entrevistas y estuve en ambos lados de la confrontación. Ahora es el momento de compartir los rompecabezas más interesantes con otros. Para las entrevistas debe ser interesante y memorable, y no miserable y desmotivador.
Algunos comentarios
- Todas las tareas en lógica y / o programación. Sin connotaciones psicológicas y escotillas redondas.
- La decisión no se da intencionalmente. Sin embargo, le aseguro que casi todas las tareas tienen una solución simple y hermosa. ¡Disfrútalo!
Las tareas
Aquí están
Cadenas espejo en SQL
Supongamos que tenemos una tabla con una columna de cadena y queremos encontrar filas similares en función de alguna condición (por ejemplo, puede ser una búsqueda de texto completo o alguna función interna que recibe dos valores en la entrada y devuelve verdadero / falso). Entonces, escribimos auto-unión y, por supuesto, obtenemos duplicados entre los valores. Es decir, obtenemos pares de espejo como resultado y los valores totales son exactamente dos veces más de lo que quisiéramos. Pregunta: ¿cómo eliminar del resultado uno cualquier elemento de cada par espejo y dejar solo valores únicos hasta permutaciones?
Consejos y trucos- Hay una propiedad no obvia de cadenas y sentencias SQL básicas que puede usar ...
- O puede buscarlo en Google, si la solicitud es correcta, la respuesta estará en el primer enlace a stackoverflow.
Encontrar agujeros con SQL
Esta es una excelente tarea para evaluar el conocimiento de todas las características básicas de SQL.
Supongamos que tenemos una tabla con una columna int. No sabemos nada sobre los valores mínimos / máximos en él. Además, no sabemos nada sobre el número de filas en la tabla y, en general, varía y no debemos confiar en él. También sabemos que entre los valores hay omisiones cuya longitud no excede uno. Por ejemplo, para una tabla de 5 (cinco) elementos: 1, 2, 4, 6, 7. Pregunta: escriba una sola consulta SQL utilizando solo los operadores básicos (es decir, sin procedimiento ni variables), que devolverán el valor de todos los "agujeros". Para el ejemplo anterior, el resultado debe ser 3, 5. Recuerde que no hay valores NULL en los huecos. Los valores 3 y 5 no están físicamente en la tabla.
Propina- Si el movimiento falla, escriba varias consultas o use pl / sql, y luego, si su idea es correcta, puede ir lógicamente a una consulta.
Pista- la solicitud más hermosa será si la solicitud de las condiciones de entrada anteriores no devuelve "3, 5", sino "3, 5, 8".
Bucles en una lista individualmente vinculada
Este es un problema sobre algoritmos y complejidad.
Supongamos que tenemos una lista finita, simplemente conectada. Sabemos que probablemente tiene un ciclo. Es decir, uno de los siguientes elementos se refiere a uno de los anteriores. Es necesario describir el método para encontrar ciclos en dicha estructura en un tiempo finito. Además, debe proporcionar una estimación del tiempo y la memoria necesarios para ejecutar el algoritmo propuesto.
Continuación
Es necesario modificar el resultado para que la complejidad de la memoria sea O (1). Es decir, para que el consumo de memoria no dependa del tamaño de la lista.
Pista- recuerde que así como la masa se puede convertir en energía, también lo es la complejidad del tiempo, se puede convertir en consumo de memoria y viceversa.
Almacenamiento de valor clave
Otra tarea para coescribir código y discutirlo durante la escritura.
Escriba el almacenamiento de valores clave en el idioma que desee. Agregue la función set_all , que toma un valor y lo establece para todas las claves existentes. Estime el tiempo y los costos de memoria para la implementación resultante.
Ahora haga que set_all funcione para O (1).
¿Y puede asegurarse de que la complejidad de los métodos get y set permanezca al principio, y set_all continúe funcionando para O (1)? En caso afirmativo, implemente. Si no, pruebe por qué esto no es posible.
Salvando gente
Y en esta tarea necesita pensar y razonar con el entrevistado. Y la implementación es una cuestión de tecnología y no es particularmente interesante.
Imagina que tenemos un grupo de personas. La cantidad no importa. Todo el grupo está alineado en la parte posterior de la cabeza entre sí y se pone un sombrero negro o blanco en cada cabeza. Nadie sabe el color del sombrero que usa. Sin embargo, todos ven lo que sucede frente a ellos y escuchan lo que sucede detrás de ellos. Después de eso, un extraño con una pistola llega al final del último grupo. Él pregunta, "¿de qué color es tu sombrero?" La respuesta solo puede ser negra o blanca. No puede haber otros mensajes. Si una persona ha adivinado, lo dejarán ir. De lo contrario, se produce un disparo y, en cualquier caso, el proceso se repite con el "nuevo" último miembro de la cola.
Una aclaración importante: antes de comenzar esta experiencia inhumana, todos los miembros del grupo pueden reunirse y pensar en su estrategia de supervivencia.
Pregunta: ¿cómo maximizar la cantidad de sobrevivientes y existe una estimación precisa de la cantidad de sobrevivientes dependiendo del tamaño del grupo?
Propina- ¿Piensa cómo cada miembro puede recopilar toda la información disponible y transmitirla en un bit?
Pista- tal vez par / impar o el operador XOR puede ayudarlo?
Eso es todo Ahora es tu turno de resolver cualquiera de los problemas y hablar sobre tu interesante selección de entrevistas.