h******2
发帖数: 13 | 1 有两台机器，每台10T数据， 数据中都是url，每行一个url， 他们只有万分之一的
diff， 要查找有这两台机器的url的差集， 需要一个准确的结果（不能用boolfilter)。
类似的一题是：也是两台各10T数据，一开始两边数据相同，后来可能两边有更改，如
果能够提供一个接口，快速的比较两边数据是否有diff， 如果有，diff的是哪些url。 |
|
l****i
发帖数: 2772 | 2 昨天发了A家onsite杯具的面经，几位同胞建议我要总结一下面试的技巧。我就一次把6
个杯具都简单总结一下，包括一些面筋，也希望版上的大牛指点一下。
基本个人背景，US CS fresh PhD,国内3年国企IT部门经验，国内的工作基本就是天天
写SQL。1月初才是投简历，至今，10+个电面，拿到6个onsite，已全部杯具。
Onsite 1：
某电脑公司美国做cloud的分支。电面一轮，拿到onsite。onsite面了有5轮，有3轮
都很顺。感觉悲剧有2轮，如下：
1.2 国女，拿着一本中文打印的java面试题目，随便翻到一题，就写着版上问我，基本
都是关于java一些属性的题。其中有2道题，我不是很确定，就询问，能否讨论一下结
果，国女每次都很严肃的和我，“This is interview, I cannot tell you true or
false. I cannot tell you anything.”. 拒绝和我讨论任何题目的答案。此国女的态
度，就是interview就是考试。不需要沟通讨论。
1.4 台湾CTO，上来写了一个算法给我，就是常见的二分法求乘积。让... 阅读全帖 |
|
j******2
发帖数: 362 | 3 实战得来的，都没答好，希望对后人有用
1.一个文件里超多行，每行格式是
user_id, item_id
其中item_id有很多重复。怎样压缩。
答案：用哈夫曼coding（越常见的用越少bit）
2.一个超大磁盘（大于内存），串行存了很多文本文件，格式是
file_name, file_size, file_content
有几十台机器可用，怎么找出重复文件。
答案：第一步：分区，用哈希函数把文件内容映射到一个整数，按整数分区到不同机器
上；第二步：在各机器上用哈希表（文件内容为key，个数为value），最后输出重复的
。 |
|
f*********1
发帖数: 75 | 4 大家看这个行不行？
由2^k 得到启发
建一个大表 每行表示一个ad， 每列表示frequent query string 的一个词，表的值表
示单词是否出现在某一个ad里。
wordcount new... york ...department ...store ... sale.
ad1 5 1 1 1 1 1
ad2 1 0 1 0 0 1
ad3 4 1 1 1 1 0
...
adn 1 1 0 0 0 0
建表需要O(N)
查询需要先生成query string的所有subsets， 这一步需要2^k, 然后与(&)query
string match对应列vector，选与值为1的ads。最后再用第一列的word cou... 阅读全帖 |
|
f*********1
发帖数: 75 | 5 大家看这个行不行？
由2^k 得到启发
建一个大表 每行表示一个ad， 每列表示frequent query string 的一个词，表的值表
示单词是否出现在某一个ad里。
wordcount new... york ...department ...store ... sale.
ad1 5 1 1 1 1 1
ad2 1 0 1 0 0 1
ad3 4 1 1 1 1 0
...
adn 1 1 0 0 0 0
建表需要O(N)
查询需要先生成query string的所有subsets， 这一步需要2^k, 然后与(&)query
string match对应列vector，选与值为1的ads。最后再用第一列的word cou... 阅读全帖 |
|
f*********m
发帖数: 726 | 6 从版上大牛的面经中找到的：
---------------
1）原题can Jump, 然后拓展到minJump, 我用dp + greedy从左边做， 写完code,他要
求再说说从右边忘左边如何高。 我说还是dp + greedy（这个估计是他自己背的答案）
，他想了会说， 算了，好像跟你的一样！我也不知道是不是一样就move 到下一道题了。
从右往左好像不好想吧，从左往右跳（最后跳到最右边）和从右往左跳（最后跳到最左
边）不是等假的吧？
-------------
2）一个BST tree， 现在要求在每个node， 添加一个succeesor的指针。 用递归搞定
（这个在他提示下搞出的，code 用递归就几行而已）
考虑inorder 的succeesor。用inorder traverse，大家看对不对？
void inorder(node* n, node*& prev)
{
if (!n)
return;
inorder(n->left, prev);
if (!pre)
pre->succeesor = n;
pre = n;
inord... 阅读全帖 |
|
r**h
发帖数: 1288 | 7 5） 写个函数 输入7张牌， 然后输出是否有同花顺， 顺子， 和同花。 return 一个
int 然后turn on 里面3个bits建立一个14*4的矩阵，把输入的排放在矩阵对应的位置
，然后扫描每行、每列看能否组成花顺， 顺子， 和同花。还有跟好的方法吗？
刚写了一个判断梭哈的，发现只要记录每种颜色的牌总数和每种号码的牌总数就行了 |
|
Q****s
发帖数: 1301 | 8 给一个文件, 里面每行一个数字, 让我对其排序并且删掉重复的(留下一个),
可以用shell,java, 或者c++, 随意.
告诉我先做, 他要离开6-7分钟.
我说用shell一行不就出来了吗?
他说我给你换道, 我说要不你先去? |
|
|
u*****o
发帖数: 1224 | 10 LZ愿意分享一下你的CODE吗？我觉得我脑子比你还乱，自己在纸上写了写，已经放弃了
。。如果每行字符不一样的话，好麻烦的啊。。。 |
|
h***i
发帖数: 1970 | 11 此题还好,先读到文件的长度,然后就挨行读,每行你都能计算到要写的初始位置,seek到
那儿,再写就行了.只需要一个变量来累加读了多少byte就行了. |
|
r*******e
发帖数: 7583 | 12 ext4/NTFS的单个文件最大size是16TB
每行一个字符的话，行号肯定放不进内存哈 |
|
c******a
发帖数: 789 | 13 18.12就调用一次，求最大sum的sub－matrix，熟max－run的立刻就能想到用max
histogram每行搞一搞max－run了。
这题鼓励pre-compute，多次调用，我晕了5分钟max－run不work我就去看答案了,555。
你这么一说的确是，关键就是：利用已有matrix们O(1)解要求的matrix。 |
|
r*********n
发帖数: 4553 | 14 更简单一点的方法是
1.一本书随机选出来N页
2.每页随机选出M行
3.每行随机选出L个单词
做N*M*L次string comparison，如果有超过95%的结果是相等，则两本书是一样的。 |
|
s***5
发帖数: 2136 | 15 是简单版本，每行第一个比上一行最后一个小。
bottom |
|
B*******1
发帖数: 2454 | 16 1个星期写了1000行汇编，每行都是simd的。 |
|
|
|
|
a**********0
发帖数: 422 | 20 就是那个 \n了 哈哈 主要担心hadoop的mapper 我设置的是ascii作为输入 |
|
f*****6
发帖数: 61 | 21 一个烙印面试官，声音给人感觉死气沉沉的。。。
上来就说了下自己的名字，问我是不是面这个的人。
然后也没叫我自我介绍，就问我熟悉啥语言。我说java用的多。然后就直接突然问题目
了。
基本都是概念题。
linkedlist 和 array的区别
我就分析了时间空间上以及对于element操作的一些特点，然后他继续问我还有其他不
同么，我沉默了一会感觉脑子空白了，然后他就说ok就下一题了。
什么是binary search tree，什么是HashTable, binary search tree和HashTable的区别
static的作用
什么是mutable object in java
然后就出了一道括号匹配的编程题，判断是不是wellformed的String。我先说了思路，
然后就在doc里写，很快就写完了面试官也没多问，就问了代码每行是干嘛的。
今天发信问HR已经说move forward another candidate了好吧。
简历上的东西一个没问.
面试过程中的确因为听力问题有的话让面试官重复了一边。或者叫他打在doc里。。。
太菜了，继续找面试，多积累多锻炼吧。真的... 阅读全帖 |
|
A***o
发帖数: 358 | 22 feel like a tough team
* 哈度基础
* restful services
* SOAP
* 分布式事务
* 控制反转, 依赖注入
* 代码题重建多叉树，输入一文件，每行一条根到叶的路径，其实就一特殊的trie |
|
m**********j
发帖数: 610 | 23 来自主题: JobHunting版 - 求解面试题 epic，电面，第一轮
给一个2D table，每一个entry是boolean
find rows with most entries in common (could be two or more)
比如说有2行分别是011011， 011010， 在6个column里面有5个相同
没说具体复杂度要求，不过不让对每行做pairwise comparison
对面的三哥说给你半分钟思考
没想出来要hint也不给 |
|
m**********j
发帖数: 610 | 24 来自主题: JobHunting版 - 求解面试题 epic，电面，第一轮
给一个2D table，每一个entry是boolean
find rows with most entries in common (could be two or more)
比如说有2行分别是011011， 011010， 在6个column里面有5个相同
没说具体复杂度要求，不过不让对每行做pairwise comparison
对面的三哥说给你半分钟思考
没想出来要hint也不给 |
|
|
u***8
发帖数: 1581 | 26 2个面试官，都不在一个office，用的远程，结果有一个很简单的，最后一个人的最后
一道题目，1个大file很大，sort里面的单词，每行一个词，memory只有1／100 of
file size.最后脑袋有点小短路。回答得磕磕巴巴的
有个印度人，有个国人吧。不知道国人大国会不会放水。哎。听天由命了。
想在悲剧之前给recruiter发信，说信号不好，没听清楚。想再面一次。湾区给钱大的
厂子就只有他家＋另外几家。怎么办
另外：要写thank you letter 么？ |
|
e******0
发帖数: 291 | 27 给出16 characters（可能有重复的）， 求在4*4的Grid上输出 valid words. (即每行
每列都是valid 4字母单词)。 给了字典。
a / / /
/ / / /
/ / / /
/ / / / |
|
e******0
发帖数: 291 | 28 给出16 characters（可能有重复的）， 求在4*4的Grid上输出 valid words. (即每行
每列都是valid 4字母单词)。 给了字典。
a / / /
/ / / /
/ / / /
/ / / / |
|
l*******g
发帖数: 82 | 29 把字典用suffix tree存放。
给出16 characters（可能有重复的）， 求在4*4的Grid上输出 valid words. (即每行
每列都是valid 4字母单词)。 给了字典。a / / / ........ |
|
c****m
发帖数: 179 | 30 谢谢lz，
那我来捧个场吧希望lz多share。
onsite里面的2，面试官说时间连续，但实际上还是离散的吧，因为输入是离散的？还
是说共有部分要加权，比如【2,4】 是100，【3,5】是200，【3,4】就是150， 而不是
300？
onsite里面的7，是想detect什么异常？如果不是复杂的log，是不是可以直接check
pattern或者hash。 你说的outlier detection，是说要把每行log先转化成feature，
然后把几个常见的pattern设为positive，异常的row作为negative，然后train
classifier吗，？
onsite 1，你是答得learn to rank吗，然后讨论该用什么做label吗？ 还是说想
newsfeed design一样人工设定各个权重？ |
|
a********9
发帖数: 129 | 31 google面的是SRE
电面是国人大哥，一些c语言的pointer问题，然后一道leetcode原题
onsite1:
1)combination,还是没dupliate的，要把结果保存起来，我说用linked list，因为是
用c写，还要自己implement linkedlist， 略坑爹
2) 就是很简单的统计两个string分别有多少个单独的letter
onsite2:
bst inorder iterator
onsite3:
一个文件，每行是rack_name + machine id，输出每个rack有多少个machine,按大小排
序，我是先扫一遍存hashtable，再存进linkedlist再sort，这回没让我实现hashtable
跟linkedlist了，不过要我把用过的api单独再declear一下，最后再写个mergesort
onsite4:
有很多个machine，要求检测哪些die了，要求parallel，就写了一个for loop创建若干
个thread来执行任务，有点thread pool的感觉,用一个array来表示哪个machine被检... 阅读全帖 |
|
p**********e
发帖数: 70 | 32 一开始觉得面得很好，结果拒信飘过， 继续努力中。。。。。。
无论结果如何， 发面经先。
小弟CS PHD， 打算找明年的fulltime，move on吧，anyway，跪求推荐 microsoft,。
。。。
一共五轮
round 1：
问简历， 问什么时候毕业，出乎意料的是，他们用的竟然是去年的简历，上
面写expected 今年十二月份毕业，我说这份简历啊好像没有update， 我打算明年7月
毕业了。。。。。
然后他就说做题吧。。。
求两个字符串的公共子串，然后去掉duplicate 部分。
test cases:
round 2: 不知道大小输入一个字符串流， 然后计算最近100个数的平均数，test
cases
round 3： 扑克题， 转化成字符串就可以了， 就是有一次重复得1分。像四个一样的
，就4得分。
round 4： format string 把一个非常非常长的字符串输出line by line， 每行有大
小，每个单词不可以拆开， 结尾不应该有空格， 所以空格要插入到单词之间，尽可能
要求每... 阅读全帖 |
|
l*********3
发帖数: 26 | 33
row
扫描，得到每行每列的和，并计算全部行列和,say, S. O(mn)time, O(m+n)space。
扫描行，每扫一行，累计在它上面的行的总和，在它下面的行的总和＝S-上面行总和-
本行和。扫描列同理。O(m+n)time, O(m+n) space
输出所有的平衡数： brute force, O(mn) time. |
|
M********u
发帖数: 42 | 34 假定输入是50m，每行4个数字，sizeof(double) * 4 =~ 32 bytes, 如果全部cache在
内存里，大概需要50m * 32 =~ 2GB。有的thread finish的比较早，有的比较晚是因为
每个thread分配到一样多的count，但是有的输入可能需要算很久。这类科学计算的问
题一般使用openmp，非常容易写。
http://en.wikipedia.org/wiki/OpenMP
可以用scheduling clause里的dynamic |
|
J****R
发帖数: 373 | 35 你的方法是什么？
我想的先对每个字符串按照单词排序，
然后把每行的第一个单词作为Key,行号作为list， 存在hashmap里。
对每个key对应的list 进行iterate,找到每个key对应的最长的pair的长度。
比较每个Key对应的最长的pair的长度，找到最大的。
time complex is nlgn |
|
c******3
发帖数: 5 | 36 来自主题: JobHunting版 - M的面试题 输入一个词典termDict.txt，每行一个单词，同时输入一个不含空格的字符串，例如：
ilovethisgame，输出包含空格的英文句子，例如I love this game。
要求：
1， 编码实现该函数，如果有多种可能输出，输出所有可能
2， 建议先考虑整体流程，再进行优化，若时间有限，可使用部分伪代码
3， 分析并讨论：如果有多种可能输出，如何选择最有可能的输出 |
|
f******n
发帖数: 53 | 37 来自主题: JobHunting版 - M的面试题 如果是考虑多种组合，显然是DP算法。
构建dp[s.length][s.length]
根据dict设置dp[i][j] = 1 其中s[i...j]可以在dict中找到
dp每行会有多个1
根据ilovethisgame的静态算法如下
显示的a[i] 为每个word的第一个字母位置
void printpath (int a[13])
{
for (int i = 0; i < 13; i++)
printf("%d ", a[i]);
printf("n");
}
bool findAllPath(int dp[13][13], int a[13], int s, int e)
{
if (dp[s][e] == 1)
{
a[s]=1;
printpath(a);
return true;
}
int i = s;
bool found = false;
while (i <= e)
{
if (dp[s][i] == 1)
... 阅读全帖 |
|
L******S
发帖数: 40 | 38 有个人在glassdoor上问了这个问题，但是没人回答
http://www.glassdoor.com/Interview/Given-a-2-31-x-2-31-tic-tac-
如果原题是这样的话，那就意味着保存数据的目的就是为了判断输赢，那就简单了
总共2^31行，也就是4G，每行用2 bit来记录这行有没有三连字，因为有四种情况，两
方都没有，两方都有，白方有，黑方有，总共要8G bits，然后列同理，也要8G bits，
剩下的就是两种对角线方向，每个需要16G bits，总共是16 + 16 + 8 + 8 = 48G bits
, 这个才6GBytes内存
我感觉这个题的描述太唬人了 |
|
|
m*****k
发帖数: 731 | 40 记下每行为1的indexes,
和另一行的indexes
求交，结果集>1即可。还是O(N^3), :( |
|
s******c
发帖数: 99 | 41 最后一步是multi-way merge，这时每一行已经是排好序的，分别取每行的第一个data
（最小），拿到内存里，所以是K个data在内存，只要k < x 就没有问题。整个merge过
程建一个heap,每次找到最小的元素，写到output里，同时最小的元素从哪一行来的，
就从那一行再取下一个元素，然后maintain这个heap，再找到最小的继续写到output。
最后直到这个heap空了为止 |
|
H**********5
发帖数: 2012 | 42 txt文档三行数据，想读到结构体中
yingduSB, 61 , 65, 43, 65, 54, 43, 65
sanjie.haojian, 91, 90, 80, 100, 89, 99, 88
sange.haoer, 98, 92, 80, 100, 89, 99, 88
while (NULL!=fgets(line,60,inputFile))
{
sscanf(line,"%20[^,],%[0-9^,],%[0-9^,],%[1-9^,],%[1-9^,],%[1-9^,
][^/n]",&stu[nIndex].name,
&stu[nIndex].quiz1,
&stu[nIndex].quiz2,
&stu[nIndex].quiz3,
&stu[nIndex].quiz4,
&stu[nIndex].midi);
//&... 阅读全帖 |
|
z**i
发帖数: 86 | 43 来自主题: JobHunting版 - FB 面筋 序列化这个问题比较有意思，我的想法
1）计算长度可能不够好，字符串可能很长，溢出可能。
2）增加offset格式位，增加存储负担。
3）可能最简单就是每行写一个字符串，最多多出"rn"2个char，且容易读取。
4）最优肯定是编码映射或者压缩方案，但要求两个字符串有特定性质。在无限制字符
串环境下，不是很合适。 |
|
a**********0
发帖数: 422 | 44 换句话说 根据某些输入 不一定可以做到同时left和right justify ： 每行只有一个
词 而这个词的长度比L小的时候 |
|
b*****c
发帖数: 1103 | 45 是每行每列分别有序，不是将matrix视作array的有序，
前者是sorted matrix的数学定义，后者是不知出处的定义 |
|
b*****c
发帖数: 1103 | 46 是每行每列分别有序，不是将matrix视作array的有序，
前者是sorted matrix的数学定义，后者是不知出处的定义 |
|
e****9
发帖数: 316 | 47 一个很大的日志文件
每行有两个field，第一个field是url, 第二个field是userid
最popular url的定义是最多unique user去点的链接。
比如两个链接，第一个只有一个用户点，点了一千次。
第二个链接十个用户点，每人点了一次。
这样第二个链接更popular.
想了想怎么都是一个n * m的复杂度。
有什么更高效的处理算法吗？ |
|
h*******e
发帖数: 1377 | 48 很多公司的code review标准不一样啊，据说g还有每行代码最大字符数的限制～～
这个面试要求这些，小公司代码标准比较loose的怎么办哦。 |
|
h*******e
发帖数: 1377 | 49 很多公司的code review标准不一样啊，据说g还有每行代码最大字符数的限制～～
这个面试要求这些，小公司代码标准比较loose的怎么办哦。 |
|
j*****8
发帖数: 3635 | 50 要求给出最优解法，但我想了半天也没进展。。
从A点传送字节去B点，求最短的传送时间。
input：
N: 最需传送的总字节数
L: 建立连接所需时间。 例如 L = 5s， 那么从A传一次到B建立连接所需时间为 2 * L
= 10s，传2次的话就需建立2次连接，那就是 2 * (2 * L) = 20s
B: 字节传送速率
C: block个数
接下来是C行，每行两个数 start, end 表示block里起始和中止位置。 例如： 2， 10
, 表示需要传送从位置2到9的字节，一共8个字节数
例子1：
input：
N = 2000,
L = 15,
B = 10;
C = 7;
0, 200
200, 400
400, 600
600, 800
800, 1000
1000, 2000
0, 1800
output: 340
这个例子里，因为建立连接时间过大。所以直接传送最大的两个block (0, 1800), (
1000, 2000) 所需时间最少，340
例子2：
N = 2000,
L = 5,
B = 10;
C = 7;
0, 200
200, 400
400, ... 阅读全帖 |
|
