Experiencia de entrevista de Media.net 2021

Evaluación en línea:

1. Dado un árbol con raíz en 1 con n Nodes, se dan q consultas. En cada consulta, d, e se dan como entrada. Debe encontrar el valor máximo de e^x donde x es uno de los ancestros de d o d en el árbol.

   n<=10^5
   q<=3*10^5
   e<=3*10^5
   1<=d<=n

2. Un autobús se detiene en n paradas de autobús, cada parada de autobús tiene una [i] gente. El autobús necesita llevar a todas las personas en el autobús. Las personas de 1 parada de autobús se bajan antes de que llegue la siguiente parada de autobús. Utilizan una tecnología de cambio de tamaño que permite cambiar el tamaño del autobús a la capacidad que deseen. Esta acción se puede realizar solo b veces como máximo. La inutilidad del autobús es la suma de un número total de asientos desocupados en n paradas. Encuentre la inutilidad mínima que el autobús puede lograr si la tecnología de cambio de tamaño se usa de manera óptima. 1<=a[i]<=10^6, 1<=b<=n<=400

   Ex 1:
   a = [10 20] b = 0
   Ans:10

   Explicación: la tecnología de cambio de tamaño no se puede aplicar. por lo tanto, la capacidad del autobús es de 20 inicialmente. en la primera parada, 20-10 asientos estaban sin usar. en la segunda parada 20 – 20 asientos están sin usar. Total de asientos sin usar = 10

   Ex 2:
   a = [10 20 30] b = 1
   Ans: 10

   Explicación: la tecnología de cambio de tamaño solo se puede aplicar una vez. La capacidad del autobús es de 10 inicialmente. en la primera parada 10-10 asientos sin usar = 0. en la segunda parada, la tecnología se usa para cambiar el tamaño a 30. 30 – 20 asientos sin usar.

   En la tercera parada, 30-30 asientos sin usar

   Total de asientos sin usar = 10.

3. Se le darán n puntos en un plano 2D que representa la zona naranja corona. En el i-ésimo día, Corona se extenderá a todas las ubicaciones que se encuentran dentro de una distancia euclidiana i de cada zona naranja de Corona. Una zona se volverá roja si coincide con al menos ‘x’ zonas naranjas. Dados los n pares y x, encuentre el día en que ocurre la primera zona roja.

   1<=n<=100, 1<=b<=n, 
   for each point, 
   1<=x<=10^9, 1<=y<=10^9
   Example-
   (9,4),(10,3) , x=2.
   Ans : 1

   En el punto (9,3), ambas zonas se habrían visto afectadas después del día 1. Por lo tanto, se convertirá en una zona roja después del día 1.

Entrevista Ronda 1: Me pidieron que me presentara. Después de una breve introducción, me dieron directamente un problema. El problema es el siguiente:

1. Se le dan 4 strings w, x, y, z. Puedes permutar cada una de las strings como quieras. Debe corregir 1 permutación para cada una de las 4 strings de modo que cuando agregue las 4 strings en un trie, la cantidad de Nodes creados en el trie se minimice.

   Example-
   w = abaa
   x = aaaa
   y = acca
   z = abca
   For permutaion:
   w = abaa
   x = aaaa
   y = acca
   z = abca

   Número de Nodes en Trie: 1 (número de Nodes nuevos para el primer carácter de todas las strings) + 3 (para el segundo carácter) + 4 (para el tercer carácter) + 4 (para el cuarto carácter) = 12

   número mínimo de trie Nodes cuando:

   w = aaab
   x = aaaa
   y = aacc
   z = aacd
   Number of nodes : 
   1 + 1 + 2 + 4 = 8

   Le di una O(2^ (cantidad de palabras (4 en este caso)) * cantidad de caracteres (26 en este caso)) usando máscaras de bits. El entrevistador estaba convencido.

Entrevista Ronda 2: Hubo una pequeña introducción. Entonces el entrevistador saltó directamente al problema.

1. Se le proporciona una array 2D de números enteros con dimensión n X m y un valor ‘k’. Hallar si existe una subarray cuadrada cuya suma sea igual a k.

   Example-
   n = 3, m = 3, k = 10
   1 2 3
   2 3 4
   3 2 6
   Output: true

   Explicación: El cuadrado que comienza desde (1,0) hasta (2,1) (indexación basada en cero) tiene una suma 2 + 3 + 2 + 3 = 10 que es igual a k.

   Primero di la solución O(m*n*min(m,n)) usando DP y la optimicé O(m*n*log(min(n,m))) usando la búsqueda binaria. Pero la solución esperada era O(m*n) usando 2 punteros.