Google 笔试题，看了半天没看懂，大神能解释一下吗

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

已注册用户请登录

这是一个创建于 2265 天前的主题，其中的信息可能已经有所发展或是发生改变。

原题如下： Problem Steven has an array of N non-negative integers. The i-th integer (indexed starting from 0) in the array is Ai.

Steven really likes subintervals of A that are xor-even. Formally, a subinterval of A is a pair of indices (L, R), denoting the elements AL, AL+1, ..., AR-1, AR. The xor-sum of this subinterval is AL xor AL+1 xor ... xor AR-1 xor AR, where xor is the bitwise exclusive or.

A subinterval is xor-even if its xor-sum has an even number of set bits in its binary representation.

Steven would like to make Q modifications to the array. The i-th modification changes the Pi-th (indexed from 0) element to Vi. Steven would like to know, what is the size of the xor-even subinterval of A with the most elements after each modification?

Input The first line of the input gives the number of test cases, T. T test cases follow.

Each test case starts with a line containing two integers N and Q, denoting the number of elements in Steven's array and the number of modifications, respectively.

The second line contains N integers. The i-th of them gives Ai indicating the i-th integer in Steven's array.

Then, Q lines follow, describing the modifications. The i-th line contains Pi and Vi, The i-th modification changes the Pi-th element to Vi. indicating that the i-th modification changes the Pi-th (indexed from 0) element to Vi.

Output For each test case, output one line containing Case #x: y_1 y_2 ... y_Q, where x is the test case number (starting from 1) and y_i is the number of elements in the largest xor-even subinterval of A after the i-th modification. If there are no xor-even subintervals, then output 0.

Limits Time limit: 40 seconds per test set. Memory limit: 1GB. 1 ≤ T ≤ 100. 0 ≤ Ai < 1024. 0 ≤ Pi < N. 0 ≤ Vi < 1024.

Test set 1 (Visible) 1 ≤ N ≤ 100. 1 ≤ Q ≤ 100.

Test set 2 (Hidden) 1 ≤ N ≤ 105. 1 ≤ Q ≤ 105.

Sample

Input

Output

2 4 3 10 21 3 7 1 13 0 32 2 22 5 1 14 1 15 20 26 4 26

Case #1: 4 3 4 Case #2: 4

In Sample Case 1, N = 4 and Q = 3. After the 1st modification, A is [10, 13, 3, 7]. The subinterval (0, 3) has xor-sum 10 xor 13 xor 3 xor 7 = 3. In binary, the xor-sum is 112, which has an even number of 1 bits, so the subinterval is xor-even. This is the largest subinterval possible, so the answer is 4. After the 2nd modification, A is [32, 13, 3, 7]. The largest xor-even subinterval is (0, 2), which has xor-sum 32 xor 13 xor 3 = 46. In binary, this is 1011102. After the 3rd modification, A is [32, 13, 22, 7]. The largest xor-even subinterval is (0, 3) again, which has xor-sum 32 xor 13 xor 22 xor 7 = 60. In binary, this is 1111002. In Sample Case 2, N = 5 and Q = 1. After the 1st modification, A is [14, 1, 15, 20, 26]. The largest xor-even subinterval is (1, 4), which has xor sum 1 xor 15 xor 20 xor 26 = 0. In binary, this is 02.

15 条回复 2019-07-31 17:00:34 +08:00

linjunxu

2019-07-30 15:52:41 +08:00

重新写下输入
2
4 3
10 21 3 7
1 13
0 32
2 22
5 1
14 1 15 20 26
4 26

mara1

2019-07-30 16:05:47 +08:00

我真是膨胀了，居然试图翻译，第二段就歇菜了。

myliang

2019-07-30 16:54:03 +08:00 via Android

懵逼。。。

koAlaPierce

2019-07-30 17:17:07 +08:00

大概思路是对一个数组做 Q 次操作，每次输出一个满足条件的最大子串的长度，子串满足异或和的二进制中 1 的个数为偶数。

markliu2013

2019-07-30 17:35:00 +08:00

给你一个数组 A，和一个数组 Q，数组 Q 中有两个数字 P，V。
现在根据数组 Q 对数组 A 就行修改操作。数组 Q 中的 P 代表 A 的索引，V 代表修改后的值。
针对每次修改后的 A，你都要求一个 largest xor-even subinterval。

