Experiencia de entrevista de Dunzo para pasante de SDE (en el campus)

Prueba en línea : Tenía 2 preguntas. No recuerdo exactamente las preguntas. pero primero fue una pregunta de array y el segundo fue una mochila modificada. Resolví el segundo completamente y el primero parcialmente. Obtuve 131/200 puntos. Recibí correo para la primera ronda de entrevistas.

Ronda 1: Fue la ronda DSA/Algo. El entrevistador fue genial y servicial. Me hizo 2 preguntas y me dio 1 hora para resolverlas.

1. Dada una string s. Encuentre la subsecuencia lexicográficamente más pequeña de tamaño k.

   Ex  -  s = "satbz" , k = 3
   Ans - "abz"

   Primero le dije a la solución de fuerza bruta. Luego le dije a la solución O (n ^ 2) usando algo de recursividad. Así que el entrevistador me pidió que hiciera en O(n). Después de un tiempo, incluso dio la pista de usar la pila. Luego dije la solución y escribí el código. fue correcto

2. Dada una array de tamaño MxN que consta de { L, R, U, B }.

   El valor ‘L’ representa que puede ir a la izquierda desde esa celda. de manera similar, ‘R’ a la derecha, ‘U’ arriba y ‘B’ abajo.

   Estás en la celda superior izquierda (1, 1). Puede cambiar cualquier valor de celda a ‘L’, ‘R’, ‘U’, ‘B’. Debe encontrar cambios mínimos en la array para que exista una ruta desde (1,1) a (m, n) celda.

   Ex-  [ [R , B , L],
              [L , B , R],
              [R , R , U]]
   Ans = 0 
   As there already exist a path , 
   (1,1)->(1,2)->(2,2)->(3,2)->(3,3). 

   Se dieron 3 casos de prueba más. Le dije un enfoque de dp y funcionó en los casos de prueba dados. No quedaba tiempo para el código.

Recibí correo para la segunda ronda de entrevistas. 

Ronda 2 (DS/Algo): También fue ronda DSA/Algo.

Las preguntas que se hicieron fueron:

1. Dado un árbol binario completo, debe indicar la cantidad de Nodes presentes en él.

   Restricciones:

   1 <= Número de Nodes (‘N’) <= 500000.

   ¡Solo se le dará el puntero al Node raíz y nada más!

   Estado del problema: resuelva lo anterior en ceil(log(N) * log(N)). La complejidad del espacio puede ser O(Log(N)) o incluso O(1).

   Resolví el problema anterior en O(log(N) * log(N)) con tiempo-espacio constante.

   Sugerencia: piense en las propiedades de un árbol binario completo.

2. Dada una array de n elementos. Devuelve la suma de min y max de todos los subarreglos.

   All the elements are distinct
   N = 3
   A = [2, 1, 4 ,3]
   Expected answer = 
   {1} + {2} + {3} + {1, 2} + 
   {2, 3} + {1, 2, 3}
   
   = (1 + 1) + (2 + 2) + (3 + 3) + 
   (1 + 2) + (2 + 3) + (1 + 3) = 24
   
   So, 24 is the required answer.

   Di la solución O(n^2) y la codifiqué. Dije el enfoque para O(n).

   Sugerencia: https://leetcode.com/problems/sum-of-subarray-minimums

Ronda 3 (Tecnología/Cultura): El entrevistador hizo 1 pregunta DSA. 

1. https://www.geeksforgeeks.org/maximum-size-rectangle-binary-sub-matrix-1s/

   Le dije la solución de inmediato porque es un problema bastante estándar. Hablamos de mi currículum y terminó en 15 minutos.

En general, tuve una gran experiencia. Todos los entrevistadores fueron de gran ayuda.  

Recibí la llamada de que soy seleccionado.