Entrevista Flipkart | Conjunto 12 (en el campus)

Recientemente me seleccionaron en Flipkart durante una campaña de colocación en el campus. Estas fueron las preguntas a las que me enfrenté.

• RONDA DE CODIFICACIÓN EN LÍNEA (2 PREGUNTAS)
  1. Dados dos conjuntos de elementos, tenemos que encontrar si el conjunto resultante de MCM de los dos conjuntos sería igual o no.
     Ej: – Deje que el conjunto sea X = {2, 3, 4}
     Entonces el conjunto MCM estaría formado por todos los MCM de cualquier subconjunto del conjunto dado.
     En este caso, LCM(X)={2,3,4,6,12}
     Restricciones:
     • El número de elementos en ambos conjuntos no supera los 50.
     • Rango de elementos, es decir, A_i y B_i ≤ 10 ⁹

     Resolví esta pregunta segregando primero los diferentes elementos en un conjunto diferente.
     Supongamos que para el conjunto A, A’ contiene todos los elementos en A que satisfacen A’=A-{A intersección B}
     De manera similar, B’ para B.
     Ahora, para cada elemento en A’, verifiqué la cantidad de elementos (n) esos son sus factores en B, es decir, números que pueden contribuir a generar el número en A’ en el MCM(B) final.
     Si para cualquier número en A’ si n<2, entonces el número definitivamente no puede estar en el conjunto LCM(B) final y la función debería devolver falso. Se llevó a cabo una prueba similar para todos los elementos en B’. Si la función no devolvió falso durante estos dos bucles, entonces la respuesta debería ser verdadera. Aunque esta lógica no cubre todos los casos (como si dos conjuntos fueran {2, 5, 70} y {2, 5, 10}. La respuesta es verdadera pero la respuesta correcta es falsa), pasó porque los casos de prueba eran débiles . (Quiero decir, si una pregunta tan difícil está en la primera ronda, deben compensar en otro lugar).

  2. Dada una red de caminos que conectan ciudades y la capacidad de cada camino (igual para todos los caminos), así como su costo de reparación (único para cada camino), se nos da la cantidad de autobuses (n) que circulan entre un par de ciudades usando solo el camino más corto . (Capacidad de vía= No de buses permitidos en esa vía).
     Las carreteras inseguras son las carreteras donde no hay autobuses en la carretera > Capacidad de la carretera.

  Ahora dado n tenemos que minimizar el costo total de todos los caminos inseguros.
  Bastante difícil por lo que recuerdo, entendí que tenemos que calcular el número máximo de caminos más cortos disjuntos para minimizar la respuesta. (Mi solución solo pasó un caso de prueba).

