Google Intern 面经，攒人品，不立flag，求过

发个面经祈福一波可好？ 请土地公公保佑我过~
前天面的

一面  白人小哥  很nice  题目是 2D mutable matrix sum  Leetcode 原题
然而并没有时间用segment tree 实现一遍~  只是最开始按照他的指引做了naive 的暴力加  然后升级了一下 用了  mutable matrix sum的方法写了 虽然也是对的 但是update 显然复杂度过大 虽然sum 是O(1)  不知道这种trade off 小哥满意不
写到这里感觉似乎已经跪了  虽然   在面试中也反复提及了segment tree实现，但是并没有形成一行代码   最后把segment tree的方法发给了面试官  希望能有所补救吧  但是感觉跪的可能性极大...

二面  打喷嚏 不问他不讲话的白人小哥   题目是 ,算了 没有截图，直接写例子吧

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

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

这个面试官占用了我20分钟自己跑case，以至于最后没有follow up  不过我自己也想不出这个题目怎么可以follow up  .. anyway  祈福吧 希望能过

也祝大家offer 多多  另外来点大米可好~









补充内容 (2017-1-10 00:28):
刚收到消息 加面

面完睡了一觉，加面题目  LC50        Pow(x, n)  希望能帮助到大家，祈求土地公公保佑过

一面应该 BIT最简单把
二面你看这个代码可以吗
List<Integer> re = new ArrayList<>();
        int maxReach = 0;
        int curReach = 0;
        int curMaxIndex = 0;
        for(int i = 0; i < arr.length - 1; i++){
            if(i + arr[i] > maxReach){
                maxReach = i + arr[i];
                curMaxIndex = i;
            }
            if(i == curReach){
                if(maxReach > curReach)
                    curReach = maxReach;
                else
                    return null;
                re.add(curMaxIndex);
            }
        }
        re.add(arr.length - 1);
        return re;

去吧叉子！ 发表于 2017-1-8 07:02
求问楼主， 第一题segment tree是面试官提出或者要求的写法吗？update和sum都是O（N）可以吗？

你的N是啥呢  segment tree 比较好吧 update 和 sum的复杂度都比较均匀，面试官没给任何提示，关于他想要的解法  相反他还会指引你从最naive的开始，一步一步前进，有没有时间升级到最好的解法就看你自己了=.= 反正我是没有来得及... seg 那个130行代码 抄都得抄10分钟...

格格笑 发表于 2017-1-8 07:45
你的N是啥呢  segment tree 比较好吧 update 和 sum的复杂度都比较均匀，面试官没给任何提示，关于他想要 ...

N是数组在1维上的长度。Array[N][N]
那楼主最后做出来的update的时间复杂度是多少呢？

bless lz！ 第二题不也是LC吗？jump game

houqingniao 发表于 2017-1-8 04:16
bless lz！ 第二题不也是LC吗？jump game

你说的对  那我岂不是面了两道hard题... 虽然都不难...  嗯 jump game  要写path的那种

求问楼主， 第一题segment tree是面试官提出或者要求的写法吗？update和sum都是O（N）可以吗？

garygao1993 发表于 2017-1-8 12:16
我二面也考了第一题，烙印问的，先写了O(1) query，再写了O(1) update，最后写了BIT

您好 O1 query比较简单 就直接straight forward
但是O1 update是什么方法呀？
BIT的update也不是O1啊