注册一亩三分地论坛,查看更多干货!
您需要 登录 才可以下载或查看附件。没有帐号?注册账号
x
刚面完。
第一轮白人,给一个有向图,图里面有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算法。最后他说p您好! 本帖隐藏的内容需要积分高于 188 才可浏览 您当前积分为 0。 使用VIP即刻解锁阅读权限或查看其他获取积分的方式 游客,您好! 本帖隐藏的内容需要积分高于 188 才可浏览 您当前积分为 0。 VIP即刻解锁阅读权限 或 查看其他获取积分的方式 第一个执行。花了将近二十分钟的时间才把问题抽象成算法问题,然后暴力解,先sort,又跟他扯常见的sort算法及时间空间复杂度。然后两层for loop比较。最后分析时间复杂度O(n^2)空间复杂度O(1)。然后让我优化比较次数,时间就剩一点点了,没想出来,时间到了后他自己跟我说了下他的解法,我说原来就是用两个heap,他说是的。
整体来说我觉得我正常发挥了,最后一轮吃亏在英语不好,美国白人说话很快,我很难听懂他说什么。 攒点人品,希望能过!
|