H***e
发帖数: 476 | 1 有个超大文件，每行存一个string,要求去除重复，如果直接hash行string的话，放不
进内存
如果存 md5(string)做为 key 存进hashmap,有可能存下，但是有可能不同string重复
key,我在想，
我可以把hashmap 的value用来存此string在原文件中的行数，那么重复的时候，可以
去原文件，看一下，是不是真的重复
只是这样如果不能直接读某行string的话，sequential的读花费就太高了。 |
|
e***n
发帖数: 42 | 2 一个文件，每行一个单词，要求编程输出所有的 anagram，比如：
input:
abc
bac
asbd
sadb
output:
[abc, bac]
[asbd, sadb]
写了一个Java的，请帮忙高手帮忙看看有什么可以改进的：
import java.io.FileInputStream;
import java.io.IOException;
import java.util.*;
import java.util.Arrays;
public class FileReadTest {
public static void main(String[] aArgs) throws IOException {
String fileName = aArgs[0];
String word;
String anagram;
Map wTable = new HashMap();
// Read words from file
List text;
Scanner scanner = new Scanner(n... 阅读全帖 |
|
i**********e
发帖数: 1145 | 3 那个是指 extra space，就是最后一行字与字之间一个空格隔开就好了，左边对齐。后
面的空格 padding 还是需要的，确保达到每行的长度 == L 的条件。
is |
|
i**********e
发帖数: 1145 | 4 那个是指 extra space，就是最后一行字与字之间一个空格隔开就好了，左边对齐。后
面的空格 padding 还是需要的，确保达到每行的长度 == L 的条件。
is |
|
r******r
发帖数: 700 | 5 海量数据处理：十道面试题与十个海量数据处理方法总结
作者：July、youwang、yanxionglu。
时间：二零一一年三月二十六日
说明：本文分为俩部分，第一部分为10道海量数据处理的面试题，第二部分为10个海量
数据处理的方法总结。
本文之总结：教你如何迅速秒杀掉：99%的海量数据处理面试题。有任何问题，欢迎随
时交流、指正。
出处：http://blog.csdn.net/v_JULY_v。
------------------------------------------
第一部分、十道海量数据处理面试题
1、海量日志数据，提取出某日访问百度次数最多的那个IP。
首先是这一天，并且是访问百度的日志中的IP取出来，逐个写入到一个大文件中
。注意到IP是32位的，最多有个2^32个IP。同样可以采用映射的方法，比如模1000，把
整个大文件映射为1000个小文件，再找出每个小文中出现频率最大的IP（可以采用hash
_map进行频率统计，然后再找出频率最大的几个）及相应的频率。然后再在这1000个最
大的IP中，找出那个频率最大的IP，即为所求。
或者如下阐述（雪... 阅读全帖 |
|
r******r
发帖数: 700 | 6 海量数据处理：十道面试题与十个海量数据处理方法总结
作者：July、youwang、yanxionglu。
时间：二零一一年三月二十六日
说明：本文分为俩部分，第一部分为10道海量数据处理的面试题，第二部分为10个海量
数据处理的方法总结。
本文之总结：教你如何迅速秒杀掉：99%的海量数据处理面试题。有任何问题，欢迎随
时交流、指正。
出处：http://blog.csdn.net/v_JULY_v。
------------------------------------------
第一部分、十道海量数据处理面试题
1、海量日志数据，提取出某日访问百度次数最多的那个IP。
首先是这一天，并且是访问百度的日志中的IP取出来，逐个写入到一个大文件中
。注意到IP是32位的，最多有个2^32个IP。同样可以采用映射的方法，比如模1000，把
整个大文件映射为1000个小文件，再找出每个小文中出现频率最大的IP（可以采用hash
_map进行频率统计，然后再找出频率最大的几个）及相应的频率。然后再在这1000个最
大的IP中，找出那个频率最大的IP，即为所求。
或者如下阐述（雪... 阅读全帖 |
|
a**q
发帖数: 3 | 7 谢谢大家的回复！因为确实没有太多的经验，很多知识也是零散存放在大脑里的，对于
面试官的提问如果没有想到所有的情况，是很难组织出有效提问的。另外因为是面试，
面试官对于这种问题都希望得到一个迅速的回答，如果一个简单问题自己没有马上作答
也是会减分的。
设计题我只是大概写了一下，中途有一些交流我省略了没有写，比如面试官对题目有所
阐释，我自己也问了一些相关问题，根据后面的结果来看不一定有多到位。我只写了触
发面试官问下一个问题的一些步骤。B tree神马的我也说了，但是面试官并没有move
forward，显然不是他想要的答案。DHT怎么work我也简单说了一下，但是他问再详细的
我确实不知道怎么说了，因为没有implement过。这个面试官整个过程只问了我这一道
题，花了很多时间，在他走的时候我明显感觉得到他没有其他面试官走时那么高兴。
关于简单题bug的问题，我有一个bug是把 == null写成 != null了，笔误。。另外一个
bug是一个边界条件写错了的问题，不过也是马上纠正了。这是同一个面试官的。另外
还有一个被指出的bug是DP题最后反着trace回来打印忘记写i = a[... 阅读全帖 |
|
f**********2
发帖数: 2401 | 8 Onsite:
泛型，我理解简单说就是数据类型待定，以参数的形式来实例化。
factory pattern： 调用java中的工厂方法，通过传进来的参数，判断需要实例化的类
的方式。
“编程题是给一个棵树的节点增加一个next指针，指向同一层在他右边的那个节点，最右
边的节点的指向null” 这个是binary tree吗？如果是的话，访问parent，再访问
parent.right？
第二轮问什么是给N个FILE，每一个FILE每一行的第一个数字是time stamp，每个文件
里的每一行是按time stamp排好序的。让你把所有的文件merge成一个文件
merge有什么限制吗？如果没有，就依照每行的time stamp顺序归并到一个大文件里？
剩下的题目没读懂，lz再讲讲？ |
|
D********g
发帖数: 650 | 9 maintain 一个size为m的min heap (这里假定m < n), heap里每个元素初始化为每行第
一个数字以及每个数字对应的行号。
然后取heap root所在行的下一个数字，replace root，heapify. 如果root所在行run
out，change root value to some MAX value, then heapify.
如此重复K-1次。root就是第K大的数。比较tricky的case是当root所在row run out.需
要找到下一个最小的数，check 其所在row的下一个数，如果也run out，则继续找下去
，直到找到为止。
这么看来用balanced search tree应该更合适，klog(m)的复杂度。 |
|
p*******m
发帖数: 47 | 10 我5月初要去Twitter onsite，面的是 Trust & Safety team
2轮电面都比较简单，2个engineers都很nice.
但听说onsite 难度会明显加大, 而且我网上能搜到的它家的题目不多，特别是onsite,
所以心里没底，来版上求经验。
希望有面试经验的同学能和我分享, 如果不方便帖出来，你也可以我站内发信或者
email: d********[email protected]
这是recruiter给我的schedule:
11:30am 去公司签到, 然后面7个人, 其中有个 team Product Manager。每轮45min,
第1轮是 lunch interview,
7轮分别有coding, Ph.D. research presentation, large-scale system design (这
个是open question)
下面是我搜集到的Twitter的题目，有些版上有过了，给后来的同学作参考。
如果你们有新的题, 也可以回在下面.
希望版上它家的信息能多些
++++++++++++++++++++++++++++++++++++... 阅读全帖 |
|
f****0
发帖数: 151 | 11 给我的话，直接查一下每行的1的个数一不一样，不一样的话肯定是苹果
如果下面两种情况也算是苹果的话
(1)只有一个1
(2)
11
11
再作为特例判断一下就好了 |
|
a******m
发帖数: 1 | 12 来自主题: JobHunting版 - 请问一道题 文件里每行存了两个城市名字，写程序，求两个城市是否相连，比如
A, B
C, D
F, E
D, E
输入 C, E 输出 yes
输入 F, A 输出 No |
|
S*****e
发帖数: 229 | 13 Linkedin，data mining职位
1. 二位矩阵，行列都sorted，每行的第一个数小于前一行的最后一个数，给一个
target，判断其在不在矩阵内
2. 如果没有第二个条件，如何搜索
3. 如何使算法是log(m) + log(n)，log的底数是多少
4. data mining question，没听懂题目，自己也对这方面不熟，被鄙视，说简历上不
是写了data么。。
Epic，看网上恶评如潮，其实我对公司的印象还不错，不过工作过的人更有发言权
epic的面试比较非主流，首先是phone screening，主要是介绍自己之前的经验，背景
，gre,tofle，平时成绩。。。。然后是机考，数学题基本都能秒杀，然后是介绍一种
编程语言，做一些选择题，这个也基本没问题，第三部分是编程题，一共4道，都能在
glassdoor上找到吧，平时做过编程作业的基本就没问题了，一道题40分钟左右。然后
是做personality test，基本上就是看看你是什么样性格的人。
onsite包括role view，就是你跟一个员工聊天，问问题，估计是看看你这个人正常交
流有没有问题；pr... 阅读全帖 |
|
S*******e
发帖数: 379 | 14 linkedin这题如果没有第二个条件，也就是每行的第一个数小于前一行的最后一个数，
也能log(m)+log(n)吗？ |
|
S*****e
发帖数: 229 | 15 Linkedin，data mining职位
1. 二位矩阵，行列都sorted，每行的第一个数小于前一行的最后一个数，给一个
target，判断其在不在矩阵内
2. 如果没有第二个条件，如何搜索
3. 如何使算法是log(m) + log(n)，log的底数是多少
4. data mining question，没听懂题目，自己也对这方面不熟，被鄙视，说简历上不
是写了data么。。
Epic，看网上恶评如潮，其实我对公司的印象还不错，不过工作过的人更有发言权
epic的面试比较非主流，首先是phone screening，主要是介绍自己之前的经验，背景
，gre,tofle，平时成绩。。。。然后是机考，数学题基本都能秒杀，然后是介绍一种
编程语言，做一些选择题，这个也基本没问题，第三部分是编程题，一共4道，都能在
glassdoor上找到吧，平时做过编程作业的基本就没问题了，一道题40分钟左右。然后
是做personality test，基本上就是看看你是什么样性格的人。
onsite包括role view，就是你跟一个员工聊天，问问题，估计是看看你这个人正常交
流有没有问题；pr... 阅读全帖 |
|
z********n
发帖数: 6 | 16 有O(n2)的算法
leetcode上Largest Rectangle in Histogram这道题有O(n)的算法，对这个矩阵每行这
么计算一下就可以了。 |
|
|
j********x
发帖数: 2330 | 18 1 2 3 4 5 6 7
8 .....
...
...
...
43 44 45 46 47 48 49
每行为第一轮7次比赛中的一组，数字代表马完成比赛的时间
看看我这个输入，你的结果是啥 |
|
f*****m
发帖数: 75 | 19 尽量不写数字和字母 以防非我族人看得懂哈哈
小弟以前在国内是做测试的，到美国还是做测试，投简历的时候问能面开发的职位不。
被告知不行，看你背景挺适合做测试的，那就面测试师吧，擦。
两轮电面的题目不太记得了，是在谷歌在线文档上写的。有一个貌似是从一个字符串里
面把每个单词打印出来，每行一个。我写了大概几行脚本语言，用正则表达式把每个单
词抠出来。电话那头是个印度小伙儿，看到我的程序完全震惊了。看了半天，说这是他
看到的最好的答案。总的来说电面非常简单，一次只有一个程序题。其中一个人简直把
问题贴在文档里，所以即使你听不懂他的印度英语你也能看到题目。
后来他们的旅行社会联系你定机票啦酒店啦。我趁机把返程机票延后了几天，在加州可
以多玩几天。
总共是五轮面试。感觉基本没有时间讨论简历或者你之前做过什么东西，因为我之前做
的东西实在非常菜。也不想多说，所以如果别人问我简历上的东西，我准备了三十秒的
答案，两分钟的答案。
第一轮先聊一下怎么开始测试计划，中间需要做那几个步骤，然后给我一个会议室里的
电话讨论怎么测试。然后有大概一分钟的时间说我们做一个程序题吧：在西语言当中，
如果给定两个变量的值... 阅读全帖 |
|
t********3
发帖数: 567 | 20 我也来尝试一下全中文描述
第一个
题目比较通俗，给你一个二岔树的顺序遍历结果，还有前续遍历结果，把树还原出来
第二个
告诉我一个游戏，叫做“生／或者／死”，在一个棋盘上，规则如下：
每格有两种状态：生，或者 死
每一轮，如果有少于两个邻居是活着的，这格就死掉
如果刚好有两个邻居活着，这格保持原有状态
如果有三个邻居或者，这格可以重生，就是如果原来是死的，现在活过来了
如果有三个以上邻居，这格就被挤死了
要在白板上写每轮如何更新整个棋盘的状态
第三个
给一个矩阵，顺时针翻转九十度
第四个吃饭
第五个
问了给了一些数轴上的范围，要求把重合的部分合并掉
最后一个
原来打算问生或者死的那题，结果发现被人抢了，很无语，于是改问零散的数学问题
估计一下谷歌地球总共要多大的硬盘来存全球的地貌照片。
一个很大的文件（一个比连），有很多行，每行长短不一，如何随机抽取一百行。假设
你有一个六十四位的比特的随机数生成器。
各位内部人士走过路过就装做没看到吧 |
|
H****r
发帖数: 2801 | 21 谷歌地球总共要多大的硬盘来存全球的地貌照片？
Knuth shuffle 得知道总行数和每行的位置吧？还得记住哪些行已经选过了？ |
|
t********3
发帖数: 567 | 22 我也来尝试一下全中文描述
第一个
题目比较通俗，给你一个二岔树的顺序遍历结果，还有前续遍历结果，把树还原出来
第二个
告诉我一个游戏，叫做“生／或者／死”，在一个棋盘上，规则如下：
每格有两种状态：生，或者 死
每一轮，如果有少于两个邻居是活着的，这格就死掉
如果刚好有两个邻居活着，这格保持原有状态
如果有三个邻居或者，这格可以重生，就是如果原来是死的，现在活过来了
如果有三个以上邻居，这格就被挤死了
要在白板上写每轮如何更新整个棋盘的状态
第三个
给一个矩阵，顺时针翻转九十度
第四个吃饭
第五个
问了给了一些数轴上的范围，要求把重合的部分合并掉
最后一个
原来打算问生或者死的那题，结果发现被人抢了，很无语，于是改问零散的数学问题
估计一下谷歌地球总共要多大的硬盘来存全球的地貌照片。
一个很大的文件（一个比连），有很多行，每行长短不一，如何随机抽取一百行。假设
你有一个六十四位的比特的随机数生成器。
各位内部人士走过路过就装做没看到吧 |
|
a*******y
发帖数: 1040 | 23 两个排序好的数组，求和最小的M 个pair, 比如 A={1, 2, 4, 5, 6}, B={3, 5, 7, 9}
m=3 那么Results 就是(1, 3),(2, 3),(1, 5)
这个好像比较麻烦，很多solution都link到了一篇paper，实在没心情看，
结论是:
对于一个n×m(n≤m)的矩阵，若每行和每列都是递增的，则可以在O(nlog2m/n)找到第k
大的数。论
文题目为“Generalized Selection and Ranking: Sorted Matrices”
如果是查中位数：
先找出每一行（列）的中位数，再找出中位数的中位数，这样可以去掉接近一半的数，
再在剩
下的数里找中位数即可，复杂度O(N(logN)^2)
这个到底怎么个意思？ |
|
f*****e
发帖数: 2992 | 24 表述有点bug，sorry。
只要是k-regular的就会有perfect matching，一开始是(n-1)regular的，记为图1，后
来是(n-2),(n-3),...,1 regular的。只要保持图是k-regular的就有perfect matching
。
以4个点为例：
1 (2,3,4)
2 (1,3,4)
3 (1,2,4)
4 (1,2,3)
找到一个matching (i,j)=(1,2) (2,1) (3,4) (4,3)，然后在图1中删掉(j,i)得到
（j不能再和前面path里的点相连，也不能和自身相连，所以要删掉前面path里的点）
1 (3,4)
2 (3,4)
3 (1,2)
4 (1,2)
再找到一个matching (i,j)=(1,3) (2,4) (3,1) (4,2)，然后在图1中删掉前面path中
出现的点得到
matching:
1 2
2 1
3 4
4 3
然后把三个matching串在一起得到：
1-2-4-3
2-1-3-4
3-4-2-1
4-3-1-2
每行都是一个path。每一... 阅读全帖 |
|
f*****e
发帖数: 2992 | 25 来自主题: JobHunting版 - G家面试题 先用LP表示：
min sum_(ij)(w_ij*x_ij)
s.t. sum_i(x_ij)=1, sum_j(x_ij)=1, 0<=x_ij<=1
然后看能否转成combinatorial的问题。
minimum cost flow(algorithm design上有详细介绍)。
想到了，每行对应一个源s_i,每列对应一个汇t_j，
每个数组元素w_ij看成是一个node，与源s_i，汇t_j相连，
N个源s_i与总源s相连，N个汇t_j与总汇t相连，
边的cost是w_ij/2，capacity是1，其他边cost=0。 |
|
f*****e
发帖数: 2992 | 26 来自主题: JobHunting版 - G家面试题 先用LP表示：
min sum_(ij)(w_ij*x_ij)
s.t. sum_i(x_ij)=1, sum_j(x_ij)=1, 0<=x_ij<=1
然后看能否转成combinatorial的问题。
minimum cost flow(algorithm design上有详细介绍)。
想到了，每行对应一个源s_i,每列对应一个汇t_j，
每个数组元素w_ij看成是一个node，与源s_i，汇t_j相连，
N个源s_i与总源s相连，N个汇t_j与总汇t相连，
边的cost是w_ij/2，capacity是1，其他边cost=0。 |
|
s*****n
发帖数: 134 | 27 第一题就是一个用十字Kernal卷积的逆过程，最终的结果是需要检测的矩阵（m x n)，
输出是 (m-1 x n-1) 的矩阵。
我的笨方法是先用两层循环把每行和每列都转化成一个十进制的数，比如[1 2 1 5 4 3
2 1] 转化为 12154321, 如果这个数不能被 111整除，return false， 如果能整除，
把 Xi/111的结果再转化成一个行矢量Wi. 同理把 Yi/111的结果转化成列矢量 Vj。 把
Wi 和Vj 按行和列Cat成矩阵W 和V
如果第2到m-1行和2到n-1列都可以整除，就比较一下W 和V， 如果相同就return true。 |
|
S******1
发帖数: 269 | 28 前两天电面amazon，说来丢人，一面就挂了。去年还onsite过，可能真的和amazon没有
缘分吧。
题目都是本版的基础题，常见的口水题，自己也练过很多遍。题目都能打出来，但是有
bug。面试之前Collabedit上面练过，但是发现面试时候我编辑哪行哪行重影，模糊，
完全看不清我在写什么，鼠标的位置也是错乱的。只能凭着感觉写，切换到下一行后在
回头看上一行写的是什么。
面试官女烙印，没怎么刁难我，但是我听不懂她她听不懂我。面试时候和她说了我看不
清我写的什么，面完后还截屏让她看到我这里到底是什么情况，希望她能take into
consideration。因为紧张和软件的问题，题目出了bug，HashSet写成Hashset,一个特
殊情况的处理没有把结果加到return set里面。结果一面就挂了， 可能烙印还是在背
后没说什么好话吧。。。
题目：
1. 工作中遇到过最难得问题。
2. 给一个文件，里面有name，address, zip code,每行一个数据。格式什么的没问题
，都是comma separted， 问怎么列出来所有的zip code，结果不能有重复。 我说用... 阅读全帖 |
|
q****m
发帖数: 177 | 29 第二道题，每行一个数据，这个数据是类似这样吗？
Ping Li, Seattle WA, 12345
Jack Wang, Atlanta GA, 30123 |
|
S******1
发帖数: 269 | 30 对的，地址那一栏只是street name， 不会有数字。不过有电话和其他什么信息的，我
忘记了。
她说格式肯定不会有错乱的，所以应该就是取每行的最后五个数字，然后uniq |
|
t****u
发帖数: 709 | 31 2. 给一个文件，里面有name，address, zip code,每行一个数据。格式什么的没问题
，都是comma separted， 问怎么列出来所有的zip code，结果不能有重复
cat file|awk -F\, '{print $3}'|sort |uniq
就可以得到uniq的zip code了 |
|
l*********8
发帖数: 4642 | 32 Given: n by m matrix A,
k
定义
int low[n]; // low[i]是在第i行查找的下限
int high[n]; // high[i]是在第i行查找的上限
low数组初始为全0， high全部是m.
取一个pivot (比如第n/2行的第k/n个元素), 在每行的low[i]和high[i]元素范围中找
该pivot对应的upper boundary，存为pos[i].
num = sum( pos[i] - low[i] | for all i) 就是比pivot小的element的数目。
if (num == k-1) {
return pivot;
} else if (num > k-1) {
// 把high数组（查找上限）update为pos数组的值。
// 在新的low,high范围内递归查找k-th smallest element
} else { // num < k-1
// 把low数组（查找下限）update为pos数组的值。
// 在新的low,high范围内递归查找... 阅读全帖 |
|
l*********8
发帖数: 4642 | 33 如果在每行使用binary search，那么每轮更新是nlog(m).
但如果采用顺序查找，因为矩阵A在每列也是有序的，所以查找的下标在一轮中是不用
回头的。
例如：
假如pos[4]值为13,因为A[5][13] >= A[4][13]，所以pos[5]就从13开始递减搜索，
假如pos[5]值为8，因为A[6][8] >= A[5][8], 所以pos[6]就从8开始递减搜索。
....
查找下标最多移动m次，重复使用的下标值最多n次，所以是O(n+m).
当然，如果m相对n很大，可以用binary search, 这样nlog(m)的效率还是比 O(n+m)好
些。 |
|
h******8
发帖数: 278 | 34
diff is line by line.
diff是经常用，从来不知道是line by line， compare 的时候是line不要line
compare，每行是char by char？
那天还有一个人问kill（2） signal call是怎么implement，这种问题怎么真是没法准
备。 |
|
b****e
发帖数: 45 | 35 嗯，输出的时候比较麻烦，每行需要跟前一行比较，并且按照column order从左到右扫
描。从第一个不一样的column开始，分层逐个输出后面的所有column。 |
|
l*********8
发帖数: 4642 | 36 考虑一个比杨氏矩阵弱的情况A： 只要求矩阵每行有序，不要求每列也有序。
in-place 调整一个矩阵来满足条件A，可对每一行做quick-sort。
每一行时间是O(n*lgn), 有m行，所以总时间复杂度是O(m*n*lgn).
所以，我认为，对于要求更高的杨氏矩阵，不可能在O(m*n)time in-place调整完成。 |
|
d****n
发帖数: 56 | 37 第一题可以用差值绝对值放进maxheap来做吧，
第二题总行数和每行的元素数量是不是都要纪录更新啊 |
|
I*******l
发帖数: 161 | 38 之前打了两轮电话，做了轮PROJECT，感觉不错而且过了。昨天再打一次电话，面试官
是组的头。结果自己准备了整俩天的关于他们公式做的东西的各种概念和技术问题全没
用上，对方抓住简历里的一个PROJECT使劲问。。。
那是个关于计算VIX指数期货的模型（就是个类似于SP500的指数），数学公式复杂，很
久没看很多细节都忘了，但大致框架还是有的，跟他解释如何使用条件期望，他没弄懂
我的意思，执念于他的理解，结果就这个细节僵持了十分钟。跟着毫无悬念哥就被
THANK YOU FOR YOUR TIME了。
如果花时间好好看看这个PROJECT，结果可能不同吧。
不知道这次是否算个教训？简历里面列的东西没有必要是做过的最难的，重要的是能容
易讲清楚并让人理解的； 其次就是每个面试都得准备得很全面，从面试题集到各种概
念的总结到个人简历上的每行字，不能说跟对方做的东西毫不相干就不看了；
欢迎大虾们指正补充哦。
PS,找工作对于没经验的人来说还是很有难度的，相比较读书时候上课写作业轻松多了。 |
|
k***a
发帖数: 1199 | 39 csv每行记录节点string,和其孩子们所在的行
内存序列化到文件类似问题的关键就是怎么用文件来记录指针,指针其实就是个位置,对
csv文件来说行数就可以当指针
碰到这样的问题就是bonus
题。 |
|
s*******n
发帖数: 97 | 40 考虑简单一点
serialize: bfs 便利，每行第一个格存这个节点有多少个children，第二个格存节点
的内容
deserialize: 从第一行开始读文件line by line, 构造node 节点(包括内容和节点数)
，放到queue中。同时如果queue里面第一个node没满，那么当前的node就是它的一个
child。否则就是下一个node的children, if it is not full. |
|
f*********m
发帖数: 726 | 41 从“秒杀。。。”看来的，不解其意。
题目：非常大的文件，装不进内存。每行一个int类型数据，现在要你随机取100个数。
文章说“可以按照操作系统中的方法，先生成4G的地址表，在把这个表划分为小的4M的
小文件做个索引，二级索引。30位前十位表示第几个4M文件，后20位表示在这个4M文件
的第几个，等等，基于key value来设计存储，用key来建索引。”
是不是说这个4G的地址表每一个地址存放一个int？但int数目大于4G怎么办？另外，随
机数generator的范围是多少，是0~4G吗？还是要用generator好几次，每次对应不同的
位？
谢谢。 |
|
e****e
发帖数: 418 | 42 hashtable这里不好使吧, 原因好猫已经说了.
我觉得从小文件里建个tree.具体如下：
1. 对小文件里的每行的域名double reverse(老题...),
i.e. washington.usa -> usa.washington
2. 再建立prefix tree.
i.e (root)
|
|
usa
/ \
/ \
oregon washington
3. 遍历大文件里的域名, double reverse 之后和比较.
优化：
prefix tree只需要建立第一层就可以了. 至此，我觉得hashtable更好！
其实是个hashset,里面放小文件里域名反转之后的第一级域名.
i.e.
usa
china
canada
然后遍历大文件, 看hashset包含反转域名之后第一级域名.
i.e.
bjhmm.seattle.washington.usa --> usa.washin... 阅读全帖 |
|
e****e
发帖数: 418 | 43 我手头上没*nix有环境，我是根据grep文档, 链接已给出. 我以为grep是把小文件的所
有内容做为一个字符串，再查看大文件内容，看是否有匹配，如果有就返回匹配处所在
的行数.
你试验可以，那表明grep把小文件里每行都作为一个字符串,大文件里的任何一处和小
文件里的任何一行字符串匹配，就返回行号. 最后看大文件里所有的行号都返回了，就
是个全包含！ |
|
j*****y
发帖数: 1071 | 44 把每行的方向反方向一下
用 bfs starting from fn |
|
c*u
发帖数: 22 | 45 这样可以么:
每行key value存map
挨个遍历取value做key递归取到最后的就是value放set
最后输出set |
|
s*******r
发帖数: 2697 | 46 两轮 phone interview
第一轮
亚裔面试官，很nice，很详细问了当前project，问到许多细节的处理
算法题 reverse words in a string.
"It is good"--------->"good is It"
很简单，写完的时候有个bug，让我检查 发现了改了
然后又提示把reverse string的函数单独提出来
follow question问能不能处理 string 前后中许多空白
我说可以 他觉得不可以 我们一块走了一遍code 可以
结束了
第二轮
面试官烙印，交流有问题，至少两处都要求重复了两三遍才听懂
先一个一个的让介绍自己的project 大概20分钟 基本都是我在说
然后开始算法题
Q1
find longest palindrome in a string leetcode原题
解释思路，对每个character 从中间向两边扫 找最长的 他说ok
开始写 写到一半 考虑到偶数的情况，说还要考虑从中间两个character往两边扫
code，然后继续写 还没写完就被烙印打断 说u r on the right trac... 阅读全帖 |
|
s*******r
发帖数: 2697 | 47 两轮 phone interview
第一轮
亚裔面试官，很nice，很详细问了当前project，问到许多细节的处理
算法题 reverse words in a sentence.
"It is good"--------->"good is It"
很简单，写完的时候有个bug，让我检查 发现了改了
然后又提示把reverse string的函数单独提出来
follow question问能不能处理 string 前后中许多空白
我说可以 他觉得不可以 我们一块走了一遍code 可以
结束了
第二轮
面试官烙印，交流有问题，至少两处都要求重复了两三遍才听懂
先一个一个的让介绍自己的project 大概20分钟 基本都是我在说
然后开始算法题
Q1
find longest palindrome in a string leetcode原题
解释思路，对每个character 从中间向两边扫 找最长的 他说ok
开始写 写到一半 考虑到偶数的情况，说还要考虑从中间两个character往两边扫
code，然后继续写 还没写完就被烙印打断 说u r on the right tr... 阅读全帖 |
|
M********l
发帖数: 22 | 48 职位SDE
1. 印度女senior SDE manager: Matrix, 每列和每行都sorted好，找target number
（career cup 150上原题）
她当时很赶，说9点半要开会，安排的太匆忙，我当时没写完代码，说要面试之后把代
码发给她，不过idea我说清楚了
2.中国人：人很nice，问了两个简单的问题：
1.如何用1/3的随机数generator，生成1/7的随机数generator
2. 如何sort电话号码10 billion个， follow up，如果memory只有2mb怎么办
没让写代码，只说idea就行
3. 中国人，貌似是个group manager
因为我phd做的和data mining有关，他就问我知不知道kmeans算法，然后要求写代码实
现，代码我还是没写完。。。（我白板写代码能力还有待提高）
4. 印度男，面试+吃饭
貌似对我一开始印象不好，问了一个从数列中找和最大的子序列，也是150原题了，我
说完idea就去吃饭了
吃饭的时候一直不是很relax，因为他一直在问问题（之前看过很多onsite面经都说吃
饭不问问题的，弄得我... 阅读全帖 |
|
b***y
发帖数: 177 | 49 有的不止是scanf，比如要分行读，每行分别再分别按word读，这个stdin要是不熟，还
是很耗时间的。 |
|
f**********t
发帖数: 1001 | 50 我有一个M*N维的矩阵
希望找到一个m*n维的子矩阵使得其元素和最大
这个子矩阵的行和列不一定要连续
这个问题有好的解么？
就比如说，一个矩阵是3*3的
设每行每列的编号是(1, 1,) (1, 2), (1, 3)(2, 1,) (2, 2), (2, 3)(3, 1,) (3, 2)
, (3, 3)，则(1, 1)(1, 3)(3, 1)(3, 3)这四个点组成的也算是个子矩阵
目前有想法，但时间复杂度很大。感觉好像只有枚举法来做这个问题。不知大家有没有
更好的解法。 |
|
