Método de solicitud: solicité Directi a través de la recomendación de un empleado.
Ronda 1: Ronda de codificación en línea (Codechef, 90 minutos)
: Fácil, Ad hoc
Declaración
Se le da una string de dígitos numéricos, debe encontrar el número más pequeño posible usando estos dígitos sin ceros a la izquierda.
Ejemplo
Si la entrada es 330101, la respuesta es 100133Restricción
Longitud de la string <= 10^5
Declaración
Se le dan dos strings, digamos A y B, de la misma longitud N. Puede intercambiar A[i] y B[i] por todas las i entre 1 y N, inclusive. No puede intercambiar dos caracteres dentro de A o dentro de B. Además, solo puede intercambiar un carácter en A con el carácter en el mismo índice en B, y con ningún otro carácter. Puede realizar esta operación cero o más veces.
Desea modificar las strings a través de las operaciones de tal manera que la cantidad de caracteres únicos en las strings sea pequeña. De hecho, si n(A) es el número de caracteres únicos en A y n(B) es el número de caracteres únicos en B; desea realizar las operaciones de modo que max(n(A),n(B)) sea lo más pequeño posible.
Imprime el valor de max(n(A),n(B)) después de todas las operaciones.
Ejemplo
Si la entrada es
ababa bababEntonces la salida debería ser uno porque podemos intercambiar y hacer el par de strings
(aaaaa, bbbbb)Restricciones
1 <= T <= 100 1 <= length(A) <= 16 length(B) = length(A)
Problema de DP de mochila modificado
Ronda 2: Ronda de algoritmos (Skype, 45 – 50 minutos)
Se le da una cuadrícula cuadrada (NxN); Cada ubicación en la cuadrícula es un ladrillo (B) o está vacío (_).
El número total de ladrillos es exactamente igual a la cantidad necesaria para construir un «muro» en la cuadrícula. Ver ejemplo para una comprensión más clara.
Es decir, al final, todos los ladrillos (B) deben colocarse en las ubicaciones de los límites.
Para mover un ladrillo desde la ubicación <x,y> a <i,j> |ix| + |jy| se utiliza combustible.
Cada ladrillo en la cuadrícula se puede mover a cualquier ubicación en el límite con la misma probabilidad. ¿Cuál es el valor esperado del combustible requerido para hacerlo? Cada ladrillo se puede mover como máximo una vez.
Ejemplo
Al final (después de mover todos los ladrillos), la cuadrícula debería verse así:
B B B B B _ _ B B _ _ B B B B B
Sugerencia
Te dan las ubicaciones iniciales de todos los ladrillos y conoces las posiciones finales.
Dado que todos los ladrillos son iguales, puede colocar cualquier ladrillo en cualquier posición límite.
Digamos que hay ubicaciones límite ‘b’ = b ladrillos
. Por lo tanto, debe asignar las ubicaciones antiguas a las nuevas.
En el enfoque de fuerza bruta, sería O(b!) probar todas las ubicaciones.
Pero puede hacerlo mejor con un poco más de información sobre cómo se suman las probabilidades en forma de ladrillo en lugar de en forma de disposición.
Esperado: O(n)
Ronda 3: Ronda de algoritmos (Skype, 45 – 50 minutos)
Ronda 4: Ronda de conocimientos técnicos (Skype, 45 minutos)
- Habla sobre un proyecto tuyo en profundidad. Esté preparado para responder cualquier pregunta al respecto. También puede hablar sobre su proyecto de pasantía. Hablé sobre mi proyecto GSoC en mi caso.
- Esté preparado para responder cualquier cosa que esté en su currículum. Me pidieron que hablara sobre otro proyecto que figura en mi currículum.
- ¿Cómo implementarías la funcionalidad diff de git? Esté preparado para preguntas de seguimiento y optimizaciones adicionales en el acto.
- Me dieron un código de muestra, con una función add_balance() y una subtract_balance(), y me pidieron que explicara el problema si dos subprocesos acceden a él. ¿Cómo lo rectificarías? (Usando el bloqueo mutex)
- Pregunta de seguimiento: ¿Cómo (cree) se implementan las operaciones de bloqueo mutex en el sistema operativo?
- Indexación de bases de datos
- ¿Qué son los índices? ¿Cómo son útiles?
- Si tuviera que construir un índice, ¿qué estructura de datos usaría?
- ¿Por qué Btree y no BST normales (cuando el número de comparaciones es mayor para Btrees)?
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA