丢盒子onsite

asdf61 发表于 2017-2-24 09:08
就是比如说你说要用array，每个element里存ID，那他会问你用什么variable存ID，这个variable多少byte，如 ...

谢谢！我想再问一下那个duplicate file 的题代码需要写到什么程度啊？是不是就把dfs写出了就好，用写md5的hash 的代码吗？

tommyhahn 发表于 2017-2-28 08:07
谢谢！我想再问一下那个duplicate file 的题代码需要写到什么程度啊？是不是就把dfs写出了就好，用写md5 ...

Hi! 不用不用..能说出来md5 hash就行，他给了好多可以用来access file system的API，所以只要把算法写出来就好了

樓主 關於segment tree那部分 是code也要寫出來嗎 還是描述思想就可以？

asdf61 发表于 2016-12-4 06:26
我表述的不大好，大意是图里这个样子。最底下一层bit array表示那个index所代表的id有没有被占用。然 ...

原来如此！谢谢LZ的分享，有一个小问题就是如果index的个数是奇数怎么办？这样最底下一层会有一个index是单独的……有点没想通，还是一开始先判断一下给的N是奇还是偶。。。如果是奇数剪掉一个 单独处理一下？

Margaret601 发表于 2017-11-11 07:47
原来如此！谢谢LZ的分享，有一个小问题就是如果index的个数是奇数怎么办？这样最底下一层会有一个index是 ...

奇数的话就可以也按这个方法来，但在initialize的时候把后面多余的设成0表示unavaliable吧！比如如果只有7个，那那个图里的bit array一开始intialize成11111110

问一下java 里有bit array这个东西吗？boolean[] 下面还有更小的吗？

asdf61 发表于 2016-12-4 02:29
给你一个max_id的值，然后写两个function分别是allocate_id和deallocate_id。

allocate_id每次call的 ...

Why not use a Queue + Bit Array to do this question?

Queue - stores all the available numbers
Bit Array - checks if the number is used

allocate() -> Pull from the head of the queue O(1), update in bit array its status to 1 O(1)
deallocate_id(id) -> set in bit array the status to 0 O(1), add the id in the end of the queue O(1)

谢谢楼主分享！看了这么多总算了解一点