The Google online challenge 2020 for summer internships 2021 was held on August 16. It was a 60-minute online test having 2 questions to code.
First Question: Size of the smallest subset with maximum Bitwise OR
Second Question: Given a list which initially contains 0, the following queries can be performed:
- 0 X: add X to the list
- 1 X: replace each element “A” of the list by A^X, where ^ is the xor operator.
Return a list with the result elements in increasing order.
Example:
5 (no of queries) 0 4 0 2 1 4 0 5 1 8
Answer:
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
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
