Google Online Challenge 2020
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:
#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 << " ";
}
}
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int t = scanner.nextInt();
while (t-- > 0) {
int q = scanner.nextInt();
PriorityQueue<Pair> pq = new PriorityQueue<>(Comparator.reverseOrder());
ArrayList<Integer> v = new ArrayList<>();
pq.add(new Pair(0, 0));
v.add(0);
while (q-- > 0) {
int a = scanner.nextInt();
int x = scanner.nextInt();
if (a == 0)
v.add(x);
else {
pq.add(new Pair(v.size(), x));
}
}
int x = 0;
Pair y = new Pair(0, 0);
while (!pq.peek().equals(y)) {
Pair top = pq.poll();
x ^= top.second;
while (pq.peek() != null && pq.peek().first == top.first) {
x ^= pq.poll().second;
}
for (int i = top.first - 1; i >= (pq.peek() != null ? pq.peek().first : 0); i--) {
v.set(i, v.get(i) ^ x);
}
}
Collections.sort(v);
for (int a : v)
System.out.print(a + " ");
System.out.println();
}
}
static class Pair implements Comparable<Pair> {
int first;
int second;
Pair(int first, int second) {
this.first = first;
this.second = second;
}
@Override
public int compareTo(Pair o) {
if (this.first == o.first)
return Integer.compare(this.second, o.second);
return Integer.compare(this.first, o.first);
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Pair pair = (Pair) o;
return first == pair.first && second == pair.second;
}
@Override
public int hashCode() {
return Objects.hash(first, second);
}
}
}
import heapq
def main():
t = int(input("Enter the number of test cases: "))
# Loop through each test case
for _ in range(t):
q = int(input())
# Initialize a priority queue and a list
pq = [(0, 0)]
v = [0]
# Process each query
for _ in range(q):
a, x = map(int, input().split())
if a == 0:
v.append(x)
else:
heapq.heappush(pq, (len(v), x))
x = 0
y = (0, 0)
# Process the priority queue
while pq[0] != y:
top = heapq.heappop(pq)
x ^= top[1]
# Pop elements with the same priority
while pq[0][0] == top[0]:
x ^= heapq.heappop(pq)[1]
# Update the list
for i in range(top[0] - 1, pq[0][0] - 1, -1):
v[i] ^= x
# Sort and print the final list
v.sort()
for a in v:
print(a, end=" ")
print()
if __name__ == "__main__":
main()
// Importing necessary package
const readline = require('readline');
// Defining input interface
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
// Function to handle input and perform operations
function main() {
rl.question("Enter the number of test cases: ", (t) => {
t = parseInt(t);
while (t-- > 0) {
rl.question("Enter the value of q: ", (q) => {
q = parseInt(q);
let pq = new PriorityQueue((a, b) => b[0] - a[0]); // Max Heap
let v = [0]; // Initialize array v with 0
pq.push([0, 0]); // Push [0, 0] into priority queue
let result = []; // Initialize result array
// Processing queries
(function processQueries() {
if (q-- > 0) {
rl.question("Enter a and x separated by space: ", (input) => {
let [a, x] = input.split(" ").map(Number);
if (a === 0) {
v.push(x);
} else {
pq.push([v.length, x]);
}
processQueries(); // Recursive call to process next query
});
} else {
let x = 0;
let y = [0, 0];
// Process elements in priority queue
while (!pq.isEmpty() && !pq.peek().equals(y)) {
let top = pq.pop();
x ^= top[1];
// Process elements with same level in priority queue
while (!pq.isEmpty() && pq.peek()[0] === top[0]) {
x ^= pq.pop()[1];
}
// Update array v
for (let i = top[0] - 1; i >= (pq.isEmpty() ? 0 : pq.peek()[0]); i--) {
v[i] ^= x;
}
}
v.sort((a, b) => a - b); // Sort array v
result.push(v.join(" ")); // Push sorted array v into result array
// Output the result
console.log("Result for current test case:");
console.log(result.join("\n"));
// Recursive call to handle next test case
main();
}
})();
});
}
});
}
// Define PriorityQueue class
class PriorityQueue {
constructor(comparator = (a, b) => a - b) {
this._heap = [];
this._comparator = comparator;
}
// Method to push element into priority queue
push(value) {
this._heap.push(value);
this._siftUp();
}
// Method to pop element from priority queue
pop() {
const poppedValue = this._heap[0];
const bottom = this._heap.length - 1;
if (bottom > 0) {
this._swap(0, bottom);
}
this._heap.pop();
this._siftDown();
return poppedValue;
}
// Method to check if priority queue is empty
isEmpty() {
return this._heap.length === 0;
}
// Method to get the element at the top of priority queue
peek() {
return this._heap[0];
}
// Method to get the size of priority queue
size() {
return this._heap.length;
}
// Method to perform upward shift operation
_siftUp() {
let node = this._heap.length - 1;
while (node > 0) {
const parent = Math.
8 12 13 14
Contact Us