Google 实习面经

发个今天下午Google的实习电面。 感觉 Google 的面试 很看人品，身边有的人面的题很难， 有的面的很简单（比如我），然并卵。
第一轮 ： 一个 印度姐姐， 感觉人还不错。电话刚打来就说有的事要一会再打来。 接着再打来之后， 出了题， 然后又说有事，要挂断一会， 正好给我一段时间好好思考。

题目很简单， 两个List， 里面的element 可以是任意type。返回 两个list的差。

比如 A=【1,2,2,2】
       B= 【1,2,3,3,3】
       A-B= 【2,2】
       B-A =【3,3,3】
要求就是 求出 A-B 和 B-A。

一开始提了一个 nested for loop 暴力解 O(mn）。 她说可以。 接着我提了 一个 O（n），用Hashmap 储存的办法，一开始我还傻傻的说要用两个hashmap，然后她提醒我一个就够了。 然后我明白了就开始写代码了。 接着写完之后 她提出要我用 O（nlogn）的时间做但是不能用hashmap， 然后我就说吧暴力解里面的一个loop改成binary search就行了，她说可以。因为时间快到了就没让我写代码让我问问题。 感觉她就准备了一道题。


第二面面的不好。题目也很简单， 可惜我题刷的太少，不熟。面试官的英语讲的模糊不清的，很难交流。

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

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

我用recursion 去做， 经过他很多次提醒，代码也磕磕碰碰的写出来了不过感觉漏洞百出，然后最后时间到了 他问我 time complexity是多少 我好像没说对，想请教一下大佬 这里time complexity应该是多少呢？ 感觉应该挂了，不奢求有加面了(其实也是很累了不想面了）。接下来准备好好查缺补漏刷题，真正提升自己的能力才是关键。



补充内容 (2018-1-26 16:22):
面的不太好 不过还是拿到加面了。

第一题出的非常好。相当于实现数据库里的left anti semi join. join的方法有三种，nestloop join, hash join和sort merge join. 可能她想要的是sort merge join，两个数组都先排序，然后anti match.

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

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

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

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

yuanhsh 发表于 2018-1-20 11:42
第一题出的非常好。相当于实现数据库里的left anti semi join. join的方法有三种，nestloop join, hash joi ...

不对，好像还不太一样。抱歉。

请问楼主，第一题能解释一下A - B和B - A是怎么算出来的吗，谢谢
       A=【1,2,2,2】
       B= 【1,2,3,3,3】
       A-B= 【2,2】
       B-A =【3,3,3】.

第二题的decremntal word是什么意思呢，如果 Print->Pint ->Pit ->IT ->I 是的话，那任意一个单词都是啊，这里decremntal word是什么意思呢

rogerlin1234 发表于 2018-1-20 12:47
因为Print->Pint ->Pit ->IT ->I，每次都删一个character， 一直删到只剩single character为止， 每次删 ...

为什么感觉这题bfs可以做呢

oio14644 发表于 2018-1-20 16:36
为什么感觉这题bfs可以做呢

我好像用的是dfs。。

感谢题主，第二题BFS的话，初始长度为n，T(n) = nT(n - 1) =...=n!, 应该是factorial的复杂度吧