什么是 largest xor-even subinterval 呢？
数组 A 的 xor-sum 是对数组的每一个元素就行抑或操作累积。
The xor-sum of this subinterval is AL xor AL+1 xor ... xor AR-1 xor AR
xor-sum 之后会得到一个数字，这个数字的二进制中 1 的个数如果是偶数，那就符合 xor-even 了。
N 个数的数组有 2 的 N 次方个子数组，如果子数组符合 xor-even，那就是 subinterval，现在你要找的就是数组长度最大的
subinterval。

sigmapi

2019-07-30 17:38:36 +08:00

这不是上周 kick start 的第一题么
就是一个数组 A，总共进行 Q 次操作，每次修改其中一个数数，然后选择两个下标 {l, r} ，计算 A[l] ^ A[l+1] ... ^ A[r] ，设结果为 x，则若 x 表示为二进制后 1 的数量为偶数，则 {l,r} 符合要求，可能有多组 {l, r} 满足要求, 输出 r-l 的最大值

dreamstart

2019-07-30 17:45:19 +08:00 via Android

线段树维护 1 的个数，然后查询就行了

lance6716

2019-07-30 19:03:03 +08:00 via Android

Kickstart 看官方题解啊

wfd0807

2019-07-30 19:06:10 +08:00

鲁班学院的讲师“子路”在谷歌工作过两年，看了这到面试题，结合他上课时表现出的英语水平，感觉被忽悠了

markliu2013

2019-07-30 19:09:26 +08:00

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

// https://codingcompetitions.withgoogle.com/kickstart/round/0000000000051061/0000000000161426
public class Solution {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
try {
int T = sc.nextInt();
for (int i = 0; i < T; i++) {
int N = sc.nextInt();
int Q = sc.nextInt();
int[] A = new int[N];
for (int j = 0; j < N; j++) {
A[j] = sc.nextInt();
}
System.out.print("Case #"+(i+1)+": ");
for (int j = 0; j < Q; j++) {
int index = sc.nextInt();
int value = sc.nextInt();
A[index] = value;
System.out.print(largestXOREvenSubinterval(A) + " ");
}
System.out.print("\n");
}
} finally {
sc.close();
}
}

public static int largestXOREvenSubinterval(int[] A) {
List<List<Integer>> subrraySet = CollectionUtil.subsets(ArrayUtil.toList(A));
int result = 0;
for (List<Integer> subArray : subArraySet) {
if (subArray.size() > 0) {
int xorSum = getXORSum(subArray);
if (Integer.bitCount(xorSum) % 2 == 0) {
result = Math.max(result, subArray.size());
}
}
}
return result;
}

public static int getXORSum(List<Integer> A) {
if (A.size() == 0) {
return 0;
}
int xorSum = A.get(0);
for (int i = 1; i < A.size(); i++) {
xorSum ^= A.get(i);
}
return xorSum;
}

}

class ArrayUtil {
public static List<Integer> toList(int[] array) {
List<Integer> result = new ArrayList<>();
for (int i = 0; i < array.length; i++) {
result.add(Integer.valueOf(array[i]));
}
return result;
}
}

class CollectionUtil {
public static <T> List<List<T>> subsets(List<T> list) {
List<List<T>> solutiOnList= new ArrayList<>();
solutionList.add(new ArrayList<>());
for (int i = 1; i <= list.size(); i++) {
solutionList.addAll(combine(list, i));
}
return solutionList;
}
public static <T> List<List<T>> combine(List<T> list, int k) {
List<List<T>> solutiOnList= new ArrayList<>();
if (k == 0) {
solutionList.add(new ArrayList<>());
return solutionList;
}
if (k == list.size()) {
solutionList.add(new ArrayList<>(list));
return solutionList;
}
T lastItem = list.get(list.size()-1);
List<T> subList = list.subList(0, list.size()-1);
List<List<T>> list1 = combine(subList, k);
solutionList.addAll(list1);
List<List<T>> list2 = combine(subList, k-1);
for (int i = 0; i < list2.size(); i++) {
list2.get(i).add(lastItem);
}
solutionList.addAll(list2);
return solutionList;
}
}

刚刚写了一个非常非常暴力的解法，结果是内存超时了，但是可以确定我题目是理解对了。等我想想动态规划，prefix sum，各种数据结构，优化优化。