Google 电面 + Onsite面经

美国西北角的那个城市的office，非MTV。

电面，一个小时，阿三面试官，非常nice。
Word Square:
A B C D
B N R T
C R M Y
D T Y E

Word Square的定义是，任取0<=k<n(长/宽)，第k行和第k列的字符组成的字符串是一样的，比如第一行ABCD和第一列ABCD，是一样的。

除此之外，以下这种情况也是valid的。
A B C D
B N R T
C R M
D T

先写一下假设你要写一个函数判断给定的输入是不是WS你会怎么写test case
然后，给一个list of 字符串，给一个length，求长宽为length的所有valid的word square，以list of list of 字符串的形式返回。
我是用backtracking/DFS的方法做的。

最后分析一下复杂度。我的方法是n!，估计有更好的，但是后来结果还是pass了。


很快收到了onsite邀请。这个office部门以白人和国人为主，很少有三哥。

第一轮
LC的抢劫犯第一题和第二题。做完以后还有半小时。
接着是一个设计一个游戏算法，不需要写code。游戏是让用户猜单词。
一开始屏幕会显示一串下划线，代表这个词有多长，比如是 _ _ _ （假设答案是DAD的话）
玩家输入'E'，屏幕会显示 _ _ _
玩家输入'D', 屏幕会显示D _ D
玩家有一个尝试次数的上限。
现在要设计的算法是，这个词库，给定的是有限的（假设长度是一样的），计算机想要cheat，就是一开始这个词其实并没有确定，而是根据玩家输入的字符进行动态调整，目的是让玩家输，怎样去设计这个算法，同时保证不会让玩家发现程序在cheat（也就是每次程序返回的结果都是valid的）。这题面试官也只想让我聊一聊，基本的思路就是根据现有词库里的单词里的字符的组成，结合用户的输入，尽可能保住多的词库吧，用一点简单的概率，我没给出最后的完整算法，本来时间也不多了。

第二轮
LC 340
这题虽然是hard难度，其实思路很简单，代码量也不大。我是用类似multiset的思路，1 pass。不过面试官不熟悉C++，白板上code也不好看，花了挺多时间解释和走test case，面试官后来终于理解了。
Follow up:
如果这个string是一个输入流，string非常大，内存里放不下怎么办。我扯了一些，最后没给出一个让面试官满意的方法。不过面试官最后也说觉得已经很不错了。

第三轮：
LC 391
我今天写面经的时候刚刚出现的题，目前2290提交160个AC的hard题。当时真的把我难住了。面试官说他是第二次问这个问题。
我给的方法是，首先找所有矩阵的最左上角，最右上角，最右下角和最左下角的点，求这个面积，然后sum up所有小矩阵面积，两者必须相等。这一步很简单。
在满足以上条件下，先按照每个矩阵的垂直边X轴坐标排序，track当前矩阵的左边和右边沿，每个矩阵往上加的时候必须刚好贴在左边沿或者右边沿。这样做两次，一次正序，一次逆序。
同理，对水平边Y轴也做一次。
面试官心中的解法不是如此，但是也举不出一个bad example。我自己也无法证明自己。这一轮估计没让我过。

第四轮：

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

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

第五轮：
LC 108。2分钟秒过了。面试官半开玩笑地说，你不应该做这么快。
然后是一道迷宫题。
假设你在一个迷宫里，你不知道迷宫大小，不知道自己方向。你只有以下3个API函数可以调用：
1. 检查是不是已经到了出口
2. 往前move一格（返回true表示成功move，返回false表示失败，不能移动，即撞墙）
3. 原地向左转90度。
要求写个函数把这个迷宫走出去。假设迷宫本身没有loop。
正常情况来说楼主应该是可以顺利做出来的，无非就是DFS，唯一要小心的就是不要走圈子，或者说走回头路。但是那天生病了，特别不舒服，最后一轮了体力不行了。面试官说我very close，但真的没精力去检查最后那个小BUG了。

吐槽一下
G提供的酒店非常糟糕，楼下是工地，很吵，房间能听到隔壁打电话看电视。面试当天楼主生病了，长途跋涉又有时差，身体极其不舒服，几乎站不住，真的也是运气不好。

您好！
本帖隐藏的内容需要积分高于 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

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

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

楼主看起来其实你面的不错，不一定要所有题都做的全队的
祝好运

edyyy 发表于 2016-8-29 01:30
楼主看起来其实你面的不错，不一定要所有题都做的全队的
祝好运

感谢安慰，已跪

楼主 想请问一下是哪家酒店呀

我在想，他们挂你的原因是不是因为你题目秒的太快了啊。

第三轮： 能不能这样

先求各自面积， sum ，  必须等于最左下到最右上 的面积， 这是第一个条件。 （如果找不到最左下，最右上， 则必然不是矩阵）

然后 sweep line x 轴 查有没有交集就行了吧 ？

pushazhiniao 发表于 2016-8-29 04:25
楼主 想请问一下是哪家酒店呀

The HXXXXXXX HOTEL

lvvvvv 发表于 2016-8-29 07:12
第三轮： 能不能这样

先求各自面积， sum ，  必须等于最左下到最右上 的面积， 这是第一个条件。 （如 ...

因为在LC上已经出现这道题，你大可以试一下~我过阵子去做这题。

google真的好难哦，请问lz第一轮follow up 怎么整啊？

楼主确实运气不好, 第三题先求面积是否相等, 然后再查是否有重叠, 目前查重叠我是O(n^2), 大数据过不掉, 如果要求O(n)完成确实不容易