g*******y
发帖数: 1930 | 1 怪mitbbs了，显示不了tab缩进，每行都变成左对齐了。。。呵呵
while(k)就是单独的一句话(单独的一个loop),跟下面两个for loops没关系。
while(k)的作用，只是要计算一个等于或者约大于N的2的整次方数。
其实我完全也可以把while(k)改写成：
k = 1 << (Log2(N-1)+1);
至于你说的2,3,4要O(N^2)是不对的，整个j loop做完，也就是O(N).
所以最后复杂度就是 log(k) * O(N) = O(NlogN)
这个本质上就是一个divide-conquer的非递归实现，复杂度当然不会有变化。 |
|
h*********i
发帖数: 2605 | 2 我记得以前有人讨论过。一种方法是merge sort, maintain a heap，用时O(n^2logn)
，还有更快的方法么？ |
|
|
k*k
发帖数: 49 | 4 Constructing Young's Tableau does not offer too much benefit on sorting...
for n^2 numbers, the lower bound for comparison-based sorting is
2 n^2 log n (or N log N if N == n^2)
given each row/col is sorted, sorting will take in O(N^1.5) N * sqrt(N);
N for total numbers, sqrt(N)=n for complexity to extract min from remaining matrix.
N*sqrt(N) > N log N ...
so i guess it is better just sort it directly. |
|
h*********i
发帖数: 2605 | 5 一共n*n个数字，怎么可能O(N)时间完成呢。
假设你说的是O(n^2)，虽然行列都sort好了，但是：
a1 a2
b1 b2
我们还是不知道b1和a2的相对大小
所以每次要从n行里找出最大的（用heap），用O(logn)时间。所以总共应该是O(n^
2logn)。
remaining matrix. |
|
h*********i
发帖数: 2605 | 6 发现你刚才修改过了。
我也觉得O(NlogN)是最快的。
remaining matrix. |
|
k*k
发帖数: 49 | 7 yes... but with additional space for min-heap
considering the complexity of constructing such a table in addition to the n
^2 log n sorting complexity...
young's table is really not a good way to tackle sorting problem.... |
|
H*M
发帖数: 1268 | 8 咋办?
我已经完全没有fancy格式了,上传之后还是乱了,关键是回车的地方会mess掉.
谁能给讲下怎么弄啊?
每行最多多少字符一般上传后就没有问题了?
多谢多谢... |
|
H*M
发帖数: 1268 | 9 职业杯上的题是这样的:
Imagine you have a square matrix, where each cell is filled with either blac
k or white. Design an algorithm to find the maximum subsquare such that all
four borders are filled with black pixels.
不过按他的算法,我觉得是O(n^4)而不是O(n^2):
1. iterate each full column ->n
2. iterate each sub column -> n^2
3. check if it can form a sqaure ->n
total O(n^4)
第三步可以用2n个interval tree记录每行每列的连续0的起始index,这样第三步就省到
lgn,总共可以O(n^3.lgn). |
|
H*M
发帖数: 1268 | 10 讨论讨论
You have a file with millions of lines of data. Only two lines are identical
; the rest are all unique. Each line is so long that it may not even fit in
memory. What is the most efficient solution for finding the identical lines?
这个连每行都不能放进内存里。有什么好方法吗？ |
|
r**u
发帖数: 1567 | 11 这个可以reduce成find max rectangle in柱状图。考古一下。Another hint: 先找到
每行的连续序列。
e.g., convert 1 0 1 1 1 0 --> 1 0 1 2 3 0. |
|
|
m******2
发帖数: 252 | 13 同意，
具体点就是：
先保存第一行，
读到第二行时，1/2概率此行被保存，1/2保留原来的不变
。。
在读第n行，有1/n的概率此行被保存， （n-1）/n概率不变
这样算下来，每行都有1/n概率被保存 |
|
|
r****o
发帖数: 1950 | 15
明白了，就是在这里实现了在每行末尾加个NULL，对把。 |
|
i****h
发帖数: 321 | 16 25匹马的问题。
输入int，返回char*，每三位加一个逗号。
一个文件，每行有一个单词，如何返回只出现一次的单词。
然后随便扯了一点简历。
我觉得这样的问题就没有必要讨论了吧。关键每个问题结束后都得到了肯定答复。我不
知道该怎
么办了。 |
|
z****x
发帖数: 57 | 17 从板上看了不少题目，回馈本版。
故意不写英文，尽量用中文了，大家将就读。
上来就聊聊我的论文做啥，让我说给他听听。这个东西能在该公司
如何应用。
十分钟后开始做题：
1. 一个文件，里面一行一行的字符，会有重复的行，问怎么去重。
我就问文件能否装在内存里，他说那先讨论能放在内存的情况。
我就先说装载到内存，排序，然后一遍扫描去重。
然后他说，要维持原来的顺序，我就说用哈希表，之后他
要求写代码。写完之后，再问改进，我说不需要用每行文字做键值，
只需要拿哈希值做键值。之后再问，内存放不下怎么办，我说分段
处理，每段处理完之后保存到新文件，之后再拿新文件来去重。
类似external sort的思想。
2. 某机器发现可用内存越来越少，问可能什么情况。
内存泄漏了。说C和C++里面什么情况下会内存泄漏，分配之后没有
释放、或者有异常抛出。问有什么解决办法。说用商业软件来检测，
注意new/delete或者malloc/free的使用，使用shared_ptr或者
auto_ptr等等
3. 经典题，一个数组，再给一个目标值，找出数组里面两个数字的
和等于这个目标值。写代码，O(n)和O(n |
|
y**i
发帖数: 1112 | 18 就是不知道文件行数，只能读取一次，按行读取，怎样读取让取到每行的概率相等
原帖版面搜吧 |
|
p********7
发帖数: 549 | 19 我觉得这个办法很好，histogram做一次O（N）每行都做O（M＊N） |
|
|
S******a
发帖数: 862 | 21 这道题我觉得就是看看编程基本功，把程序写对就行。
我onsite还碰到过找出数组里最大的数，汗。。
具体来讲，思路就用bitmap
以下是以前的讨论：
======================================================
则：
======================================================
非常感谢你的回答！
我觉得用一个a[9]，然后扫描三次，每行，每列，每block。你的虽然扫描一次，但每
个元素要跟多个不同的a[9]比较，总的比较次数应该和我说的一样，但我说的用的a[9]
少一些。你觉得呢？我是不是哪里理解不对？
========================================================
======================================================== |
|
s*****t
发帖数: 19 | 22 连接的两个面试，每个45分钟，感觉题目都很不典型，与在版上看到的不太一样。
面试官1
1、 有多个large size file，file里每行存一string，问用啥方法将这些文件包含的
string都列出来（去掉重复的）。 我回答可以用unix自带的一些命令，比如先sort
再unique。。 然后又支支吾吾说这样速度也许可以用hashtable记录，但是他觉得空间
是个问题，实际上一般情况下大家也就用Unix命令搞定这些事情。
2、如何用最少的空间记录25条Y/N的信息，ii) 如何修改第N条信息。我回答，用单个
int
32bit表示，用位操作如&, | 等。
3、java 中interface 和abstract class的区别
4、列一些你熟悉的数据结构。 （我列了数组，单向双向链表，树，图，等等
5、一般如何表示一个图？ 需要提供一些什么操作？
6、coding 描述了他们的一个page ranking的算法，（由于有点紧张，导致基本不理解
算法），page 和page 形成一个图， 给段代码，修改每个page的score。这题因为一开
始没理解算法，所以时间在 |
|
q*********u
发帖数: 280 | 23 好像最近都是back2back的电话，强度很大阿，除了1，你的答案应该都很赞，
顺便问一下，你的page rank用的是二维数组吗，时间这么短就要code page rank,
如果不是事先就对路准备上很难阿
连接的两个面试，每个45分钟，感觉题目都很不典型，与在版上看到的不太一样。
面试官1
1、 有多个large size file，file里每行存一string，问用啥方法将这些文件包含的
string都列出来（去掉重复的）。 我回答可以用unix自带的一些命令，比如先sort
再unique。。 然后又支支吾吾说这样速度也许可以用hashtable记录，但是他觉得空间
是个问题，实际上一般情况下大家也就用Unix命令搞定这些事情。
2、如何用最少的空间记录25条Y/N的信息，ii) 如何修改第N条信息。我回答，用单个
int
32bit表示，用位操作如&, | 等。
3、java 中interface 和abstract class的区别
4、列一些你熟悉的数据结构。 （我列了数组，单向双向链表，树，图，等等
5、一般如何表示一个图？ 需要提供一些什么操作？
6、co |
|
s********l
发帖数: 998 | 24 我想问一下
你这个young tableau 是说这个样子的？
1 2 4 7 8
3 5 6 9
10
还是说就是个m*n的 每行和每列都是递增的矩阵？
case |
|
j**l
发帖数: 2911 | 25 原题是这样的，数组A和数组B的长度都是n, 且都严格单调递增，取A中一个元素和B中
一个元素组成一个pair，共有n^2个pair。每个pair对两个元素求和，找出和最小的n个
pair。这道题有O(n)的算法么？
这道题实际上是可以转换成Young Tableau的，定义C[i][j] = A[i] + B[j], 则矩阵C
的每行每列都是严格升序排列的，所以C是一个Young Tableau
虽然C让问题看去很直观，但大小为n x n的Young Tableau是做不到O(n)时间取得最小n
个元素的吧？或许原题可以转换为这个新问题，但能找到一个更巧妙的方法，其复杂度
小于这个新问题? 也就是原问题和新问题，不是等价的。 |
|
r****o
发帖数: 1950 | 26 问一下，Young Tableau是怎么定义的？是不是每行每列都顺序递增就是Young Tableau?
C
小n |
|
j**l
发帖数: 2911 | 27 是的，这个Young Tableau比较特殊，也就是说每行的差量是一样的，每列的差量也是
一样的 |
|
a*s
发帖数: 425 | 28 这个问题，我可以想到的最有效的方法是
先找最小的pair,
比如
A=[1,2,3,4]
B=[5,6,7,8]
然后最小的肯定是A 和 B的第一个元素相加，
然后，就相当于
找
A1=[2,3,4]
B1=[5,6,7,8]
OR
A2=[1,2,3,4]
B2=[6,7,8]
这两个组的最小，
有点像二分树的情况，
一个pair，共有n^2个pair。每个pair对两个元素求和，找出和最小的n个pair。
每行每列都是严格升序排列的，所以C是一个Young Tableau。问题化归为，如何在一个
Young Tableau中找到前n个最小元素?
实际上，矩阵C这个Young Tableau是比较特殊的，我们注意到每一行的增量相同，每一
列的增量也相同。所以如果不附加这个特性到Young Tableau, 则原问题和新问题不是
等价的。
问题，应该是等价的。 |
|
r****o
发帖数: 1950 | 29 处理每行的时候反序将children节点放进qeueue里不行吗?
，不 |
|
f*********t
发帖数: 271 | 30 4. 假设给你一个文件（可能很大），每行还有人名，和电话号码，设计数据结构使
得给出人名，迅速的查其电话号码。如果要支持给出first name查电话，给出last
name查电话号码呢？如果要在查询支持名字中含wild card呢？
===========================================================
这个是用hash？？ |
|
w******a
发帖数: 236 | 31 一不小心，上次写的面经第一部分上了十大推荐。太激动了，谢谢斑斑奖励的包子。还
要特别感谢aeon同学送的大包子。（第一部分在这里：http://www.mitbbs.com/article_t/JobHunting/31659453.html）
话说第一次on-site，我本人自己感觉良好，觉着题目都做出来了，虽然有些多余变量
，也没关系吧。于是喜滋滋的等着那轮四个人的interview。没想到，过了几天，HR哥
哥写信来，说面试官觉得我写程序不够快不够简洁，建议再来coding的面试。无语，谁
让咱不是那种在whiteboard上写code如流水的牛人，只好灰溜溜的同意再来一次on-
site。
第二次是一个很nice的哥哥面我，一直微笑，在我卡壳的时候，也都提示我。废话少说
，上题目：
1. 一个rotated的排序整数数组，比如A=[6，8，1，2，4，5]，写code找一个给定元素
，并分析复杂度。其实就是binary search的变体，但是需要考虑两种A[m]中值的情况
加以判断。
2. 他谈到facebook的log，如果每个log文件有10 billion行，每行包括t |
|
y*r
发帖数: 590 | 32 读取一个文件，格式为
700 task1
300 task2
800 task3
...
每行第一个为等待的时间（单位ms），第二个为要执行的task。
例如第一行为程序开始后等待700ms，然后执行task1.
这里等待的时间有什么好办法实现没？感觉用nanosleep（）不太好。 |
|
A********l
发帖数: 184 | 33 8月份投的简历，一个礼拜后约了在线测试，因为我很少用c++,所以选的是java。题目基本上是j2ee和core java，感觉一半一半。
几天后约了电话面试，一开始就直接告诉对方，我c++用的很少。对方很遗憾的说，我准备了很多c++的题目，那我问别的吧：
1. 一个文件，1m行，每行是一个1-5000的整数，问你如何找到出现次数最多的10个数
2. linux下，已知一个process的名字，如何kill
3. 一个cube，表面涂成黑色，内部是白色，横竖分别切三刀，然后随意从27个小cube中选1个，toss，问黑色面朝上的概率
电话面试持续了半个小时，几天后约了onsite。
因为recruiter出差，onsite约到3个礼拜后，就是这个周一。
见了两个小兵，很年轻，一个印度人，一个美国人。
如法炮制，直接告诉他们，c++用的很少。然后他们就开始问算法题。
1. 实现一个stack,使得pop,push, min都在O（1）实现
2. linkedlist 找环，并且返回环的起始点
3. binary tree,如何将同一层的节点联结成一个linkedlist
4. 讨论了c++ |
|
p********7
发帖数: 549 | 34 我觉得每行的最大max和矩阵的最大max没有关系的，有可能最大max的每一行都不是这
一行的
最大max array |
|
n******2
发帖数: 47 | 35 Bloomberg的这个问题答案是什么？
假设给你一个文件（可能很大），每行还有人名，和电话号码，设计数据结构使得给
出人名，迅速的查其电话号码。如果要支持给出first name查电话，给出last name查
电话号码呢？如果要在查询支持名字中含wild card呢？
pre-fix tree? bloomberg一般不会问这么难的算法题吧？ 那就得用三个hashtable
on full name, first name and last name? 似乎又不合适，而且也没办法处理wild
card。 |
|
n******n
发帖数: 49 | 36 发Yahoo MS Amazon面经
我碰到的 也都是一些还算中规中矩的题 所以 也算是来给各位找工作的打打气！
Yahoo 电面 印度人
1.电话键盘上1-》abc 2->cde... 现在来一堆数，未知长度，比如123456..... 请输出
序列可能对应的所有字符串
比如 123 输出acf, acg, ach, bcf...
2.检测链表是否有环
3.sql语句
employee(id(primary key),name)
employee_bonus(id(primary key), bonus) （现在觉得这题 似乎有点问题，因为他和
我说 id可以对应多个bonus, 那这还算是primary key吗。。。）
请写sql 输出name和这个人bonus总和。
MS on campus interview - first round
1. 简历问题
2. 给一个字符串检测是否是valid ip address, 这题他似乎是想看看我的思路，我说
regular express, 他说要code, 我就写了一些，解释了一下。总之，这题真要追究起
来，细节颇多，但因为我们每个... 阅读全帖 |
|
n******n
发帖数: 49 | 37 发Yahoo MS Amazon面经
我碰到的 也都是一些还算中规中矩的题 所以 也算是来给各位找工作的打打气！
Yahoo 电面 印度人
1.电话键盘上1-》abc 2->cde... 现在来一堆数，未知长度，比如123456..... 请输出
序列可能对应的所有字符串
比如 123 输出acf, acg, ach, bcf...
2.检测链表是否有环
3.sql语句
employee(id(primary key),name)
employee_bonus(id(primary key), bonus) （现在觉得这题 似乎有点问题，因为他和
我说 id可以对应多个bonus, 那这还算是primary key吗。。。）
请写sql 输出name和这个人bonus总和。
MS on campus interview - first round
1. 简历问题
2. 给一个字符串检测是否是valid ip address, 这题他似乎是想看看我的思路，我说
regular express, 他说要code, 我就写了一些，解释了一下。总之，这题真要追究起
来，细节颇多，但因为我们每个... 阅读全帖 |
|
l*****c
发帖数: 316 | 38 给定一个整数n , 给定整数m
列举所有的矩阵，满足条件：1 元素都是0 或 1
2，矩阵 n * m
3, 每行的和为 m-1，每列不得全为1
例如 n=4, m=3
1 0 1
0 1 1
1 1 0
1 0 1
或
1 1 0
0 1 1
1 1 0
1 0 1
如何找出所有的矩阵，用最少的时间
觉得这题有点bt, 被难住了，求帮助 |
|
f***g
发帖数: 214 | 39 跟8皇后类似吧，
往全1矩阵里面放0；
条件：
每行有一个0；
每列必须要有0；
递归。
不知道有没有更快的 |
|
h**6
发帖数: 4160 | 40 f(n, m)的定义是每行恰好有一个0，每列至少有一个0的矩阵数。
那么在第一行第j列放0后，以下n-1行有两种选择：
1. 第j列没有0 => f(n-1, m-1)
2. 第j列有0 => f(n-1, m)
两种选择不会重复或遗漏 |
|
P********l
发帖数: 452 | 41 没搞懂，觉得哪里不对。
先说我的理解。
把每行的0的位置写下来可以得到一个编码.
例如 n=4, m=3
1 0 1
0 1 1
1 1 0
1 0 1
编码是: 1,0,2,1.
0到2肯定在其中，然后再从0－2任选一个。
所以f(4,3)=3! * 3 * 3 = 54种。
han6的迭代公式是36种。哪里不对。 |
|
t*****j
发帖数: 1105 | 42 新题目也不难，就是假设
memory只能存m个char，无硬盘可存，程序不断从一个文件里读char，不知道文件有多
少行，等读完了才知道。需要读完以后能够返回一个char，该文件里每行返回的概率都
相等。 |
|
h*****1
发帖数: 74 | 43 假设给你一个文件（可能很大），每行还有人名，和电话号码，设计数据结构使得给出
人名，迅速的查其电话号码。如果要支持给出first name查电话，给出last name查电
话号码呢？如果要在查询支持名字中含wild card呢？ |
|
a*m
发帖数: 14 | 44 最近面了好几个公司，把题目和经验分享一下攒人品求祝福：
Amazon 两轮：
Round 1:
1. C++ Copy Constructor, 包括接口和deep vs. shallow的区别，这题答得一般，有些
细节没搞得特别透彻
2. Hash Table的实现和技术要点 (仔细看过一遍wiki就没问题了）
3. Large file, multiple lines, how to get any line in equal probablity. 这题
可以问得很深入，比如文件太大内存无法装入如何办。
我回答的思路：
内存够文件内容就都装入内存，然后randomGenerator选一行,one pass
内存不够可以记录每行的偏移值在内存，这样之后可以fseek到那一行去读取
如果偏移值都放不下，可以divide into ranges, 当然这个range的stepsize不好选，可
以预估，也可以动态改变（到这一层其实大致给些思路就ok了）
Round 2:
1. Research problem
2. How to build a service to generate ... 阅读全帖 |
|
b******y
发帖数: 660 | 45 比较郁闷最近的几个公司的onsite都不能一天完成，两轮onsite真是累人。
由于NDA的缘故，不方便报得太具体。要具体讨论请pm。
报一下今天SF某著名网络公司的onsite。
面了５个人，最重要几个leader从３点开始开会，估计还得再去一趟（如果他们觉得我
前面面的还行的话）。不过有幸面到的第五个是创始人之一 ！
几乎每个面试都问到我做过的十分match他们的一个小project，其实就是一个final
project，幸好还算interesting。下面聊聊问到的技术问题。
１）测试一个stack（给出接口）；实现这个stack
２）找两个已排序数组的交集
一步步优化，最后要做到比mlogn更好。
３）优化我project当中的一个n＾２的算法
４）很多机器，每个机器都有一个log（一系列的访问记录，每行是一个网站名）。要
求这些机器当中的访问最多的前K个网站。 |
|
h**********d
发帖数: 4313 | 46 就是一个很大的file，不知道有多少行，问你怎么才能random的选其中一行，使得每行
被选的概率相等 |
|
s*******t
发帖数: 248 | 47 我能想到的是这样：
每行取最大O(n), 是一个sorted array， 取最大O(1), 然后 insert next value to t
he right place O(log(n)). k个所以klog(n). 是这个意思吗？
有人说用heap，但是感觉建个heap就要nlog(n)吧。 |
|
M7
发帖数: 219 | 48 First 电面:
1. 谈一下不同数据结构的优缺点。
2. 一个大文本文件里有电话号码。每行至多有一个号码。How do you process and
return the total number of phone numbers. (in command line, use grep and wc)
3. A generic tree. how to print out nodes by level (one lever a line)
说了pseudo code, 要求电面后email给他。
4. A database application is slow. How do you investigate the problem and
how to improve it.
Second 电面:
1. 写一个函数，输出一个整数里1-bit的数目。比如CountOneBits(7)应返回3。
2. 网页很慢。找出可能原因。（和一面的最后一个问题差不多）
3. 下面statements的区别是什么？接着问了关于constructor的问题(copy), shallow
vs. d... 阅读全帖 |
|
j******a
发帖数: 55 | 49
如果并行化grep，等价于mapreduce中的哪一步。我不是很sure，我觉得grep都返回结
果了，应该算
是两个都沾上吧。我类比一下wordcount，觉得把每行并行化，算是map，把结果匹配出
来返回是
reduce。有没有行家解释一下？ |
|
r*****b
发帖数: 8 | 50 面试实习的职位。一共3轮。
第一轮，问了一下自己觉得最有意思的项目。然后就是3个题：有一个很大的Log文件，
记录了每个用户点击网页的时间，问怎么找到最常见的3连击；有两个很大的文件，文
件里每行都是string，问怎么找到重复的；找一个无序数组的第k大元素。
第二轮，很多基本的问题，比如什么是hash,怎么处理冲突；然后什么是encapsulation
，什么是inode。大多是基本概念。然后问了个程序题，怎么验证一个数是不是素数。
最后考了一个OOD，那个电梯的题目。
第三轮，两个进程之间有多少种方式可以互相通讯（尽量说，不要管效率）。然后问了
问怎么处理race condition。接着就是验证一个二叉树是不是BST。然后问了一个设计
题，题目描述太复杂了。。很难复述。。然后俺就跟面试官聊啊聊，后来才发现他想要
一个多态的设计。
大概就是这样。 |
|
