- #美国面经
- #码农类general
- #面试经验
- #snapchat
snapchat 3/29 onsite
sheepmiemies940557
昨天刚结束，很感谢地里大家分享的面筋，中了一些，不过无奈水平有限，多半已跪。给大家分享下新题。
onsite前：
沿海滩走10分钟到，一个叫GingerBread Court的小巷子。如果HR不说还真挺难找，不过进去了也不知道是哪一间因为没有标志，是一个小哥开门领进去check in的。之后在隔壁候着，陆续一共有五个人来，两个面QA的老外，我们有三个国人面SDE。11点的面试等到了11:15才开始，都等乏了。。。
第一轮：
面试官：亚裔妹子，人很nice很可爱，好像是broadcast组的，就是题一出我就有点懵了。
题目： ternary expression paser （三目运算符）， input是一个string，其中 'T' 表示true， 'F' 表示false， 要求返回最后运算的结果。
乍一看题目很直接， bool expression ? first result : second result
本帖隐藏的内容需要积分高于 188 才可浏览，点击前往一亩三分地论坛阅读。
i) 不能违背第二条规则。
（2）nextMove()。返回当前玩家的任意一个movement，要求对手无法获胜，如果找不到报错（我选择了返回-1）
脑子实在累了，讨论了一下给出了bruteforce的方案。
（1）valid主要难点在怎么判断已经有人赢了，LZ用check8个方向一共16个格子的方法，于是O(16*N^2)。跟小哥交涉，表示常数可以减小，不过16也合理可以写。
（2）假设当前为player A， 则枚举A的n个选择，每个选择会对应B的n个选择，复杂度依然是O(16*N^2)。但实际上如果不保存board state，不管是A还是B都得先找到每一列放置的位置，每次都扫描一遍就会多出O(N)的时间，总时间会变成O(N^3)，所以需要保存一下状态。
加上一些细节的调整，最后写完但依然没时间测试debug了，两人一起表示过了一遍应该work。。。。
总结：
刷面筋依然高效。遇到思路不清晰的问题，还是在纸上多举几个例子跟面试官讨论一下，思维清晰了反而能节省时间。继续保持coding，并且坚持运动增强体力。。。move on。。。。
补充内容 (2016-3-30 22:50):
抱歉第一题例子有个小typo。。。 T ? T : F ? T ? 1 : 2 : F ? 3 : 4; 会转化成T : 1 : 4，然后返回1
补充内容 (2016-3-30 22:51):
第三轮也有个小typo，XML和之前面筋一样都是三种类型 {open, close, text}
补充内容 (2016-3-31 02:34):
已跪，各位加油！
onsite前：
沿海滩走10分钟到，一个叫GingerBread Court的小巷子。如果HR不说还真挺难找，不过进去了也不知道是哪一间因为没有标志，是一个小哥开门领进去check in的。之后在隔壁候着，陆续一共有五个人来，两个面QA的老外，我们有三个国人面SDE。11点的面试等到了11:15才开始，都等乏了。。。
第一轮：
面试官：亚裔妹子，人很nice很可爱，好像是broadcast组的，就是题一出我就有点懵了。
题目： ternary expression paser （三目运算符）， input是一个string，其中 'T' 表示true， 'F' 表示false， 要求返回最后运算的结果。
乍一看题目很直接， bool expression ? first result : second result
本帖隐藏的内容需要积分高于 188 才可浏览，点击前往一亩三分地论坛阅读。
i) 不能违背第二条规则。
（2）nextMove()。返回当前玩家的任意一个movement，要求对手无法获胜，如果找不到报错（我选择了返回-1）
脑子实在累了，讨论了一下给出了bruteforce的方案。
（1）valid主要难点在怎么判断已经有人赢了，LZ用check8个方向一共16个格子的方法，于是O(16*N^2)。跟小哥交涉，表示常数可以减小，不过16也合理可以写。
（2）假设当前为player A， 则枚举A的n个选择，每个选择会对应B的n个选择，复杂度依然是O(16*N^2)。但实际上如果不保存board state，不管是A还是B都得先找到每一列放置的位置，每次都扫描一遍就会多出O(N)的时间，总时间会变成O(N^3)，所以需要保存一下状态。
加上一些细节的调整，最后写完但依然没时间测试debug了，两人一起表示过了一遍应该work。。。。
总结：
刷面筋依然高效。遇到思路不清晰的问题，还是在纸上多举几个例子跟面试官讨论一下，思维清晰了反而能节省时间。继续保持coding，并且坚持运动增强体力。。。move on。。。。
补充内容 (2016-3-30 22:50):
抱歉第一题例子有个小typo。。。 T ? T : F ? T ? 1 : 2 : F ? 3 : 4; 会转化成T : 1 : 4，然后返回1
补充内容 (2016-3-30 22:51):
第三轮也有个小typo，XML和之前面筋一样都是三种类型 {open, close, text}
补充内容 (2016-3-31 02:34):
已跪，各位加油！
