丢盒子onsite

sf3 发表于 2016-12-4 03:36
恭喜楼主！能不能透露一下包裹

实习嘛，没什么包裹....7500/月，有cooperate housing

用了树之后，allocate时间是O（n），内存是两倍这句话是不是说错了。。求问这个树该怎么构造还是没看懂，root left child是怎么会是bit而不是node。。

asdf61 发表于 2016-12-4 04:04
实习嘛，没什么包裹....7500/月，有cooperate housing

噢噢，估计住的挺奢华。。

duorme 发表于 2016-12-4 06:07
用了树之后，allocate时间是O（n），内存是两倍这句话是不是说错了。。求问这个树该怎么构造还是没看懂，ro ...

我表述的不大好，大意是图里这个样子。最底下一层bit array表示那个index所代表的id有没有被占用。然后每往上一层array也是用bit存，是指左边或右边的subarray里有没有available id。如果root是0，就说明整个array里都没有available ID；如果root是1，那就可以继续顺着他是1的child往下找.....这样allocate的时间就是.....O(logN)?对我好像确实说错了。找到以后在bottom up都update一遍，allocate的时间还是O(n)吧

这样假设最下面一层是N bit，每一层加起来可以用geometric series sum算出来（差不多）是2N，所以和之前只用一个bit array来存的方法相比内存是两倍（这个没说错）。

每个bit array之间是树的关系，但在date structure里不一定要有树的结构。因为可以算出每个bit在下一个array里refer to的index，所以我觉得可以直接access，不需要存pointer什么的（如果存了pointer内存就不止大两倍了）

补充内容 (2016-12-4 06:27):
allocate时间是O(logN)...又说错了...

sf3 发表于 2016-12-4 06:22
噢噢，估计住的挺奢华。。

2B2B四个人住...所以有室友... 不过在DT那么贵，这样已经挺难为人家公司的了

asdf61 发表于 2016-12-4 06:28
2B2B四个人住...所以有室友... 不过在DT那么贵，这样已经挺难为人家公司的了

是，贵的不敢想

asdf61 发表于 2016-12-4 06:28
2B2B四个人住...所以有室友... 不过在DT那么贵，这样已经挺难为人家公司的了

四个人住有室友？？啊那我得考虑下要不要房补。
我另一个实习室2b2b两个人住没有室友我以为dropbox只会更好就直接答应了。（哭

楼主，我下周去db onsite，还是不太明白allocate id这题，不知可否加微信向你请教一下？可以的话我微信Milolyf
谢谢了！

楼主你好！请问一下allocate ID那个题你提到space complexity 问的比较细，要计算多少个byte, 想问一下能麻烦稍微详细点解释一下吗？谢谢啦

tommyhahn 发表于 2017-2-23 04:28
楼主你好！请问一下allocate ID那个题你提到space complexity 问的比较细，要计算多少个byte, 想问一下能麻 ...

就是比如说你说要用array，每个element里存ID，那他会问你用什么variable存ID，这个variable多少byte，如果有100个ID的话这个array要用多少内存