Facebook, Uber, y otras empresas con equipos potentes de ingeniería son conocidas por tener entrevistas difíciles; en la parte de programación lo que valoran son los conocimientos algorítmicos y no los conocimientos sobre lenguajes concretos, por lo que estas entrevistas las puedes hacer en el lenguaje que quieras.
Un par de semanas antes de la parte algorítmica de la entrevista te dan acceso a un portal de prácticas que tiene un montón de ejercicios tipo.
Os pongo algunos que me han parecido interesantes. Por cierto, durante la entrevista no puedes ejecutar tu código, así que hay que prestar mucha atención a escribir el código correctamente y hacer debug mental...
Importante: Soluciones de fuerza bruta nunca sirven. Fijaos que los datos de entrada pueden tener un millón de elementos.
Paso de anuarios
Hay n estudiantes, numerados del 1 al n, cada uno con su propio anuario. Quieren pasar sus anuarios y que los firmen otros estudiantes.
Se les da una lista de n enteros arr[1..n], que se garantiza que es una permutación de 1..n (en otras palabras, incluye los enteros de 1 a n exactamente una vez cada uno, en algún orden). El significado de esta lista se describe a continuación.
Inicialmente, cada alumno tiene su propio anuario. A continuación, los alumnos repetirán los dos pasos siguientes cada minuto: Cada alumno i firmará primero el anuario que tiene en sus manos (que puede ser suyo o de otro alumno), y luego se lo pasará al alumno arr[i-1]. Es posible que arr[i-1] = i para cualquier i, en cuyo caso el alumno i se pasará su anuario a sí mismo. Una vez que un alumno ha recibido su propio anuario, lo conservará y no participará más en el proceso de paso.
Está garantizado que, para cualquier entrada válida posible, cada alumno acabará recibiendo su propio anuario y nunca acabará teniendo más de un anuario a la vez.
Debe calcular una lista de n enteros de salida, cuyo elemento en i-1 es igual al número de firmas que habrá en el anuario del alumno i una vez que lo reciba de vuelta.
Firma
int[] findSignatureCounts(int[] arr)
Entrada
n está en el rango [1, 100.000].
Cada valor arr[i] está en el rango [1, n], y todos los valores en arr[i] son distintos.
Salida
Devuelve una lista de n enteros de salida, como se ha descrito anteriormente.
Ejemplo 1
n = 2
arr = [2, 1]
salida = [2, 2]
Pase 1:
El alumno 1 firma su propio anuario. A continuación, pasa el libro al estudiante que se encuentra en arr[1], que es el Estudiante 2.
El estudiante 2 firma su propio anuario. Luego le pasa el libro al estudiante en arr[2], que es el Estudiante 1.
Pase 2:
El alumno 1 firma el anuario del alumno 2. Luego se lo pasa al estudiante en arr[1], que es el Estudiante 2.
El alumno 2 firma el anuario del alumno 1. Luego se lo pasan al estudiante en arr[2], que es el Estudiante 1.
Pase 3:
Ambos estudiantes tienen ahora su propio anuario, por lo que el proceso está completo.
Cada estudiante ha recibido 2 firmas.
Ejemplo 2
n = 2
arr = [1, 2]
salida = [1, 1]
Pase 1:
El alumno 1 firma su propio anuario. Luego pasa el libro al estudiante que está en arr[1], que es él mismo, el estudiante 1.
El estudiante 2 firma su propio anuario. Luego le pasa el libro al estudiante en arr[2], que es él mismo, el Estudiante 2.
Pase 2:
Ambos estudiantes tienen ahora su propio anuario, por lo que el proceso está completo.
Cada estudiante ha recibido una firma.
Mediana de un stream
Te dan una lista de n enteros arr[0..(n-1)]. Debes calcular una lista output[0..(n-1)] tal que, para cada índice i (entre 0 y n-1, ambos inclusive), output[i] sea igual a la mediana de los elementos arr[0..i] (redondeada al entero más cercano).
La mediana de una lista de enteros se define como sigue. Si los enteros estuvieran ordenados, entonces:
Si hay un número impar de enteros, entonces la mediana es igual al entero del medio en el ordenamiento.
En caso contrario, si hay un número par de enteros, entonces la mediana es igual a la media de los dos enteros más centrales del ordenamiento.
Firma
int[] findMedian(int[] arr)
Entrada
n está en el rango [1, 1.000.000].
Cada valor arr[i] está en el rango [1, 1.000.000].
Salida
Devuelve una lista de n enteros output[0..(n-1)], como se ha descrito anteriormente.
Ejemplo 1
n = 4
arr = [5, 15, 1, 3]
salida = [5, 10, 5, 4]
La mediana de [5] es 5, la mediana de [5, 15] es (5 + 15) / 2 = 10, la mediana de [5, 15, 1] es 5, y la mediana de [5, 15, 1, 3] es (3 + 5) / 2 = 4.
Ejemplo 2
n = 2
arr = [1, 2]
output = [1, 1]
La mediana de [1] es 1, la mediana de [1, 2] es (1 + 2) / 2 = 1,5 (que debe redondearse a 1).
Subarrays contiguos
Se le da un array arr de N enteros. Para cada índice i, debe determinar el número de subarrays contiguos que cumplen las siguientes condiciones:
El valor del índice i debe ser el máximo elemento en el subarray contiguo, y
Estos subarrrays contiguos deben empezar o terminar en el índice i.
Firma
int[] countSubarrays(int[] arr)
Entrada
Array arr es una lista no vacía de enteros únicos que van de 1 a 1.000.000.000
El tamaño N está entre 1 y 1.000.000
Salida
Un array donde cada índice i contiene un entero que denota el número máximo de subarrays contiguos de arr[i]
Ejemplo:
arr = [3, 4, 1, 6, 2]
salida = [1, 3, 1, 5, 1]
Explicación:
Para el índice 0 - [3] es el único subarray contiguo que comienza (o termina) con 3, y el valor máximo en este subarray es 3.
Para el índice 1 - [4], [3, 4], [4, 1]
Para el índice 2 - [1]
Para el índice 3 - [6], [6, 2], [1, 6], [4, 1, 6], [3, 4, 1, 6]
Para el índice 4 - [2]
Por lo tanto, la respuesta para la entrada anterior es [1, 3, 1, 5, 1]
Hynkel