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

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

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

懵逼。。。

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

给你一个数组 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。

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

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

Kickstart 看官方题解啊

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

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>> subArraySet = 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，各种数据结构，优化优化。

@wfd0807 在顶级外企工作的人英语都不错，如果子路老师张口脆可能是假 Google 吧

我凑。。。

楼上已经给出答案了 相当于线段树裸题了

不好意思，我上面的理解不对，题目说的是子数组，应该是连续的两个索引中间的。所以一个数组应该是 C(n, 2)个子数组。代码重新写了一下。这里传不了。

谷歌果然不是我等凡人能够挑战的。。。