热乎乎的骨骼 onsite 面经

刚面完。
第一轮白人，给一个有向图，图里面有label和state。state的取值范围有多种，其中有一种是end。 给你任意个图的node，问能否gurantee 走到end，即他所有的neibors都必须能走到end，只要有一个return false。  我carify 有没有可能出现环，他说好问题，然后让我直接返回false。 我用dfs + hashSet直接秒了，然后他让我跑两个test case。最后他说应该能work，然后剩几分钟聊天了。
第二轮老中，Majority number，第一问找1/2，我从sort讲起，讲常见的sort方法以及他们的时间空间复杂度，然后讲hash Map, bit 操作。然后假装不知道vote算法， 他让我进一步优化，我说我试试水涨船高。然后demo了下，写了下算法，最后问1/3的情况。每一种算法再分析下，让我继续用vote算法。最后他说pretty good。
第三轮：比较版本的新旧。给两个String,比如“1.1.1”“3.1.1”，“3.1.1”是新版本。我跟他clarify时，说了下null 和size==0的情况，他问我这两种情况有什么不同，我给他分析了stack heap结构。然后问我应该各自返回什么，我说为null时一般视为异常，然后写了try catch结构抛出异常。但是其中一个String size == 0时返回另一个String即可。他说很好。然后写代码。挨个比较，最后他问我“1.1”和“1.1.0”和“1.1.0000”该怎么办，我说那我们需要pre process或者Pro precess，让我分析哪种好，我说时间复杂度和空间复杂度都一样，所以两种方法没区别，他说对。然后我写了preprocess，把最后的0全都删除掉。
第四轮：一办BQ，问我最近的项目，最难的地方在哪里，我答最难的地方也是我最骄傲的地方是当我们的用户增加时，我的架构需要做相应的优化。然后见我使用了cache，问使用cache常见的风险是什么，我说风险是cache的数据会掉电消失，我们使用log的方式从掉电中恢复cache数据。然后剩一半时间问我假如一辆车只有一排位置，每次乘客上车后都

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

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

第一个执行。花了将近二十分钟的时间才把问题抽象成算法问题，然后暴力解，先sort，又跟他扯常见的sort算法及时间空间复杂度。然后两层for loop比较。最后分析时间复杂度O(n^2)空间复杂度O(1)。然后让我优化比较次数，时间就剩一点点了，没想出来，时间到了后他自己跟我说了下他的解法，我说原来就是用两个heap，他说是的。   


整体来说我觉得我正常发挥了，最后一轮吃亏在英语不好，美国白人说话很快，我很难听懂他说什么。 攒点人品，希望能过！

看上去应该是稳了，楼主，要是过了，要不要一起去google 租房呢？私信留个联系方式呗

第五轮可以麻烦楼主再详细说说嘛？
不同的任务之间是否有关系？
最多有多少任务可以同时运行？
可以第一个执行的条件是什么？
谢谢楼主！

dynastyW2 发表于 2018-1-18 10:48
请问写code是白班用笔写，还是键盘打？

真白板，整面墙都是你的。。。

祝好运！！！！！

楼主能讲一下第5轮的具体要求和解法吗~~~

都做出来了，应该稳了。

我也昨天面完狗家，过程差不多，祝你好运吧

请问写code是白班用笔写，还是键盘打？

求问第一轮就算每个点都能走到end，但只要有环，还是return false么？

应届生一般不是4轮吗