Experiencia de entrevista de Google | Conjunto 2 (preguntas de ubicación)

Preguntas MCQ: 20 (+4, -1)
Pregunta subjetiva: 1

1) Dadas cuatro arrays
P = 20×10
Q = 10×5
R = 5×10
S = 10×10
Encuentra el número mínimo. de multiplicación requerida para PxQxRxS?
a) 4000
b) 2500
c) 3000
d) Ninguno de estos

2) Se dan dos arrays de tamaño n. n1 en orden decreciente y n2 en orden creciente. Si c1 es la complejidad de tiempo para n1 usando ordenación rápida y c2 es la complejidad de tiempo para n2 usando ordenación rápida. Entonces:
a) c1 > c2
b) c1 < c2 c) c1 = c2 d) Ninguno de estos
3) Si hay una array ordenada de N, ¿cuál es la complejidad temporal de encontrar 2 números que suman menos de 1000?
a) O(1)
b) O(n^2)
c) O(n)
d) O(registro)

4) Hay algún proceso. ¿En cuál de los algoritmos de programación la utilización de la CPU es mínima? Si el tiempo de ráfaga de E/S es de 90 ms y el tiempo de ráfaga de la CPU es de 10 ms (la pregunta es muy larga de recordar)

5)

int func(int x, int *y, int **z)
{
  int p, q;
  x += 2;
  p = *y++;
  q = **z++;
  q = **z++; //Not a repeated line.
}
void main()
{
  int a = 5, *b, **c;
  b = &a;
  c = &b;
  printf(“%d”,a);
}

6) Encuentra el dígito menos significativo de 2^3*google donde google=10^100.
a) 2
b) 4
c) 6
d) 8

7) Deje que w(n) y A(n) denoten respectivamente, el peor caso y el tiempo promedio de ejecución del caso de un algoritmo ejecutado en una entrada de tamaño n. ¿Cuál de las siguientes es SIEMPRE CIERTA?
a) A(n) = Omega(W(n))
b) A(n) = Theta(W(n))
c) A(n) = O(W(n))
d) A(n) = o (W(n))

8) Considere un gráfico no dirigido completo con el conjunto de vértices {0, 1, 2, 3, 4}. La entrada Wij en la array W a continuación es el peso de la arista {i, j}.

    0 1 8 1 4
    1 0 12 4 9
W = 8 12 0 7 3
    1 4 7 0 2
    4 9 3 2 0

¿Cuál es el peso mínimo posible de un árbol de expansión T en este gráfico tal que el vértice 0 sea un Node hoja en el árbol T?
a) 7
b) 8
c) 9
d) 10

9) En el gráfico dado en la pregunta 8, ¿cuál es el peso mínimo posible de un camino P desde el vértice 1 al vértice 2 en este gráfico tal que P contiene como máximo 3 aristas?
a) 7
b) 8
c) 9
d) 10

10) Una tabla hash de longitud 10 utiliza direccionamiento abierto con función hash h(k)=k mod 10 y sondeo lineal. Después de insertar 6 valores en una tabla hash vacía, la tabla es como se muestra a continuación.

|0|   | 
|1|   |
|2| 42|
|3| 23|
|4| 34|
|5| 52|
|6| 46|
|7| 33|
|8|   |
|9|   |

¿Cuál de las siguientes opciones da un orden posible en el que los valores clave podrían haberse insertado en la tabla?
a) 46, 42, 34, 52, 23, 33
b) 34, 42, 23, 52, 33, 46
c) 46, 34, 42, 23, 52, 33
d) 42, 46, 33, 23, 34 , 52

11) ¿Cuántas secuencias de inserción diferentes de los valores clave usando la misma función hash de la pregunta 10 y el sondeo lineal darán como resultado la tabla hash que se muestra arriba?
a) 10
b) 20
c) 30
d) 40

12) La relación de recurrencia que captura el tiempo óptimo del problema de la Torre de Hanoi con n discos es
a) T(n) = 2T(n – 2) + 2
b) T(n) = 2T(n – 1) + n
c ) T(n) = 2T(n/2) + 1
d) T(n) = 2T(n – 1) + 1

13) Dados tres semáforos, S0, S1 y S2 se inicializan como S0=1, S1=0, S2=0 y procesan P0, P1 y P2.

P0 : while(true)
P0, P1 and P2.
P0 : while(true)
{
  wait(S0);
  printf(“ 0 “);
  Release(S1);
  Release(S2);
}
P1: while(true)
{
  Wait(S1);
  Release(S2);
}
P2: while(true)
{
  Wait(S2);
  Release(S0);
} 

Averigüe cuántas veces el proceso P0 ejecuta la instrucción printf.
a) Al menos dos veces
b) Exactamente una vez
c) Exactamente dos veces
d) Exactamente tres veces

14) Dada la siguiente construcción de programa

{
 if ( a == b ) { S1; exit(); }
 else if ( c==d ) { S2; }
 else { S3; exit(); }
 S4;
} 

Dados 4 casos de prueba, averigüe cuál de los siguientes cubre las 4 afirmaciones
T1: a, b, c y d son iguales.
T2: a, b, c y d son todos distintos.
T3: a == b y c != d.
T4: a != byc==d.
a) T1, T2 y T3;
b) T1, T4.
c) T2, T4.
d) T1, T2 y T4.

15) ¿Cuáles de las siguientes afirmaciones son verdaderas?
I. La primera programación del tiempo restante más corto puede causar inanición
II. La programación preventiva puede causar inanición
III. Round robin es mejor que FCFS en términos de tiempo de respuesta
a) Solo I
b) Solo I y III
c) Solo II y III
d) I, II y III

16) Secuencias de acceso a páginas lógicas:
1 2 3 2 4 1 3 2 4 1
Técnicas de sustitución de página Óptima,LRU,FIFO implementadas.
Entonces no. de fallas de página en :
a) Óptimo < LRU < FIFO b) Óptimo < FIFO < LRU c) Óptimo = FIFO d) Ninguno
17) Encuentre el no. de fallas de página para la técnica de reemplazo de página óptima en la secuencia dada de la pregunta no. 16.
a) 5
b) 6
c) 7
d) 8

18) Dado un gráfico simple de 6 Nodes (nota: es un gráfico simple), indique cuál de los siguientes es un conjunto de grados de gráficos válidos.
a) 4,4,1,1,1,1
b) 4,4,2,1,1,1
c) 4,4,2,2,1,1
d) Ninguno

19)

gcd(n,m)
{
  if (n%m == 0)
    return n;
  n = n%m;
  return gcd ( m, n);
} 

¿Cuál es la complejidad de calcular mcd(n, m) en el peor de los casos?
a) O(lgn)
b) O(lgm)
c) O(lg(lgn))
d) O(lg(lgm))

20)

void f(char * x)
{
  x++;
  *x = 'a';
}
int main()
{
  char * str = "hello";
  f(str);
  cout << str;
  system("pause");
  return 0;
} 

a) hola
b) hola
c) allo
d) string vacía

SECCIÓN B – Pregunta subjetiva
El recorrido de un caballo es una secuencia de movimientos de un caballo en un tablero de ajedrez tal que el caballo visita cada casilla exactamente una vez. Encuentre todos los recorridos distintos de un caballo colocado en (x,y) de un tablero de ajedrez NxN.
X,Y Knight puede ir a 8 posiciones (regla predeterminada). Escribe un código de ejecución.

Estas preguntas son aportadas por Harshit Gupta . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo electrónico a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.