Google Intern 电面

11/09面的，还没feedback好心焦，因为手头暂时没其他interview了，recruiter姐姐说要一两个礼拜。一天要查好几次邮件，还有些distraction，发个面经求土地公公保佑！
两轮背靠背，感觉题目跟地里比起来简单的不像话，不知道是福是祸。

1. 听起来是国人姐姐，声音很温柔，一上来还很礼貌地为迟到两分钟解释了下
Problem：一个矩阵，支持两个操作，update一个格子，range query一个子矩阵
答：我经验比较少，直接写了二维树状数组，后来在网上查发现其他有人碰到过这个题，挂在面试官完全不知道树状数组这个结构，有些庆幸我的面试官姐姐很了解
然后让我过了个简单例子，分析了下复杂度O(logM * logN)
Follow up：

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

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

）
最后他范围follow up4问我sort方法，包括快排worst case，以及稳定的NlogN方法（我说heapsort），然后我嘴贱地说merge sort，他问我空间复杂度，我一想发现需要额外的NlogN space赶紧纠正。
然后最后弥补了迟到的五分钟让我问了问问题结束。

希望能尽早拿到好的feedback :)
也祝大家顺利 :)

第一题要用binary index tree？

最后一题是想让用xor吧？

jiongjiongyoush 发表于 2016-11-12 09:45
第一题要用binary index tree？

我想到的第一个解法就是BIT。。。。

wey066 发表于 2016-11-12 10:35
我想到的第一个解法就是BIT。。。。

BIT好难解释＝＝

iammajian 发表于 2016-11-12 10:17
最后一题是想让用xor吧？

精妙！不过xor没办法验证invalidation吧

jiongjiongyoush 发表于 2016-11-12 10:38
BIT好难解释＝＝

是的.....所以从这点看我运气不错 = =.....我跟他说BIT然后问他能不能get到我idea，他说可以，我就开开心心写代码了...

wey066 发表于 2016-11-12 10:48
是的.....所以从这点看我运气不错 = =.....我跟他说BIT然后问他能不能get到我idea，他说可以，我就开开心 ...

国人姐姐一定刷过lc 哈哈哈

第二题如果确保是vaild的字符串的话，直接把asscil码加起来就行了，两个相减就行了

我也感觉他是让你XOR