E***n
发帖数: 166 | 1 假设矩阵是n * n的，
中数必然在从右上到左下的对角线上,所以找到这条对角线上的中数就行了，对角线上
一共有m+n个元素，时间复杂度O（n）
如果找到第k个元素，我的方法是先拿出每行的第一个元素，组成一个最小堆，然后不
断的extracMin,然后从对应的行再取下一个元素，放入最小堆中，Reheap。连续k次
extractMin可以得到k th element
最小堆有n个元素，这样需要k * log n时间
貌似通过DP有更好的方法，我忘了 |
|
b******n
发帖数: 4509 | 2
对新加入的 interval 范围再合并
用一个marker来分隔每行即可
rabin karp
先把多边形画出二维地图，之后就容易了 |
|
b*******8
发帖数: 37364 | 3 有人贴过O(MN)的算法，大意是对每行求直方图的最大面积O(N)，一共M行。 |
|
s***n
发帖数: 459 | 4 一个文件里n行m列，每行是一个record，每列一个feature，
你时不时要按不同feature排序和查找。不能用数据库，文件
大小内存能装下，数据结构和算法不限，语言不限，给出你
最好的办法。 |
|
d*******l
发帖数: 338 | 5 其实是对于每行，只累加从这一行开始向上连续的1，你的例子应该是
0 1 0 1 0
1 0 1 0 1
0 1 0 1 0
1 0 1 0 1
1 0 1 0 1 |
|
x******g
发帖数: 41 | 6 不能诶，不过我想了一下能不能这么解
0 1 0 1 0
0 1 1 1 1
1 1 0 0 1
0 1 0 0 1
1 1 0 0 1
1 1 1 1 1
-》每行统计连续上升的0，跟你刚才说的方法一样的话得到
1 0 1 0 1
2 0 0 0 0
0 0 1 1 0
1 0 2 2 0
0 0 3 3 0
0 0 0 0 0
如果是被1包围的，那它周围必定都是0，而且是个矩形
就变成直方图里面找个矩形，而且两侧都是0，比前面那个应该还简单一些
这么解可以么？ |
|
d*******l
发帖数: 338 | 7 你这个是求最大子矩阵的方法，这样确实没错，但0-1矩阵的最大全1矩阵确实是O(n^2)
的，对每一行用一次直方图方法即可，而每行的值可以在一次O(n^2)的预处理中全部得到
共O |
|
g**u
发帖数: 583 | 8 求祝福，刚面完Google第一轮。
电话面试没有NDA，所以把记得的题目记下来
太紧张了，发挥的很差。。。
Interviewer迟了3分钟， 没什么口音，估计是老美。面试一开始就上Google doc，
上来就要求写2个factorial的实现。
写了factorial的定义，马上写了个recursive的实现，说了边界检查，说了overflow，
然后开始写， 结果， 居然一急之下把base case给忘写了（哭死）。。。第二个写了
个iterative的实现，解释tail recursion可以马上改写成iterative的
接着是问一个非常大的文件里面有很多string，每行一个，问如何去重？ 说了hash和
sort的2种方法，比较了time and space complexity
接着是问了 set of strings, how to sort？问了memmory的限制，问了string的长度
分布，提出可以quick sort， 要求说明原理和时间空间复杂度，被追问还有其他方法
， 脑子犯傻，说了radix sort(大忌， 不要说自己不彻底清楚的东西)，说了基本原理... 阅读全帖 |
|
a**********2
发帖数: 340 | 9 两个文件A,B，每行存了一个sentence（可能会很长），文件B非常大
要你找出A里面每个sentence在B中出现的次数
我说用hash table，他就问我hash function怎么写，说这个句子可能很长
貌似他想要的是其他解法。 |
|
a*o
发帖数: 54 | 10 第一次的经验在 http://www.mitbbs.com/article_t0/JobHunting/31862241.html
又是早晨6点开始。5:58打开google doc，发现面试官比我还早，还在里面敲了很多字
，问我哪个电话号码合适之类。有了上次的经验，要求他们一定打到我电脑上，用耳麦
聊。过程很简单，先介绍他自己所在的组，然后聊了10分钟我的项目，他基本一直在听
，并且把要点直接记到了google doc里，问了一两个细节，解释清楚就开始做题。
一共两道，一个是给定很大的文件，每行一个id和value。问如何处理之后，把id和它
的平均值按range输出出来，比如均值在[0, 100)间的id有哪些。我问他这些id有多少
，被告知虽然文件size大，但id总数是manageable的。我就直接给了扫一遍文件，用
hashtable统计每个id的sum和count，最后把id按average value排序输出的解法。本来
以为他会再变变题目，需要把文件进行划分之类的方法，没想到就开始第二题了。
第二个就是按层次打印二叉树，同层的节点独占一行。也没什么特殊的，无非是标准的... 阅读全帖 |
|
g**e
发帖数: 6127 | 11 这是个特殊的young tabeleau，每行和每列之间的差是个定值。但是这个特殊属性不知
道怎么用。
这个题我关注了一年了，版上讨论过三五次，没见过谁能给出O(k)算法的 |
|
g*****k
发帖数: 623 | 12 不明白你说的，题目没说每行和每列之间是个定值。
那我不才，给出个想法，你看看是不是队的。
pair array1;
pair array2;
array1.first = 1;
array1.second = 2;
array2.first = 1;
array2.second =2;
size1 = m;
size2 = n;
res[0] = A[0]+B[0];
for (i=1; i
if (A[array1.first]+B[array1.second]<=B[array2.first]+A[array2.second]){
res[i] = A[array1.first]+B[array1.second;
if (array1.second = m - 1) {
array1.second = array2.first +1;
array1.first += 1;
}
else
array1.second+=1;
}
else {
... 阅读全帖 |
|
g***s
发帖数: 3811 | 13 "题目没说每行和每列之间是个定值"
the delta values of each line are same.
a1+b1 a1+b2 a1+b3.... a1+bn
a2+b1 a2+b2 a2+b3.... a2+bn
delta values are {b_i - b_i-1} |
|
g*****k
发帖数: 623 | 14 刚实验了一下，找到了个bug,现在修改了下，简单测试结果是对的，而且是O(K)复杂度。
不明白你说的，题目没说每行和每列之间是个定值。
那我不才，给出个想法，你看看是不是队的。
pair array1;
pair array2;
array1.first = 1;
array1.second = 2;
array2.first = 1;
array2.second =2;
size1 = m;
size2 = n;
res[0] = A[0]+B[0];
for (i=1; i
if (A[array1.first]+B[array1.second]<=B[array2.first]+A[array2.second]){
res[i] = A[array1.first]+B[array1.second;
if (array1.second = m - 1) {
array1.second = array2.first +1;
array1.first += 1;
}
... 阅读全帖 |
|
g**e
发帖数: 6127 | 15 这是个特殊的young tabeleau，每行和每列之间的差是个定值。但是这个特殊属性不知
道怎么用。
这个题我关注了一年了，版上讨论过三五次，没见过谁能给出O(k)算法的 |
|
g*****k
发帖数: 623 | 16 不明白你说的，题目没说每行和每列之间是个定值。
那我不才，给出个想法，你看看是不是队的。
pair array1;
pair array2;
array1.first = 1;
array1.second = 2;
array2.first = 1;
array2.second =2;
size1 = m;
size2 = n;
res[0] = A[0]+B[0];
for (i=1; i
if (A[array1.first]+B[array1.second]<=B[array2.first]+A[array2.second]){
res[i] = A[array1.first]+B[array1.second;
if (array1.second = m - 1) {
array1.second = array2.first +1;
array1.first += 1;
}
else
array1.second+=1;
}
else {
... 阅读全帖 |
|
g***s
发帖数: 3811 | 17 "题目没说每行和每列之间是个定值"
the delta values of each line are same.
a1+b1 a1+b2 a1+b3.... a1+bn
a2+b1 a2+b2 a2+b3.... a2+bn
delta values are {b_i - b_i-1} |
|
g*****k
发帖数: 623 | 18 刚实验了一下，找到了个bug,现在修改了下，简单测试结果是对的，而且是O(K)复杂度。
不明白你说的，题目没说每行和每列之间是个定值。
那我不才，给出个想法，你看看是不是队的。
pair array1;
pair array2;
array1.first = 1;
array1.second = 2;
array2.first = 1;
array2.second =2;
size1 = m;
size2 = n;
res[0] = A[0]+B[0];
for (i=1; i
if (A[array1.first]+B[array1.second]<=B[array2.first]+A[array2.second]){
res[i] = A[array1.first]+B[array1.second;
if (array1.second = m - 1) {
array1.second = array2.first +1;
array1.first += 1;
}
... 阅读全帖 |
|
h*********n
发帖数: 11319 | 19 还是没搞懂这个中点是什么意思
是说每行，每列都是个偏序集，给出的数列不能违反其中的顺序？
1- |
|
c*****t
发帖数: 13 | 20 本人CS硕士名校非牛人,一年前去了一家中型软件公司做SD,不喜欢,刚刚跳去一家小HF.面试
的过程好像西游记一样,路途遥遥,艰险不断,怪物层出不穷,自己的本领也日渐增长,2年来承蒙
版上各路豪杰照顾分享,今日也算有个结果;特此拿出小弟所见所闻共勉,纪念找工作的艰辛,愿
大家早日心想试成,取到真经!
/***********************
小测验
***********************/
首先来个小测验,看你能看懂多少
1.array,list,BST,Hashtable,queue,stack,suffix tree,collection...
2.BFS,DFS,DP,D&C,Greedy,Dijkstra,tree traversal,recursion,quick
sort...
3.A,F,G,L,M,O,T,Y...
4.OOP,GC,Polymorphism,interface,abstract class,singleton...
5.bar raiser,white board programming,lunch interview..... 阅读全帖 |
|
a*****a
发帖数: 46 | 21 boggle puzzle那道题能详细说一下么？是每行/列/斜线组成一个词 还是 整个表组一
个词？ |
|
h*****g
发帖数: 312 | 22 zz:
原文：
http://blog.csdn.net/njnu_mjn/archive/2010/04/04/5449098.aspx
八皇后问题(C++) 收藏
1 、问题描述： 在一个8*8 的棋盘上放置8 个皇后，不允许任何两个皇后在棋盘的同
一行、同一列和同一对角线上。
2 、关键字： 递归、上溯
3 、技巧：
1 ）、
经观察发现，对8 x 8 的二维数组上的某点a[i][j](0<=i,j<=7)
其主对角线（即左上至右下）上的每个点的i-j+7 的值（范围在(0,14) ）均相等；
其从对角线（即右上至左下）上的每个点的i+j 的值（范围在(0,14) ）均相等；
且每个主对角线之间的i-j+7 的值均不同，每个从对角线之间的i-j+7 的值亦不同；
如a[3][4]:
主：3-4+7=6
从：3+4=7
因此可设两个数组b[15],c[15] 分别表示主、从对角线是否安全
（为1 表示有皇后，不安全；为0 表示安全）
2 ）、
每行有且仅有一个皇后：
每i 个皇后放在每i 行(0<=i<=7)
void eightQueens( int line );
4 、源码（... 阅读全帖 |
|
G******i
发帖数: 5226 | 23 ☆─────────────────────────────────────☆
currant (葡萄干) 于 駡 提到:
/***********************
小测验
***********************/
首先来个小测验,看你能看懂多少
1.array,list,BST,Hashtable,queue,stack,suffix tree,collection...
2.BFS,DFS,DP,D&C,Greedy,Dijkstra,tree traversal,recursion,quick
sort...
3.A,F,G,L,M,O,T,Y...
4.OOP,GC,Polymorphism,interface,abstract class,singleton...
5.bar raiser,white board programming,lunch interview...
如果以上任何概念不能熟练给出详细解答,请在往下面看之后抓紧复习1.数据结构(这个如果一
个没看懂可以按后退关窗口了)2.算法3.公司背景4.面向对象编程5.on... 阅读全帖 |
|
r******n
发帖数: 170 | 24 我随便说说，看是否有大牛出来吧
1. format存成file或者db table,存的内容基本就是user id(unique)的friend关系，
比如file每行 1 2就表示user1和user2是friend
2.file存在io问题，interface上得自己重新建立datastructure来提供常见的function
,同时这也是优势，更灵活，有完全控制权；可以像读triangle mesh一样读进来，然后
建立mesh；db通常有先有工具，只需考虑table schema的设计，有index等手段优化
search等功能；db易于数据同步，备份，建立db cluster, load balance等常见手段
3. 两个数组按照user id升序排列，找相同id,O(m+n)遍历，可以找完
4. tableName:Connection, 两个column friendStart, friendEnd,都用来存放userId,
两个column都是index
select distinct friend from (
select friendEnd from Conn... 阅读全帖 |
|
s*********b
发帖数: 815 | 25 貌似是两个常见算法的组合：word wrapping，和text justification。决定在哪里断
行用word wrapping算法，决定怎么让前后不出现空格，用text justification算法。
我没有想通的地方是，这俩算法放在一起未必总是可行啊？比如说一行的最大宽度L=6
，而字符串是"The ox is running”. 那你不管是按照Word的贪心算法：
The ox
is
running
还是Knuth and Plass:
The
ox is
running
如果不允许破折号且词与词间空格数不超过2的话，都做不到后面没有空格啊？还是面
试官的意思是说每行长度不用凑足L个字符？ |
|
B*********e
发帖数: 9 | 26 要按顺序打印，
我觉得面试官是说不用考虑词比L大的情况，应该是每行至少可以打两个词，当然我也
没有问。
最后一行的问题我也没有问。太菜了
6 |
|
w********h
发帖数: 48 | 27 ① 设计一个类来保存一些整数，提供两个接口：增加一个整数、获取中位数。提供
不同的实现分别优化这两个接口。
② 反转链表。分别用递归和循环实现。
③ 面向对象设计：在线二十一点游戏
④ 分层打印一个二叉树，每层格式自由
⑤ 在一个整数序列中寻找一个和最大的连续子序列。（空序列是非法输入输出）
⑥ 面向对象设计：类Unix文件系统
⑦ 两个数组A1、A2，长度分别为L1、L1+L2。A1和A2的前L2个元素均已分别排序好
。请合并A1和A2的前L2个元素到A2中。
⑧ 一个文本文件，每行有三列：shipment ID, UPC code, quantity，写Unix
shell命令输出quantity最大的十行。
⑨ 实现atoi函数。请考虑各种可能情况及如何错误处理。
⑩ 排序后旋转的数组内查询元素
⑪ 判断一个二叉树是否是二叉排序树。
⑫ 现在是周三，你有一个系统计划下周一交付运营。另外一个组告诉你系统
依赖的web service原计划本周一交付，但他们在忙于其它项目，不得不推迟两到三... 阅读全帖 |
|
k****n
发帖数: 369 | 28 hit words太open了，实在讲不清楚
可以看看modern information retrieval以及introduction to information
retrieval之类的书
按我理解，应该是对Search Engine的基本数据的重复利用什么的
sudoku就是把每行每列每个正方形都单独存一份，所以一共有
int rows[9][9]
int cols[9][9]
int squares[9][9]
这样，更新就更新三次，取数随便从哪个取当然都行
关键是他要求的判断是否合法的操作，就对27个int[9]做同样的判断就行了 |
|
g*****i
发帖数: 2162 | 29 先谢谢了
1. 算POLYNOMIAL，比如5x^4+6x^3-7x^2-8=?
原文说思路是减少乘法变成x^2(x(5x+6)-7)-8, 然后找数据结构存数字和运算符.
我的问题是什么数据结构呢?是否要存prefix notation?
2.给你三个烤箱，每个烤箱可以同时烤两片面包，需要的时间分别是3分钟，4分钟和3
分钟。但第三个烤箱有一个slot出了点问题，每次只能烤面包的一面。所以这个烤箱三
分钟后只能算烤好一片半面包，你需要把那半片翻个面，在同一个slot里再烤一次才算
一片完整的。现在给你这三个烤箱，问烤好21片面包最少需要多少时间？如果是2100片
呢？如果是任意给定的N片，要求O(1)时间内给出最少需要的时间。
我的思路:12分钟正好20片没浪费,1-19事先算好存在array里.对吗?
3. read n lines of random numbers(space as delimiter) from a file, lines
with same numbers are treated as duplicated lines, regardless of the ... 阅读全帖 |
|
k*j
发帖数: 153 | 30 某刚上市公司onsite。已经被拒了。奉献面经攒rp.
1。hosting manager来介绍他们的项目。no technical question，但这个时候应该多
讨论，刚看一本面试书说应该listen和ask questions的时间一半一半。我当时见缝插
针问了几个问题，别人就很开心，说good question之类的。不知道这轮对最后评分有
没有影响。建议去之前先了解他们的产品。
2。给一个string,老pattern换成新pattern。不用in place。感觉不太考算法，但要注
重coding细节。特殊input之类的要考虑好。第二题是长string output成每行K个字符
的题。这题考思路。
3。most interesting project
4。 open question,如何改进他们产品，可以用什么算法
5。讲research，之前用过什么算法云云（半小时）。然后编程，如何对稀疏矩阵求dot
plot。写class。他是想用linkedlist来存储pair。而不是用vector来存。
6。 如何判断2个linkedlist相交，在哪相交。编程之美上有... 阅读全帖 |
|
P**********c
发帖数: 3417 | 31 看来L公司很喜欢考那个长string output成每行K个。这个上次大家讨论有最终的标准
答案吗？ |
|
h*********n
发帖数: 915 | 32 长string output成每行K个字符
这题啥意思啊？ |
|
h*********n
发帖数: 915 | 33 发信人: kxj (kxj), 信区: JobHunting
标 题: 新鲜面经
发信站: BBS 未名空间站 (Thu Aug 25 19:41:31 2011, 美东)
某刚上市公司onsite。已被拒.
1。hosting manager介绍项目。这时应多讨论。我见缝插针问了几个问题，别人就很开
心，说good question。建议去之前先了解他们的产品。
2。给一个string,老pattern换成新pattern。不用in place。不太考算法，但要注重
coding细节。特殊input之类的要考虑好。第二题是长string output成每行K个字符的
题。这题考思路。 |
|
B*******1
发帖数: 2454 | 34 1. A = {4, 10, 15, 20}
B = {1, 13, 29}
C = {5, 14, 28}
１． 每行取一个，排序，|a-b| + |b-c| + |c-a| ＝２*(max-min),更新全局最小的值
2. 扔掉ｍｉｎ，从拿ｍｉｎ那组数里面拿一个，跳到１执行，
如此反复执行，直到有一行所有数拿光了
用以上例子运行如下
１．｛４，１，５} -> {1,4,5} -> answer = 2 *(5-1) = 8
2. 扔掉１，拿１３ {4,5,13}-> answer = 2 *(13-4) = 18
3.扔掉４，拿１０，{5,10,13} -> answer = 2 *(13-5) = 16;
4．扔掉 ５拿１４ {10,13,14} -> answer = 2*(14-10) = 8
5. 扔掉１０ 拿１５，｛１３，１，４，１５｝-> answer = 2*(15-13) = 4
6.扔掉１３，拿２９ {14,15,29} -> answer = 2*(29-14) = 30
7. 扔掉 １４拿２８ {15,28,29} -> answer = 2*(29-15... 阅读全帖 |
|
r******n
发帖数: 170 | 35 自己考古了一下，版上似乎讨论过，似乎没有结果？还是我没找到
给你一个很长的string list，让你分行打印。然后告诉你一行只能写L（比如
25）个字符，而且首位和末尾不能是空格，空格只能在中间，两个词中间可以空两个或
者格子。 |
|
y*******g
发帖数: 6599 | 36 就是贪心，放入最多的word，如果还有多余的space随机分配到已有空格中 |
|
|
|
H*M
发帖数: 1268 | 39 为啥是minheap? 是max 吧。保持每行最大值在里面 ，每次pop出的都是最大的 |
|
H*M
发帖数: 1268 | 40 为啥是minheap? 是max 吧。保持每行最大值在里面 ，每次pop出的都是最大的 |
|
h****n
发帖数: 1093 | 41 Technical questions:
1. 一堆有限个整数及其出现的概率之间的函数关系是p=2的(-x)次方，设计一种最优熵
编码。如果p=e的(-x)次方呢？
不懂
2. 给你millions of random bit generators,每个generator产生bit 0 或者1，概率
不定，如何设计一个32-bit整数的generator，使得产生的整数的概率分布式平均分布？
平均分布的话如楼上的办法，要是正太分布的话可以用中心极限定理
3. 有一batch printer jobs with priorities. 每个job的priority是high, medium
或者low之一，设计算法使得printer按照priority从高到低打印所有jobs
最大堆的实现吧
4. write a function to check Sudoku的解是valid的
老题，每行，每列，每个小九格子check，采用数组哈希
5. 为什么destructor必须是virtual的？
保证子类使用自己的destructor来释放资源 |
|
i*******6
发帖数: 107 | 42 很好玩的，这个面试的人估计自己都没准备好，打电话说你稍等一下，我找一下面试题
的文档，咦到哪儿去了？...然后敲了1分钟鼠标...
题目很简单，doc上写代码：
1.很大的文件里面若干行，每行一个字符串，去重复，保留第一次出现顺序
2.比如aabbbbccccccdde这么个排好序的字符串，输入c，输出c出现的次数6 |
|
d******p
发帖数: 335 | 43 一共两次电面一次onsite
电面1. 印度人：
1. research相关问题
2. 给一个巨大的文件(>10GB)，每一行都是一个数字，怎么sort。只要答到external
sort就可以了
3. 一个概率题，具体记不清了，大概的意思是有红色和蓝色球，如果拿到红色，那么
放回，如果拿到蓝色，再拿下一个，根据下一个的花色来判断是否放回。问：拿到就剩
最后一个球是红色的概率是多少
电面2. 欧洲人：
1. research相关
2. 和twitter很相关的一个问题，根据twitter的follow关系，如何efficiently找到所
有的connected components。有一个很大的文件，每行存一条follow关系的边。基本上
达到hash就差不多对了。会不断问细节，然后如何改进。这轮面的很好。
onsite记得的题目如下：
1. 国人大哥
twitter怎么做fraud detection，怎么根据tweet做clustering，问了一些IR的问题
2. 南美人
自己最满意的项目是什么，又按照简历问了一些问题
怎么找hot的tag（就是#tag这种）
3. 白人
1
... 阅读全帖 |
|
d******p
发帖数: 335 | 44 一共两次电面一次onsite
电面1. 印度人：
1. research相关问题
2. 给一个巨大的文件(>10GB)，每一行都是一个数字，怎么sort。只要答到external
sort就可以了
3. 一个概率题，具体记不清了，大概的意思是有红色和蓝色球，如果拿到红色，那么
放回，如果拿到蓝色，再拿下一个，根据下一个的花色来判断是否放回。问：拿到就剩
最后一个球是红色的概率是多少
电面2. 欧洲人：
1. research相关
2. 和twitter很相关的一个问题，根据twitter的follow关系，如何efficiently找到所
有的connected components。有一个很大的文件，每行存一条follow关系的边。基本上
达到hash就差不多对了。会不断问细节，然后如何改进。这轮面的很好。
onsite记得的题目如下：
1. 国人大哥
twitter怎么做fraud detection，怎么根据tweet做clustering，问了一些IR的问题
2. 南美人
自己最满意的项目是什么，又按照简历问了一些问题
怎么找hot的tag（就是#tag这种）
3. 白人
1
... 阅读全帖 |
|
w****x
发帖数: 2483 | 45 "和twitter很相关的一个问题，根据twitter的follow关系，如何efficiently找到所
有的connected components。有一个很大的文件，每行存一条follow关系的边。"
struct EDGE
{
int x;
int y;
EDGE(int a, int b) : x(a), y(b) {}
};
void _inner_find_comp(int x, hash_map>& mp, set& st,
vector& vecComp);
void _insert_conn(int x, int y, hash_map>& mp);
void GetConnectedComp(vector& edges, vector>& comps)
{
hash_map> mp;
for (vector::iterator it = edges.begin(); it !... 阅读全帖 |
|
w****x
发帖数: 2483 | 46 "和twitter很相关的一个问题，根据twitter的follow关系，如何efficiently找到所
有的connected components。有一个很大的文件，每行存一条follow关系的边。"
struct EDGE
{
int x;
int y;
EDGE(int a, int b) : x(a), y(b) {}
};
void _inner_find_comp(int x, hash_map>& mp, set& st,
vector& vecComp);
void _insert_conn(int x, int y, hash_map>& mp);
void GetConnectedComp(vector& edges, vector>& comps)
{
hash_map> mp;
for (vector::iterator it = edges.begin(); it !... 阅读全帖 |
|
e******o
发帖数: 757 | 47 随能解释一下这个题目么？ 什么叫 “找到所有的connected component"? 比较土，没
用过twitter. thanks
2. 和twitter很相关的一个问题，根据twitter的follow关系，如何efficiently找到所
有的connected components。有一个很大的文件，每行存一条follow关系的边。基本上
达到hash就差不多对了。会不断问细节，然后如何改进。这轮面的很好。 |
|
f*********m
发帖数: 726 | 48 下面三题的想法：
（1）2. 和twitter很相关的一个问题，根据twitter的follow关系，如何efficiently
找到所
有的connected components。有一个很大的文件，每行存一条follow关系的边。基本上
达到hash就差不多对了。会不断问细节，然后如何改进。这轮面的很好。
想法：
通过follow关系给每个用户建立adjacent list，其中存放其followers。这样我们得到
一个graph.然后用bfs 或dfs找出和一个给定用户连接的节点（用户）。
(2) 5. team lead
悲剧就悲剧在他身上了，问了一个电面一样的问题，我说问过了，换一个吧，然后就换
了一个，结果答的比较烂：
给一组tweet的inverted index，怎么找一个phrase（多个词）的最短组合，比如找
phrase "twitter good tool", twitter is a good tool就比twitter is good,
facebook is a better tool距离近
想法：
计算tweet和candidate phrase的“距... 阅读全帖 |
|
e******o
发帖数: 757 | 49 随能解释一下这个题目么？ 什么叫 “找到所有的connected component"? 比较土，没
用过twitter. thanks
2. 和twitter很相关的一个问题，根据twitter的follow关系，如何efficiently找到所
有的connected components。有一个很大的文件，每行存一条follow关系的边。基本上
达到hash就差不多对了。会不断问细节，然后如何改进。这轮面的很好。 |
|
f*********m
发帖数: 726 | 50 下面三题的想法：
（1）2. 和twitter很相关的一个问题，根据twitter的follow关系，如何efficiently
找到所
有的connected components。有一个很大的文件，每行存一条follow关系的边。基本上
达到hash就差不多对了。会不断问细节，然后如何改进。这轮面的很好。
想法：
通过follow关系给每个用户建立adjacent list，其中存放其followers。这样我们得到
一个graph.然后用bfs 或dfs找出和一个给定用户连接的节点（用户）。
(2) 5. team lead
悲剧就悲剧在他身上了，问了一个电面一样的问题，我说问过了，换一个吧，然后就换
了一个，结果答的比较烂：
给一组tweet的inverted index，怎么找一个phrase（多个词）的最短组合，比如找
phrase "twitter good tool", twitter is a good tool就比twitter is good,
facebook is a better tool距离近
想法：
计算tweet和candidate phrase的“距... 阅读全帖 |
|
