Position: SWE Intern
Place: India

Time: 60 minutes
Max. Score: 60 points (30 points / problem)

Problem 1: Existence of a Path

You are given a weighted undirected graph G that contains N nodes and M edges. Each edge has a weight associated to it.

You are required to answere Q queries of the following type:

• x y W : Find if there exists a path in G between nodes x and y such that the weight of each edge in the path is at most w. If such path exists , then print 1. Otherwise, print 0.

Input Format

• The first line contains an integer T denoting the number of test cases. For each test case :-
• The first line of each test case contains three space separated integers N, M, Q.
• Next M lines of each test case contains three space separated integers u, v, and w denoting an edge between node u and v with weight w.
• Next Q lines of each test case contains three space separated integers x, y, and W denoting the queries.

Output Format

For each test case, print Q lines denoting the answer to respective queries.

Constraints

1 ≤ T ≤ 5
1 ≤ N, Q, M ≤ 10⁵
1 ≤ w, W ≤ 10⁵
1 ≤ x, y ≤ N

Input: 
1
5 4 2 
1 2 10
2 3 5
3 4 9
4 5 13
1 5 13
2 5 12

Output:
1
0

Explanation:
For query 1:

Find a path between node 1 and 5 containing edges whose weight are at most 13 .
There exist a path 1 → 2 →  3 →  4 → 5. Hence, the answere is 1.

For query 2:

Find a path between node 2 and 5 containing edges whose weight are at most 12.
There does not exist any such path, Hence, the answer is 0.

Input: 
1
8 4 3
8 8 67
2 3 85
3 6 97
7 5 44
5 2 86
8 5 47
5 5 63

Output:
0
0
1

Input: 
1
5 1 4
3 5 51
4 5 71
2 3 91
4 4 61
3 1 8

Output:
0
0
1
0

Input: 
1
5 4 2
1 4 30
2 4 50
5 1 77
3 4 74
1 4 26
1 3 10

Output:
0
0

Problem 2: The maximum XOR value

You are given an array consisting of N integers. You are given q queries. Each query has two integers x and m. For each query, you are required to determine the array value that provides the maximum bitwise XOR value with x where the array value is not more than m.

In other words, for each query, you must find arr_i (1 ≤ i ≤ n, arr_i ≤ m) such that the value of (x ⊕ arr_i) is maximum where ⊕ denotes the bitwise XOR operator. If there is no such value that satisfies the condition, then print -1.

Input Format

• The first line contains an integer T denoting the number of test cases.
• The first line of each test case contains an integer N denoting the number of elements in the array.
• The second line of each test case contains N space-separated integers denoting arr₁, arr₂, arr₃ . . . , arr_N .
• The third line of each test case contains an integer q denoting the number of queries.
• Next q lines contain two integers x and m denoting the i^th query.

Output Format

For each test case, print q lines denoting the required answer.

Constraints

1 ≤ T ≤ 5
1 ≤ N, q ≤ 10⁵
0 ≤ arr_i, x, m ≤ 10⁹

Input: 
1
7
3 7 19 18 7 12 17
7
3 8
21 20
24 17
1 7
23 17
12 9
99 2

Output:
7
12
7
7
12
3
-1

Explanation:
In the first query x = 3 and m = 8. There are three values in the array that are not more than 8 (3, 7, 7). Therefore, XORs of these values are (3 ⊕ 3) 0 and (3 ⊕ 7) 4. The answer is 7.

In last query, all the values of the array are greater than 2. The answer is -1.

Inventory of Past Google Online Assessment Problem Statements