Google virtual onsite

来发一个3月初Google virtual onsite面经本人在西雅图地区，因为疫情的原因，原本约在3月5日的面试，4号的时候接到通知全部改成hangout 面试，我估计我算是第一波virtual onsite的人吧

您好！
本帖隐藏的内容需要积分高于 305 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 305 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

祝大家，健康平安，找工顺利！



补充内容 (2020-3-27 17:31):
第一题O(n) + O(n) 的思路我应该记得是有问题的，请大家忽略，不过应该是可以做到O(n)的。Sorry

lz 能降低一点积分要求吗？300分好高。。。

第一题：
https://www.geeksforgeeks.org/number-of-submatrices-with-all-1s/

gzs 发表于 2020-3-25 19:12
多谢楼主分享。很详细！
第二题我写了一下treemap解法，不知道和楼主是否一样，如果有问题请帮忙指出，多 ...

不大一样，我用的是TreeMap<int, int> key是num，value是count，出现的次数，防止有重复。我是treemap还要加上sliding window
TreeMap的话删除和添加都是logn所以总体是nlogn

第二题，直接用sliding window不行吗

llcourage123 发表于 2020-3-25 15:55
第二题，直接用sliding window不行吗

我说的那个two pointer就是sliding window, 但是只用sliding window复杂度太高，肯定不是面试官想要的

恭喜楼主加米了
第二题用deque的话好像只能求固定长度窗口大极值？那还是要二分答案，复杂度是一样的？
第四题“通过给定的string得到”，是用给定string里的字符，还是用整个string去拼dictionary word？
感谢！

Ljw921111g 发表于 2020-3-26 08:17
我说的那个two pointer就是sliding window, 但是只用sliding window复杂度太高，肯定不是面试官想要的

楼主我仔细想了下，单纯的sliding window的确解不了
有两种解法。
第一种是用两个heap，min heap 和max heap。这个是面试官要求的么？
第二种是二分。最短的答案可能是1，最长的答案可能是n，然后就进行二分，每次二分之后得到的值去check可不可行，可行的话l+1，不可行的话r-1，时间复杂度应该是o（nLogN）思路和切巧克力那道题类似。。
不知你觉得这两种方法可行么，另外你能详细说下oN解法么

多谢楼主分享。很详细！
第二题我写了一下treemap解法，不知道和楼主是否一样，如果有问题请帮忙指出，多谢。

    public int getLongestSubarray(int[] nums, int k) {
        TreeMap<Integer, Set<Integer>> valueMap = new TreeMap<>();
        for (int i = 0; i < nums.length; i++) {
            Set<Integer> indexes = valueMap.getOrDefault(nums[i], new HashSet<>());
            indexes.add(i);
            valueMap.put(nums[i], indexes);
        }
        int start = 0;
        int end = nums.length - 1;
        while (start < end) {
            if (valueMap.lastKey() - valueMap.firstKey() > k) {
                return end - start + 1;
            }
            if (nums[end] > nums[start]) {
                updateValueMap(nums, start, valueMap);
                start++;
            } else {
                updateValueMap(nums, end, valueMap);
                end--;
            }

        }
        return -1;
    }

    private void updateValueMap(int[] nums, int index, TreeMap<Integer, Set<Integer>> valueMap) {
        Set<Integer> indexes = valueMap.get(nums[index]);
        indexes.remove(index);
        if (indexes.isEmpty()) {
            valueMap.remove(nums[index]);
        } else {
            valueMap.put(nums[index], indexes);
        }
    }

另外烦请楼主分享下o（n）解法？ 以及heap这里确实有removeKey的瓶颈啊，感觉没办法做到nlogn？

请问第一道题, 最后用histogram 不是也需要O(N)的时间吗?
全部的点是O(N^2), 这样时间是否应该是O(N^3)

if (nums[end] > nums[start]) {
                updateValueMap(nums, start, valueMap);
                start++;
            } else {
                updateValueMap(nums, end, valueMap);
                end--;
            }

想问下为什么这样就一定能确定找到最长的subarray呢？

gzs 发表于 2020-3-26 11:12
多谢楼主分享。很详细！
第二题我写了一下treemap解法，不知道和楼主是否一样，如果有问题请帮忙指出，多 ...

用两个单调队列可以做到O(n)的

楼主牛逼，想明白了用双单调列对实现o(N)解法。。。，。