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

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

  •  
  •   linjunxu · 82 天前 · 3257 次点击
    这是一个创建于 82 天前的主题,其中的信息可能已经有所发展或是发生改变。

    原题如下: 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
        1
    linjunxu   82 天前
    重新写下输入
    2
    4 3
    10 21 3 7
    1 13
    0 32
    2 22
    5 1
    14 1 15 20 26
    4 26
        2
    mara1   82 天前
    我真是膨胀了,居然试图翻译,第二段就歇菜了。
        3
    myliang   82 天前 via Android   ♥ 1
    懵逼。。。
        4
    koAlaPierce   82 天前
    大概思路是对一个数组做 Q 次操作,每次输出一个满足条件的最大子串的长度,子串满足异或和的二进制中 1 的个数为偶数。
        5
    markliu2013   82 天前   ♥ 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。
        6
    sigmapi   82 天前
    这不是上周 kick start 的第一题么
    就是一个数组 A,总共进行 Q 次操作,每次修改其中一个数数,然后选择两个下标 {l, r} ,计算 A[l] ^ A[l+1] ... ^ A[r] ,设结果为 x,则若 x 表示为二进制后 1 的数量为偶数,则 {l,r} 符合要求,可能有多组 {l, r} 满足要求, 输出 r-l 的最大值
        7
    dreamstart   82 天前 via Android
    线段树维护 1 的个数,然后查询就行了
        8
    lance6716   82 天前 via Android
    Kickstart 看官方题解啊
        9
    wfd0807   82 天前
    鲁班学院的讲师“子路”在谷歌工作过两年,看了这到面试题,结合他上课时表现出的英语水平,感觉被忽悠了
        10
    markliu2013   82 天前
    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,各种数据结构,优化优化。
        11
    kayv   82 天前
    @wfd0807 在顶级外企工作的人英语都不错,如果子路老师张口脆可能是假 Google 吧
        12
    zgl263885   82 天前 via iPhone
    我凑。。。
        13
    wang2332   81 天前 via Android
    楼上已经给出答案了 相当于线段树裸题了
        14
    markliu2013   81 天前
    不好意思,我上面的理解不对,题目说的是子数组,应该是连续的两个索引中间的。所以一个数组应该是 C(n, 2)个子数组。代码重新写了一下。这里传不了。
        15
    tyrantZhao   81 天前
    谷歌果然不是我等凡人能够挑战的。。。
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   2418 人在线   最高记录 5043   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 24ms · UTC 14:02 · PVG 22:02 · LAX 07:02 · JFK 10:02
    ♥ Do have faith in what you're doing.