• Ronda 1 (F-2-F)
  Me hicieron una variedad de preguntas que van desde strings hasta dp y gráficos.
  1. Dada una string corrupta, es decir, es la string original con solo los espacios en los lugares equivocados, construya la string original. Nos dan un diccionario de palabras.

        Ex:- 
         string: Com put erengineering
         original string: Computer Engineering 

     Le di al entrevistador una solución recursiva. Luego me pidieron que lo codificara. Después de eso, me preguntaron si podía optimizar más el código. No pude.

  2. Dado un carril donde hay varias casas, cada una de las cuales contiene una cantidad fija de oro. Ahora bien, un ladrón tiene que robar las casas de tal manera que cuando roba una casa no se puede robar la contigua. Calcular la cantidad máxima de oro recogido por él. (Pregunta clásica de Dp).
     Enlace del artículo: https://www.geeksforgeeks.org/find-maximum-possible-stolen-value-houses/
     Enlace de práctica: https://practice.geeksforgeeks.org/problems/max-sum-without-adjacents2430/1
  3. Dados 1000 elefantes, ninguno de los cuales se conocen las alturas exactas, se dan declaraciones que serán de dos formas

          I. E_i is taller than E_j
           OR
          II. E_i is smaller than E_j 

     Calcula el orden ascendente de los elefantes (en términos de altura).
     Me pareció difícil a primera vista, pero después de unos minutos, pude hacerlo.
     (Construya un DAG usando las declaraciones y luego ordénelas topológicamente para obtener la respuesta)

  4. Ordene topológicamente el DAG (excluyendo la disposición forestal) proporcionado si no se conoce la fuente.
     Por ejemplo: si los bordes son 1 → 2, 1 → 3, 2 → 4, 3 → 4.
     entonces normalmente ejecutaríamos DFS desde cada pt y luego elegiríamos el Node como fuente que visita todos los Nodes.
     Esto es justamente un algoritmo O(n ² ).
     Luego me preguntaron si hay un algoritmo O(n) disponible.
     Le dije al entrevistador que si ejecutamos dfs desde cada Node pero en lugar de vaciar la array visitada cada vez que solo mantenemos los datos, entonces el dfs del Node después de lo cual se marca toda la array visitada, es decir, todos los Nodes visitados es la fuente.
     cuando se ejecuta dfs desde un Node, si en algún punto se encuentra un Node visitado, dejamos el Node y pasamos al siguiente elemento secundario. Con solo mantener una pila también durante el dfs… después de marcar todos los valores en la array visitada, tendremos el orden clasificado topológico final del DAG en la pila.
  5. Dado un estanque donde todas las piedras están alineadas a una distancia de una unidad (C en cada fila y hay R tales filas), cada piedra tiene un valor especial que denota la longitud del salto que puede hacer la rana, es decir, si la rana está en piedra (x, y) y el valor es k, entonces la rana puede saltar a (x+dx, y+dy) donde dx + dy = k y la rana no sale de los límites. Encuentra el número mínimo de saltos para alcanzar la piedra en (R, C).
     Lo visualicé desde una array. Lo hice usando DP …….. En caso de que se lo pregunte, para una rana en cel (x, y) ejecute dos bucles de dx y dy donde net dx+dy=k y haga dp[ x+dx][y+dy]=min(dp[x][y]+1, dp[x+dx][y+dy]).
     La respuesta estaría en dp[R][C].
     Luego me pidieron que retrocediera por el camino, lo cual fue bastante fácil, ya que para dp[x][y] restarle 1 y buscar el valor resultante en las celdas (i, j) donde i ≤ x y j ≤ y. Repita este proceso hasta llegar a (0, 0).
     Esto concluyó mi primera ronda. También se hicieron una o dos preguntas más, pero no las recuerdo correctamente.
• RONDA 2(F-2-F)
  Técnico + RRHH
  1. Implemente la política de reemplazo de páginas LRU y LFU utilizando estructuras de datos.
     Enlace del artículo: https://www.geeksforgeeks.org/least-frequently-used-lfu-cache-implementation/ Ya me había encontrado con la pregunta mientras me preparaba para Amazon.
     Lo hice usando una cola doblemente terminada y un hashmap (mapa o BST no importa, ya que ambos tienen la misma complejidad para la recuperación e inserción de datos).
  2. Dado un dado normal y un dado en blanco. Rellene el dado en blanco de modo que la probabilidad de la suma del número de ambos dados sea la misma para todas las sumas resultantes y la suma tenga un rango de 1 a 12.
     Después de acertar y probar, me di cuenta de que el número en el dado en blanco sería repetirse para una distribución de probabilidad uniforme dada.
     Elemento mínimo requerido en el dado en blanco = 0
     Elemento máximo requerido en el dado en blanco = 6.
     marque 3 lados con 0 y tres con 6 .
     Debido al hecho de que la probabilidad de ocurrencia de 0 y 6 en el dado en blanco es la misma e igual a 0.5,
     P(Cada suma)=1/2*P(i)=1/12 para cada número.
     Ahora, tomar 1/12 al principio y luego derivar la solución debería haber sido fácil, pero debido al día agotador y al peor clima, mi mente tomó el método de la puerta trasera.
     Algunas preguntas relacionadas con recursos humanos para proyectos menores realizados en la universidad y preguntas relacionadas con mi experiencia con Flipkart como cliente.
• RONDA 3 (RONDA DE BONIFICACIÓN)
  Cuatro de nosotros que fuimos seleccionados después de la segunda ronda fuimos llamados para una ronda GD donde nos dijeron que deseaban llevarnos solo a dos de nosotros.
  Estábamos desconcertados por el reclamo.
  Nos dijeron que querían una discusión grupal sobre el tema ¿POR QUÉ FLIPKART DEBE CONTRATARTE?
  Continuamos durante 10 minutos tratando de untarlos con las ventajas de Flipkart y Dios sabe qué.
  Luego nos dieron nuestros resultados en una ficha.
  Después de abrir la ficha nos dimos cuenta de que solo era una broma.
  WTF !! Bienvenido a Flipkart

Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.