GoDaddy Online Inclusive Hackathon Assessment – DSA Question

The assessment consisted of 18 questions in total:

16 Multiple Choice Questions (MCQs).

2 Data Structures and Algorithms (DSA) questions.

DSA Questions

Question 1: Task Scheduling with Cooling Period

A medium-level problem based on completing tasks with a given cooling period between consecutive executions of the same task.

I was able to work on this problem.

Question 2: Count Subsets with a Given XOR for Multiple Queries

I couldn't solve this question during the assessment.

Problem Statement

You are given an array of integers arr of size n and q queries.

Each query consists of two integers:

• end: The ending index of the prefix to consider.
• k: The target XOR value.

For each query, count the number of subsets that can be formed using the elements from index 0 to end (inclusive) such that the bitwise XOR of all elements in the subset equals k.

Input

• An integer array arr of size n.
• An integer q, representing the number of queries.
• Each query contains two integers, end and k.

Output

For each query, output the number of subsets of the prefix arr[0...end] whose elements have a bitwise XOR equal to k.

Constraints

• 1 ≤ n ≤ 10⁵
• 1 ≤ q ≤ 10⁵

The constraints on the array elements and target XOR values were not specified.

Example

Input:

arr = [1, 2, 3]
q = 2
queries = [(1, 3), (2, 0)]

Output:

1
2

Explanation:

For arr = [1, 2, 3], consider the following queries.

Query 1: (1, 3)

The ending index is 1, so the prefix is [1, 2].

All possible subsets:

Subset	XOR	Matches target (3)?
{}	0	No
{1}	1	No
{2}	2	No
{1, 2}	1 ^ 2 = 3	Yes

Answer = 1

Query 2: (2, 0)

The ending index is 2, so the prefix is [1, 2, 3].

All possible subsets:

Subset	XOR	Matches target (0)?
{}	0	Yes
{1}	1	No
{2}	2	No
{3}	3	No
{1, 2}	3	No
{1, 3}	2	No
{2, 3}	1	No
{1, 2, 3}	1 ^ 2 ^ 3 = 0	Yes

Answer = 2

Therefore, the output is:

1
2

Note: This assumes the empty subset is allowed and each subset is counted once.