Experiencia entrevista Directi | Conjunto 25 (fuera del campus para ingeniero de plataforma)

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 100133

Restricció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 babab

Entonces 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)?