狗家昂赛

运气不错五轮全是白人，可惜自己学艺不精，每一轮都挣扎无比。。。

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

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

可能是因为有工作经验的原因（4年），并没有问刁钻的算法，问了好多基本的非常考验coding和problem solving的问题，最近练习了好多花式hard题，结果最基本的知识点都没有熟练，面完出来满脑子都是“学艺不精”四个字~~啊~还有孙红雷拿着枪摇那个光头的脑袋：给你机会你不中用啊

求米求米，希望大家offer 多多

idatascience 发表于 2018-5-22 01:15
没太理解，那map的key如何设置可以实现O（1）的查询呢？求楼主大大解惑~

我回忆回忆，如果epsilon 是0.1，代表最小精度是0.1, 1/0.1 = 10, 10就是用来计算bucket的multipler

如果put(1.2, "hello") ，那就把 （1.2， "hello")这个pair放到 1.2 x 10 = 12 的bucket里面

如果要查找 get( 1.22) , 那么就去bucket 1.22 * 10 = 12的bucket 和他的两边邻居的bucket里面找（ 11， 13，这个case直接在12就找到了，那么返回hello）
如果查 get(1.12)， 那么就去 bucket 1.12 * 10 = 11的bucket 和他两遍邻居（10, 12）找

因为epsilon是0.1. 如果我们把每个bucket的范围限制在0.1 (方便计算，乘以multipler映射成整数），那么我们知道符合结果的key如果存在，那么一定在他整数映射的bucket或者他两遍的邻居里面。

补充内容 (2018-5-22 05:41):
输入法血崩，两边的邻居，意会下吧

ushergod 发表于 2018-5-20 03:50
请问楼主 第二题 get还需要保证O(1)吗 bucket的思路是啥 我想的是直接建一颗bst每个node 有range和value 搜 ...

我当时说BST logn找key，不过他说换了思路，比如eplison是 0.1那就以0.1为间隔建bucket, 就是你会有 0.1, 0.2, 0.3的bucket，这样你搜1.1的时候只需要找相邻的三个bucket, 1.0,1.1,1.2 。

补充内容 (2018-5-20 05:37):
bucket里放的original key, 如果那个key在查询的范围内，返回key对应的value

最后一轮每一层的通路只存在于两端的node？

devilnut 发表于 2018-5-19 15:20
最后一轮每一层的通路只存在于两端的node？

是的 1 层5个node, 2层 3个，就有 5x3 个edge

请问楼主 第二题 get还需要保证O(1)吗 bucket的思路是啥 我想的是直接建一颗bst每个node 有range和value 搜索时候 走一遍就可以

感谢LZ 分享，同问第二题 bucket 的思路

duangduangduang 发表于 2018-5-20 05:36
我当时说BST logn找key，不过他说换了思路，比如eplison是 0.1那就以0.1为间隔建bucket, 就是你会有 0.1, ...

感谢楼主分享思路 在这道题 eplison 是0.1 会有get(1.11)的case吗？

楼主能不能降点分TAT 跪谢啊

楼主四年经验面T3还是T4啊