El desafío en línea de Google 2020 para pasantías de verano 2021 se llevó a cabo el 16 de agosto. Fue una prueba en línea de 60 minutos con 2 preguntas para codificar.
Primera pregunta: Tamaño del subconjunto más pequeño con máximo Bitwise OR
Segunda Pregunta: Dada una lista que inicialmente contiene 0, se pueden realizar las siguientes consultas:
- 0 X: añadir X a la lista
- 1 X: reemplaza cada elemento “A” de la lista por A^X, donde ^ es el operador xor.
Devuelve una lista con los elementos del resultado en orden creciente.
Ejemplo:
5 (no of queries) 0 4 0 2 1 4 0 5 1 8
Responder:
C++
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
while (t--) {
int q;
cin >> q;
priority_queue<pair<int, int> > pq;
vector<int> v;
pq.push({
0,
0,
});
v.push_back(0);
while (q--) {
int a, x;
cin >> a >> x;
if (a == 0)
v.push_back(x);
else {
pq.push({ v.size(), x });
}
}
int x = 0;
auto y = make_pair(0, 0);
while (pq.top() != y) {
auto top = pq.top();
x ^= top.second;
pq.pop();
while (pq.top().first == top.first) {
x ^= pq.top().second;
pq.pop();
}
for (int i = top.first - 1; i >= pq.top().first;
i--) {
v[i] ^= x;
}
}
sort(v.begin(), v.end());
for (auto a : v)
cout << a << " ";
}
}
8 12 13 14
Publicación traducida automáticamente
Artículo escrito por walkinspacewithme y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA