V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
linjunxu
V2EX  ›  求职

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

  •  
  •   linjunxu · 2019-07-30 15:51:40 +08:00 · 5600 次点击
    这是一个创建于 1704 天前的主题,其中的信息可能已经有所发展或是发生改变。

    原题如下: 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
        1
    linjunxu  
    OP
       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
        2
    mara1  
       2019-07-30 16:05:47 +08:00
    我真是膨胀了,居然试图翻译,第二段就歇菜了。
    myliang
        3
    myliang  
       2019-07-30 16:54:03 +08:00 via Android   ❤️ 1
    懵逼。。。
    koAlaPierce
        4
    koAlaPierce  
       2019-07-30 17:17:07 +08:00
    大概思路是对一个数组做 Q 次操作,每次输出一个满足条件的最大子串的长度,子串满足异或和的二进制中 1 的个数为偶数。
    markliu2013
        5
    markliu2013  
       2019-07-30 17:35:00 +08:00   ❤️ 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。
    sigmapi
        6
    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
        7
    dreamstart  
       2019-07-30 17:45:19 +08:00 via Android
    线段树维护 1 的个数,然后查询就行了
    lance6716
        8
    lance6716  
       2019-07-30 19:03:03 +08:00 via Android
    Kickstart 看官方题解啊
    wfd0807
        9
    wfd0807  
       2019-07-30 19:06:10 +08:00
    鲁班学院的讲师“子路”在谷歌工作过两年,看了这到面试题,结合他上课时表现出的英语水平,感觉被忽悠了
    markliu2013
        10
    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>> 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,各种数据结构,优化优化。
    kayv
        11
    kayv  
       2019-07-30 20:45:43 +08:00
    @wfd0807 在顶级外企工作的人英语都不错,如果子路老师张口脆可能是假 Google 吧
    zgl263885
        12
    zgl263885  
       2019-07-30 21:11:43 +08:00 via iPhone
    我凑。。。
    wang2332
        13
    wang2332  
       2019-07-31 00:25:13 +08:00 via Android
    楼上已经给出答案了 相当于线段树裸题了
    markliu2013
        14
    markliu2013  
       2019-07-31 07:02:35 +08:00
    不好意思,我上面的理解不对,题目说的是子数组,应该是连续的两个索引中间的。所以一个数组应该是 C(n, 2)个子数组。代码重新写了一下。这里传不了。
    tyrantZhao
        15
    tyrantZhao  
       2019-07-31 17:00:34 +08:00
    谷歌果然不是我等凡人能够挑战的。。。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   2663 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 15:17 · PVG 23:17 · LAX 08:17 · JFK 11:17
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.