s*****i
发帖数: 355 | 1 有重复的就计数器加一。用ascii bitmap的方法比较好 |
|
d****v
发帖数: 458 | 2 具体说一下什么是 ascii bitmap啊
用计数器这就涉及到上面说的true bias的时候第二个很长的可以不全遍历了吧 |
|
g*****u
发帖数: 298 | 3 我感觉Elevator类还是应该记录所有它应该停靠的楼层，比如用stop_floors表示，而
不只是一个destination。这个可以用bitmap或者数组来实现。电梯里的人可以按下多
个楼层。另外bank收到楼梯间的request的时候，决定哪个电梯来响应这个服务，并把
该楼层加入到相应服务的电梯的stop_floors里。在某一层停过后就从中删除。 |
|
|
s********f
发帖数: 510 | 5 1 知道range可以用bitmap，不知道range如果spaceO(1)最快也就是nlogn了吧？
2 第一次取样就是是头10个，第二次就是两个10的取样各50%几率再取样，
第三次就是已有的10个有2/3的几率被取，新的10个有1/3的几率被取，再取样。
第n次就是以后的按(n-1)/n的几率，新的按1/n的几率取。
45 |
|
|
t******t
发帖数: 2404 | 7 range小才行. 否则bitmap比hash还大. |
|
|
j*****u
发帖数: 1133 | 9 thanks for sharing!
follow-up: 如果有一个big single file, many servers, how to use these
servers to compute this problem? 要求尽量balance load
我觉得这个题没什么意义，除非这个file是存储在distributed FS，有replica。因为
如果在单机上，要distribute要首先split这个file，这就已经是一次读写了，读写中
还有一个是remote的。有这一次读写去重已经完成了。
如果是unsorted并且bitmap不能fit到single memory，这时并行才有意义。 |
|
|
r**u
发帖数: 1567 | 11 1) 你的一维array size算得不对吧。应该是256*256/(32bits/int)
如果给的start, end, eraseStart, 都是一维array的index，
就要换算一下在哪个int里，然后set off行了吧，像bitmap operation.
如果给的是2D array的index, 换算麻烦点。
是做
off。
256/ |
|
m*****g
发帖数: 226 | 12 那个1billion的问题，我也被问的
难道是一个人？
当时我就先说hash, 然后再说的bitmap |
|
v****s
发帖数: 1112 | 13 恩，那天我们组的老美也说了radix sort, o(nk). 但是我觉得我说的bitmap也是o(n),
interview也太tough了吧。。。 |
|
|
m*****g
发帖数: 226 | 15 如果把cache之类的考虑上来的话，还是bitmap最好阿
有没有牛人说说这题
usage + cache usage.
Amazon, Yahoo...
ago to test people. |
|
m*****g
发帖数: 226 | 16 如果把cache之类的考虑上来的话，还是bitmap最好阿
有没有牛人说说这题
usage + cache usage.
Amazon, Yahoo...
ago to test people. |
|
v****s
发帖数: 1112 | 17 i've done this calculation during the interview, and told him i could finish
this using bitmap in a 32bit machine.
usage + cache usage.
Amazon, Yahoo...
ago to test people. |
|
l*****a
发帖数: 14598 | 18 1 billion =1000 million=10 pow 9
which need (10 pow 9)/8 =125*( 10 power 6)=125M memory
to use bitmap
usage + cache usage.
Amazon, Yahoo...
ago to test people. |
|
v****s
发帖数: 1112 | 19 where did u get this "2GB"?
i think a 32 bit machine has 2^32 ~~ 4GB, though a bit less than exactly 4GB
, which is about 3.4GB.
besides, bitmap deal with "bit" , so it's significantly less than 3.4GB .
app |
|
H*X
发帖数: 281 | 20 why do you need 4GB in the first place? why do you want to use 1 Byte per
integer? He was suggesting the bitmap method...not the "bytemap method". |
|
r********g
发帖数: 1351 | 21 我记得programming pearls上有关于大数组的讨论，但要是想找出所有的duplicate，
还是bitmap
最好吧...如果只需要找出一个duplicate，估计有更好的办法（怎么我的印象还是跟
binary
search有关的）....
usage +
cache usage.
Amazon,
Yahoo...
ago to test
people. |
|
m*****r
发帖数: 280 | 22 I assume 4 bytes for an integer. Bitmap may use no memory in
case of all zeros. But should your program consider the worst case? |
|
g*****t
发帖数: 42 | 23 两个array, 要找公共elements, 没有duplicate
我说用bitmap
他说是sorted，
我说用for循环， O(n+m)
他说其中一个比另一个长的多
我说用binary search
他说那个长的太长了， 没办法放memory里，
我说还用binary search
他说要做一下preprocessing
还说了些提示， 实在听不清楚， 就换题了。
有没有高人给点拨一下？ |
|
v****s
发帖数: 1112 | 24 bit map is also called bit array |
|
x**********n
发帖数: 1262 | 25 programming pearl 前面一章有 |
|
|
m********g
发帖数: 692 | 27 take 8 out, when constructing the bitmap.
number |
|
w******1
发帖数: 520 | 28 raou , bitmap怎么建造， 能讲讲么？ |
|
w******1
发帖数: 520 | 29 Thank you
I got it.
如果有这样的题。比如N 个数中有几对重复的数， 也可以用这个BITMAP来实现了。 第
一次出现， 这个数，设定值为一， 第二次出现， 就直接打印出来。
/* phase 1: initialize set to empty */
for i = [0, n)
bit[i] = 0
/* phase 2: insert present elements into the set */
for each i in the input file
bit[i] = 1
/* phase 3: write sorted output */
for i = [0, n)
if bit[i] == 1
write i on the output file |
|
s*********t
发帖数: 1663 | 30 来自主题: JobHunting版 - 一道微软题 似乎会了
bitmap
遍历输入，将所有覆盖的bit标记
标记操作是o(1)的
之后输出
than |
|
l******c
发帖数: 2555 | 31 来自主题: JobHunting版 - 一道微软题 什麽是bitmap， 是STL 里的吗 |
|
g*****u
发帖数: 298 | 32 来自主题: JobHunting版 - 一道微软题 这个有问题。如果你把输入的(5,7)改为(0,7)，就不对了。
我的做法是，
1. 只排序n个起始点，用bitmap，O(n)
2. 然后一个区间一个区间的进行合并，O(n)
第一步如果范围太大会占用过多空间，而且需要初始化。
如果题目要求不能用排序，暂时还没想到办法。 |
|
r****o
发帖数: 1950 | 33 来自主题: JobHunting版 - 一道微软题 bitmap啊，
你说的两个指针比较能不能再详细说说? |
|
l******c
发帖数: 2555 | 34 来自主题: JobHunting版 - 一道微软题 a 数组排序第一个元素， b 数组放另一元素
if b[i] > a[i+1]
cross out b[i] and a[i+1]
else
no overlap.
O(n) compare and output.
什麽是bitmap 排序？ |
|
r****o
发帖数: 1950 | 35 来自主题: JobHunting版 - 一道微软题 多谢。那你的b[]要排序吗？我觉得b[]要排序。
bitmap就是在坐标轴上对相应的元素作标记把。 |
|
l******c
发帖数: 2555 | 36 来自主题: JobHunting版 - 一道微软题 是有问题， 不过这bitmap sorting 就是大空间法， 时间等于range， 不是个数。
有一百对元素， range是 -10000 到 10000， 显然不对 需两万比较 |
|
y**i
发帖数: 1112 | 37 感觉像bitmap一样？当然bit是2进制
但是7和9是对应4个字母，比较特殊，这里怎么办？ |
|
|
|
m******s
发帖数: 204 | 40 整个过程很折腾人： 说好的上午11点，结果到11：30am没人打过来，打电话到人力资
源的联系我的人，被告知要面我的烙印还在来办公室的路上，又重约了个1：00pm，打
过来要我用google的共享文档写程序，问题是之前的电子邮件里根本没提要准备电脑，
只好回家，路上烙印有打来电话，问何时能到，因为他2：00pm还要开会。。。
问了两题，答的很糟，将题目列出和大家讨论一下：
1。 给出一个柱状图，求其中最大的长方形面积.
2。 给出一个数组，创建一新数组，删掉原数组的重复的数。（问了能不能用bitmap或
排序，被告知不能用很多额外的内存）
另外，记得有人发过一个博克的连接是专门收集Google面试题的，能否告诉我？现在找
不到了。 |
|
w****l
发帖数: 88 | 41 我觉得第二题既然不能sort,也不让用bitmap， 那么简单的方法是将原始数组的数放到
一个set中，然后遍历这个set，就可以自动删除重复元素了....望高手赐教 |
|
m*****g
发帖数: 226 | 42 第二题，不能sort, 不能用内存（包括bitmap)
那就是不能遍历然后预处理
那就(n2)硬来？ |
|
l*********y
发帖数: 142 | 43 我是在看
http://www.mitbbs.com/article/JobHunting/31491461_3.html
bloom filter可以看做是对bit-map的扩展。
我原来的想法是bloom filter要比bit map省空间，因为bloom filter设计的思想就是
用错误率换空间。但是看了那个帖子里的两道题，又迷茫了不少。
问题1：给你A,B两个文件，各存放50亿条URL，每条URL占用64字节，内存限制是4G，让
你找出A,B文件共同的URL。
建议答案：根据这个问题我们来计算下内存的占用，4G=2^32大概是40亿*8大概是340亿
，n=50亿，如果按出错率0.01算需要的大概是650亿个bit。现在可用的是340亿，相差
并不多，这样可能会使出错率上升些。另外如果这些urlip是一一对应的，就可以转换
成ip，则大大简单了。
问题2)2.5亿个整数中找出不重复的整数的个数，内存空间不足以容纳这2.5亿个整数。
将bit-map扩展一下，用2bit表示一个数即可，0表示未出现，1表示出现一次，2表示出
现2次及以上。或者我们不用2bit来进行表示，我们用 |
|
S******a
发帖数: 862 | 44 这道题我觉得就是看看编程基本功，把程序写对就行。
我onsite还碰到过找出数组里最大的数，汗。。
具体来讲，思路就用bitmap
以下是以前的讨论：
======================================================
则：
======================================================
非常感谢你的回答！
我觉得用一个a[9]，然后扫描三次，每行，每列，每block。你的虽然扫描一次，但每
个元素要跟多个不同的a[9]比较，总的比较次数应该和我说的一样，但我说的用的a[9]
少一些。你觉得呢？我是不是哪里理解不对？
========================================================
======================================================== |
|
u**s
发帖数: 50 | 45 This method looks like O(nlogn).
However, when you code it, you will notice that dedup is a little bit
annoying.
If you create a bitmap/boolean for n^2 and init to false, then this is
already n^2. Of course, you can use other hashtable to solve this, but just
looks ugly.
If you ignore this issue, then you can say this is O(nlogn) ... |
|
w*****o
发帖数: 166 | 46 3)不用sort吧？直接用了min-heap，复杂度要小些。
4）bitmap
5）先按照文件大小排序。如果给的俩文件大小不同，直接返回。如果大小相同，再用
hash。如果hash相同，再逐个逐个byte比较。最后确定是否是duplicate。 |
|
I**A
发帖数: 2345 | 47 repeating phone numbers between two files?
how large are the files? can one of them fit into the available memory?
if so, are we allowed use hashtable?
if not,use bitmap?
number
sorted. |
|
|
p********7
发帖数: 549 | 49 不用多余space是做不到O（N）
应该是bitmap 可以少用点空间 |
|
K******g
发帖数: 1870 | 50 这个一般用hash或者bitmap吧，就可以O（N）了
)了 |
|
