狗家谷阳挂经

楼主1月16日狗家onsite，new grad岗，前两天被通知hc没过……
话不多说，直接上题

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

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

分数设置不高，求小伙伴加米，给别人加米自己不会扣米，没米寸步难行啊……

第四题，build一个bst，然后看有多少是invalid node。

可以用类似于判断树是否为BST的思路：维护一个“值域”R=(lo, hi)（即在当前搜索下标范围[i, j]内，只有在R范围内的数才有可能被二分法找到）。求得当前搜索范围[i, j]的中点mid。如果A[mid]在当前的R中，那A[mid]就一定能被找到。然后分别递归mid的左右两侧[i, mid-1]和[mid+1, j]。递归左侧时，允许的值域是(lo, min(A[mid], hi))；同理右侧的值域是(max(A[mid], lo), hi)。如果任何时刻发现值域R已经不包含任何整数，那就表示[i, j]这个下标范围内没有任何能找到的数字。

cjhsu0319 发表于 2019/02/02 04:50:23
For question 4. 一个数如果在"正确"的位子上,那他就可以被binary search到,即使array不是有序.  For example, 2,1,3,6,7,5,9,5中,3就可以...

不知道你的“正确”是怎么定义的，但如果这指的是和有序（升序）排列的位置相同就为“正确”的话，你的做法是有问题的。
简单例子12543，4在正确的位置上，但因为第一次mid会选中5，右半部被舍弃了，4并不会被找到

LFU只用说思路嘛？

patpat 求问下lz是swe还是seti还是sre的hc呢？

BOMBANG 发表于 2019-2-2 02:57
patpat 求问下lz是swe还是seti还是sre的hc呢？

SWE，我去的时候已经没有hc了，所以拒的很快

wtcupup 发表于 2019-2-2 02:53
LFU只用说思路嘛？

代码。因为LRU写的有点快了……没演好……

最后一题完全摸不到头脑

For question 4. 一个数如果在"正确"的位子上,那他就可以被binary search到,即使array不是有序.  For example, 2,1,3,6,7,5,9,5中,3就可以被binary search到.  左右各做一次扫描,看有多少数在正确的位子上,剩下的数就是搜不到的数.

SWE没有hc了嘛？hr和楼主说的？

hr有说啥时候还有再有hc么

AngelSeven 发表于 2019-2-2 05:03
SWE没有hc了嘛？hr和楼主说的？

对，new grad的没有了，社招正常