a*******3
发帖数: 27 | 1 第二题是找最长匹配的前缀码？还是说从某个特定位置的开始的数字串匹配到字典也算？
如果是第一种的话，可以把词典简称 trie数吧，不是以字母来建，而是以字母对应的
数字来建，这样查询数字串直接一遍遍历trie，找到最底层的，是合法word的节点就行
了。
第一题，2^40的数，如果没有重复的，那么分段计数应该是最好的方法。如果有重复的
，那么就分段写回硬盘。
比如16M内存，那么分为长度为16M为一个区间，读一遍，将每个区间单独为一个文件。
将数据写入对应的区间。
第二遍遍历每个文件，用16M做bitmap，只需要找到第一个置0的位就行了。
IO复杂度，2遍读，一遍写 |
|
h****y
发帖数: 12 | 2 面试前在版面上看不了不少，非常感谢大家，面完也把我的经历写出来，供大家参考吧。
一面一开始问我谈谈我做过的项目，感觉说的很糟糕，一直不得要领。面试官感觉很怒。
给出两个字符串，让我判断串2里面的单词是不是串1的真子集。就只有这个问题，比如
s1 = "this is a test" s2="test test test" 返回真。如果s2是"is test a this"或
者"hello world"，返回false。字符串里只有单词和空格，所以用空格split就可以了
。代码很快就写完了，不过感觉面试官说话很快，我也有有点急，虽然自己做了测试走
了一遍，但是代码有个小bug(把问题想复杂了，删了一段代码之后就正确了)。感觉一
面自己不在状态。 之后它又问我，hashmap是怎么实现的，然后我就讲了具体实现。然
后又问了各种空间时间复杂度。
二面感觉好多了，面试官介绍做过的项目，由于一面问过，这次就好多了。
第一个问题是经典的两数求和，数字可以有重复，返回所有的对。比如2，3，3，4，3
，然后和为6，应该返回3,3 2,4 3,3。这个很快就写完了。
然后第二个问题是从1到n的数，... 阅读全帖 |
|
j*****y
发帖数: 1071 | 3 bless
两数和的问题应该是返回 3，3； 2， 4； 3， 3； 3，3 吧 ?
面试前在版面上看不了不少，非常感谢大家，面完也把我的经历写出来，供大家参考吧。
一面一开始问我谈谈我做过的项目，感觉说的很糟糕，一直不得要领。面试官感觉很怒。
给出两个字符串，让我判断串2里面的单词是不是串1的真子集。就只有这个问题，比如
s1 = "this is a test" s2="test test test" 返回真。如果s2是"is test a this"或
者"hello world"，返回false。字符串里只有单词和空格，所以用空格split就可以了
。代码很快就写完了，不过感觉面试官说话很快，我也有有点急，虽然自己做了测试走
了一遍，但是代码有个小bug(把问题想复杂了，删了一段代码之后就正确了)。感觉一
面自己不在状态。 之后它又问我，hashmap是怎么实现的，然后我就讲了具体实现。然
后又问了各种空间时间复杂度。
二面感觉好多了，面试官介绍做过的项目，由于一面问过，这次就好多了。
第一个问题是经典的两数求和，数字可以有重复，返回所有的对。比如2，3，3，4，3
，然后... 阅读全帖 |
|
|
c***f
发帖数: 40 | 5 用bloom filter 考虑将元素hash 到bitmap上吗？？ |
|
r**h
发帖数: 1288 | 6 请教一下，使用inverted index的话，求并集或者交集如何做到小于O(N)呢？
无论是sort之后有序查找还是使用bitmap，最坏情况下复杂度还是O(N)呀 |
|
r**h
发帖数: 1288 | 7 请教一下，使用inverted index的话，求并集或者交集如何做到小于O(N)呢？
无论是sort之后有序查找还是使用bitmap，最坏情况下复杂度还是O(N)呀 |
|
b****g
发帖数: 192 | 8 我昨天看了LZ面经于是写了个iterative的手机键盘数字，通过了leetcode测试。
我写的是最幼稚的那种，就是比如输入是"29",就建个
vector["abc","wxyz"]
然后把另一个vector从[0,0]做像数数一样的累加
[0,0] [0,1] [0,2] [0,3] [1,0] [1,1] [1,2]... [2,3]
每个vector都对应一种输出。比如[1,2]对应"by"
其实就是数数，有点像bitmap的感觉。 |
|
s*****n
发帖数: 5488 | 9 malloc一个对象的overhead好想是32bytes.这个大家可以放狗。
那么着就太贵了。而且会造成内存碎片。
如果很小。不如做成固定大小的slot. 改external fragment为internal fragment.
另外一个问题是garbage collection.改成page table方式加上bitmap.
应该不用compact。
基本还是OS书上的内容吧。 |
|
|
y****i
发帖数: 312 | 11 应该可以直接上bitmap吧。扫两遍就可以找到重复的电话号码了。 |
|
r****s
发帖数: 1025 | 12 bitmap不就行了，又没有说什么无限长度之类的。 |
|
m****r
发帖数: 141 | 13 Could you please give more details about how to use bitmap for solving this
problem ? |
|
w*******e
发帖数: 395 | 14 希望招的一定是国人
我刚面过vsan group，onsite 4个interviewer全是阿三
其中有个阿三竟然要我把buddy system的data structure code出来，就是那几个list
，不同density的bitmap，还要写一个init的API把data structure的初始化写出来
这个难度可不是一点点。。。
decide |
|
s*****r
发帖数: 43070 | 15 不需要sort两个，一个就可以了，sort是比较cost的解法，这题也可以不用sort，比如
用bitmap |
|
l*n
发帖数: 529 | 16 不知道数的范围就上bitmap的话，岂不是要有很多浪费？hashmap就是专治稀疏数据的。
把A数组hash一下，然后过一遍B就知道AB的交集，同理CD pair也过一遍。然后AB的结
果跟CD的结果再过一遍。因为是随机的数，AB的交集肯定很小了。 |
|
|
i******w
发帖数: 407 | 18 我就是用hash这么答的，人说不满意。
哪位大牛能把bitmap解释一下吗？
的。 |
|
l*n
发帖数: 529 | 19 用一个array或者bitmap来标记吧，就是从00000到11111，反正只是iterator，不需要
按照元素个数多少排列。 |
|
P*******r
发帖数: 210 | 20 多谢。
晕了，居然忘了bitmap. 面试官提示状态机，但是当时脑子短路了。
对了，忘了说是 小于 整个长度的subset, 比如说 1，2，3，4，5，6. 要求输出size
《=4的所有subset.
略复杂一点，思路一样。 |
|
H*********a
发帖数: 34 | 21 有谁能解释下怎么用bitmap找下一个permutation呢？ |
|
k******e
发帖数: 375 | 22 (3) 7 million放hashtable内存应该没啥问题吧。不够内存的话，用Trie应该是好方法
。还不够内存的话，就用9,999,999,999个bitmap，每一个bit存相应电话号码(1-
exists,0-nonexist)。
(4) 没理解为什么是O(n2)。friends+friends of friends每一个人过一遍，难道不是O
(N)吗？搞一个Set，一个个往里加不就行了吗？ |
|
k******e
发帖数: 375 | 23 (3) 7 million放hashtable内存应该没啥问题吧。不够内存的话，用Trie应该是好方法
。还不够内存的话，就用9,999,999,999个bitmap，每一个bit存相应电话号码(1-
exists,0-nonexist)。
(4) 没理解为什么是O(n2)。friends+friends of friends每一个人过一遍，难道不是O
(N)吗？搞一个Set，一个个往里加不就行了吗？ |
|
i**********n
发帖数: 196 | 24 假设忽略大小写，那么可以建一个n*26的bitmap矩阵。然后遍历各列，去除overlap的
word，这需要o（n）。
剩下的word都是互不overlap的，那么可以在线性时间内找到长度最大的两个word，返
回之。
整体的复杂度还是o（n） |
|
|
q*******i
发帖数: 353 | 26 美国CS master毕业，现在relocate 到湾区，希望在这边能找CS相关职位，希望哪位好
心人内推（尤其看到amazon最近出了很多湾区职位，不知道有没有amazon的兄弟姐妹帮
个忙）。
CS基础课程基本满分GPA，硕士的thesis是用CUDA做金融方面VaR(value at risk)的加
速，除了CS master的课程学习和project经验，还自己学习了coursea上面几个web
programming还有andriod的课程，做过数个project， 附上自己的project 简介，所有
代码都可以在https://github.com/zzMOM查看。 使用过的语言包括Java, JavaScript,
C,HTML, CSS, SQL,使用过的platform包括Android, GitHub, HeroKu, Node.js, AWS,
Bootstrap, CUDA (GPU programming), MySQL, PostgreSQL, ArcGIS, ERDAS,
Eclipse, Emacs, Vim, 目前也在刷leetcode和CC150.... 阅读全帖 |
|
F********9
发帖数: 44 | 27 第二题也算是提示你用bitmap了吧：
说1 B个整数正好是4G， |
|
c**y
发帖数: 172 | 28 我怎么也感觉第二题就是用bitmap呢？O(n) |
|
H*********a
发帖数: 34 | 29 lz说他问了这些数大小没有范围的，这样的话，bitmap是不能使用的吧。因为你不知道
需要多少个bit来表达数字。大家觉得呢？ |
|
s*******z
发帖数: 83 | 30 我觉得还好,不能算是故意刁难.
有一点是面试里面听不懂一定要求他说清楚, 没有说清楚是他的责任, 但是听不清楚就
做题是你的责任了, 就是平时间deliver东西一个道理, 你不做都比assign给你以后不
完成要强的.
第二个应该heapsort和bitmap都是比较好的法子了. |
|
m*****n
发帖数: 2152 | 31 void BFS(Queue > que)
{
while(!que.empty())
{
for(int i=0; i
{
bitset search = que.front() | map_color[i];
if(search.all()) break; // fount it
else que.push(search);
}
que.pop();
}
} |
|
k*******r
发帖数: 355 | 32 我来想个"how to adjust the index of each element because after
each move the index has been change"
这个adjust必须在log(n)时间内完成不然就没意义了
我的想法是不需要真的adjusted index of each element, 我们只需要给定一个原始
index, 知道这个index后面有多少元素已经被用了。比如某元素原始index为5， 同时
我们知道5后面已经有3个元素被用了，那么现在此元素新的index就是5+3=8
怎么在log(n)时间内知道给定index后面多少元素被用了呢，用2叉平衡树分查找或者
bitmap都可以快速做到 |
|
d*****h
发帖数: 8 | 33 LZ， 第一题就是glassdoor上大家说的buddy bitmap吗？这题看起来就很正常啊但怎么
好多人说难。是有什么限制或者follow up吗？
第二题的addTask里说的“trigger之后”是指trigger被调用之后但是还在运行还是指
trigger被调用之后都算？
第四题： 我的解法是用一个Hashmap，加一个field: version。 entry的形式是<
Integer, Node>
class Node
{
int value;
int version;
}
每次clear时map的version++。这样是符合要求的吗？
谢谢~
为1 |
|
z***y
发帖数: 73 | 34 哈哈哈哈哈哈。
本来觉得他们公司挺好的，结果上glassdoor一看，各种搞笑。
说他们家面试题目有的比较晦涩，给了提示后就更加晦涩啦；有得吐槽，自己压根不懂
C++，简历也跟C++没半毛钱关系，结果电面第一个问题就是C++。
据说他们家的经典题目：
1.C++对象内存布局；
2.Buddy bitmap，应该就是lz说的这个；
3.Draw circle，应该也是lz说的；
4.设计一个key value系统，也是lz说的题目。
Buddy那题感觉是做内存管理的，假设内存池可以支持256K 128K 64K 32K四种大小，那
么就可以理解成一个这种树，可以分配256K必须他下面的2个128k可用，递归下去所有
子节点都要为可用。很好理解。 |
|
d*****h
发帖数: 8 | 35 LZ， 第一题就是glassdoor上大家说的buddy bitmap吗？这题看起来就很正常啊但怎么
好多人说难。是有什么限制或者follow up吗？
第二题的addTask里说的“trigger之后”是指trigger被调用之后但是还在运行还是指
trigger被调用之后都算？
第四题： 我的解法是用一个Hashmap，加一个field: version。 entry的形式是<
Integer, Node>
class Node
{
int value;
int version;
}
每次clear时map的version++。这样是符合要求的吗？
谢谢~
为1 |
|
z***y
发帖数: 73 | 36 哈哈哈哈哈哈。
本来觉得他们公司挺好的，结果上glassdoor一看，各种搞笑。
说他们家面试题目有的比较晦涩，给了提示后就更加晦涩啦；有得吐槽，自己压根不懂
C++，简历也跟C++没半毛钱关系，结果电面第一个问题就是C++。
据说他们家的经典题目：
1.C++对象内存布局；
2.Buddy bitmap，应该就是lz说的这个；
3.Draw circle，应该也是lz说的；
4.设计一个key value系统，也是lz说的题目。
Buddy那题感觉是做内存管理的，假设内存池可以支持256K 128K 64K 32K四种大小，那
么就可以理解成一个这种树，可以分配256K必须他下面的2个128k可用，递归下去所有
子节点都要为可用。很好理解。 |
|
r****s
发帖数: 1025 | 37 option 1:
int array这个应该是比较明显的提示，用bitmap sort类似的方法。
用一个2^32长度的array，每个element保存一个1/2值(short),那么总共需要的内存是2
^32=1k*1k*1k*4=4g。开个6g的java process就可以了。
然后把两个file读一遍就可以了。
option 2:
如果内存不够，就把array分成几次，每次都读一遍file。这样的好处是避免写硬盘。
option 3；
先把file分成小文件，然后再读入。这样的问题是写硬盘。
这样解题比较balanced，不偏向任何一方。 |
|
|
x***j
发帖数: 75 | 39 自己的第一个onsite, 题目不难，目测已跪，攒人品发面经。 另外： 长期求各种内推
，地点不限， 不胜感激！！
第一轮电话面经在这里：http://www.mitbbs.com/article_t/JobHunting/32818751.html
第二轮电话面：
白人，说我只能给你25分钟，写两个题，于是特别紧张。
1）写个任意树的数据结构， 再写个search(int val)的函数，返回一个节点。
2）解sudoku，
3） 问了5分钟research, 然后5分钟回答问题。
当天告诉下周可以来onsite了。
1) 是个国人大哥， 人不在现场，Skype的。感觉大哥给的问题不算难。但自己还是太
紧张了，而且交流不太好，代码写的一塌糊涂。
题目1： 给一棵二叉树， serialize成字符串，
题目2： 给一个字符串， deserialize成二叉树。
2) 一个白人，
题目： 一串灯泡，实现 flip(int i, int j)， isOn(int i)两个函数， 自己想数据
结构。followup 很多， hashmap, bitmap, tree 都用上了。
3）一个小印... 阅读全帖 |
|
|
|
c*********t
发帖数: 171 | 42 老了不知道bitmap是什么意思，如果是用一个bit纪录某数是否出现过那一定是错的。
考官会说没有那么多额外的存储空间。
所有这些很大很大的问题其实都是问排序！ |
|
o***e
发帖数: 28 | 43 我觉得用一个文件来存储 bitmap (如您所说每一位代表该数字出现与否) 还好吧 可以
用 O(X) 的空间 (其实是 \Theta(X/8)) 换取 O(Y) 的时间
如果 X, Y 很大以至于需要外排序的话 其实效率也不高吧 : ) |
|
B**********2
发帖数: 923 | 44 第三个题楼主不是说分布式么。
每个计算单元假设内存极限是 Z, 则一共需要 X/Z = N个
把 X 分为N段，每段用一个单元来查就行了
bitmap是位表，C++一个标准Template
这样做不用排序，过一遍就行了
排序基于比较时间是O(N logN), 这题的意思本来就是N很大。
既然分布式了，就可以空间换时间了 |
|
a******u
发帖数: 69 | 45 bitmap上线性查找是指做assign的时候要找没用过的id？
多层不同粒度优化是指，先用查大block里面有没有没有的id然后再逐步深入到更小的
block里？ |
|
|
e********2
发帖数: 495 | 47 4叉树，插入常时间，就是空间可能有点大。Bitmap之类的各有利弊。 |
|
e********2
发帖数: 495 | 48 4叉树，插入常时间，就是空间可能有点大。Bitmap之类的各有利弊。 |
|
S*******C
发帖数: 822 | 49 /**
* 10.3 Given an input file with four billion non-negative integers, provide
an algorithm
to generate an integer which is not contained in the file. Assume you have
1 GB of
memory available for this task.
FOLLOW UP
What if you have only 10 M8 of memory? Assume that all the values are
distinct and
we now have no more than one billion non-negative integers.
CC Page 347
*/
import java.io.*;
import java.util.Scanner;
//A bit array (also known as bitmap, bitset, bit string, or bit vector) is
an ar... 阅读全帖 |
|
w*****d
发帖数: 105 | 50 1. 看成scheduling问题变体：
1）找到最多的不重合meeting（scheduling问题，O(NlogN)），安排到room 1；
2）将已安排的meeting删除，如果还有剩余，重复1）且room数加1；
总体时间复杂度O(N^2*logN)。
2. 关键看看id是什么：如果是有限集合的字符串或者不连续int，用list；如果是有限
连续int，可以用bitmap；如果是无限连续int，那就一直current++吧，呵呵。 |
|
