狗家新鲜店面intern，求过

刚刚面完两轮店面，感觉有点虚，求过， 求大米

一面：（貌似是中国小姐姐）
Find the k closest number for a target value in a BST. 一直要求降低时间空间复杂度，她想要O(n)时间，O(k)

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

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

rong>补充内容 (2018-10-19 01:03):
最后5分钟还问了一个小题，hashmap的底层数据结构是什么，答出来array，hashcode，bucket了，但是他又问hashcode的形式是什么，就跪了

yfamy123 发表于 2018-10-17 03:08
heap么？我说了一下，他说heap删除的话，时间复杂度就高了

就是普通的queue 维持size k 一直push 新的， pop 最早的。
因为是push进去递增的数， 在 abs(x - target) >= abs(q.front() - target) 的时候return 就好了

LC 272

bearxiong2017 发表于 2018-10-18 02:29
可以请教下楼主二面的两个follow up的思路吗？
第二个follow up我的想法是把要验证的guess代入到前面的gue ...

第二个就是用第一题的函数，compare每个history guess和new guess，如果所有的结果和history guess 和secret compare的结果一致，那就是possible的。
第三个不太清楚，我就说了下用dfs，具体我也不知道，他也没说什么

exdee 发表于 2018-10-17 03:15
就是普通的queue 维持size k 一直push 新的， pop 最早的。
因为是push进去递增的数， 在 abs(x - targe ...

这个逻辑有漏洞：
例子: 输入[3,4,5], target : 3.7, k : 2
照这个逻辑会返回[4,5]， 正确答案应该是[3,4]

而且Inorder traverse本身stack不就用掉了树高的空间复杂度吗，何来只用Ok空间？

good luck!

恭喜恭喜！ good luck！

inorder traversal 然后维持一个size 是 k 的queue

来自一亩三分地官方APP

exdee 发表于 2018-10-17 03:04
inorder traversal 然后维持一个size 是 k 的queue

来自一亩三分地官方APP

heap么？我说了一下，他说heap删除的话，时间复杂度就高了

楼主加油!!

楼主oa后多久收到电面通知的？


来自一亩三分地官方APP

这个两轮店面是分着打的？原先就约好两轮的？

祝lz好运！另外请问一下lz，如果heap需要maintain length k的话每次操作需要klogk，如果这个时间复杂度超过了要求，那是否最后返回的list不需要按照difference（target-v）的大小排列？

补充内容 (2018-10-17 07:49):
对不起不是每次操作需要klogk……是一次操作需要logk……用heap的话时间复杂度就是nlogk了。