E*******0
发帖数: 465 | 1 我考虑到如果用int变量来标记的话，空间复杂度会是O(n)，如果用bit来标记，复杂度
会降低。
而且，我是64个点64个点的处理的。所以，空间复杂度是O(1). |
|
w****o
发帖数: 2260 | 2 你的这个方法，适合求并集， 复杂度是 m log m + n log n + m + n
可是你的方法，如何求交集？没有弄明白。
另外我觉得你的方法求并集的复杂度太高了。如果只把短的数组排序，用binary
search到短的数组中查找长数组里的数，这样的复杂度是 m log m + n log m (假设
m < n), 不过这个方法正像我在原帖里说的，没有办法处理重复的情形。 |
|
i**********e
发帖数: 1145 | 3 顶！
这个状态只需用 O(N^3) 的空间来保存就行，复杂度是 O(N^4)。
假设 (i,j) 分别为 s1 和 s2 的开始 index，n 为子串的长度，k 是把字串分成两个
子串的 pivot point (k = 1 ... n-1)：
F(i, j, n) = F(i+n-k, j, k) && F(i, j+k, n-k) ||
F(i, j, n-k) && F(i+n-k, j+n-k, k)
base case 为 F(i, j, 1) == true, iff s1[i] == s2[j]
然后 bottom-up 建立表，从所有 F(i, j, 2) --> F(i, j, len)，len = s1 长度。
那么答案就是 F(0, 0, len).
以下是非递归的 bottom-up DP 代码，空间复杂度 O(N^3)，时间复杂度 O(N^4).
bool isValid(string s1, string s2) {
int len = s1.length();
bool dp[64][64][64] = {f... 阅读全帖 |
|
n********k
发帖数: 40 | 4 国内数学本科，新加坡计算机博士，读到第三年末不想读了，开始找工作。找了一年，终于找到了脸书，
这里面的起伏辛酸相信大家都明白的。如果按照投简历算的话，我找了将近五十多个工
作吧，一开始找的都在新加坡，大家应该也没什么兴趣，我就抛出几个小结论吧：1.
amd ibm都是sb公司，你们懂的；2.我这种情况脸书给了我offer，但我就是无法在新加
坡找到SGD4000（相当于美元3300）一个月的工作，不得不感叹这里人工成本太低；3.
这里的公司更看重马上就能给公司创收，所以会要求新毕业的学生懂很多具体的技术啊
语言啊。
1.NV总部。
>事实：我博士是做GPU的，所以加入NV一直是我的理想。我傻到第一份简历就投给了NV
，然后去年九月拿到了我这辈子第一个电话面试，可想而知，被拒。
>题：讲讲你自己；讲讲这一个你做过的项目；你给我讲讲shared memory是什么，应该
怎么用；你给我讲讲atomic operation是什么，怎么用；你会什么语言，各个语言的自
信程度；C++里面的virtual function是什么，pure virtual function是什么；你用过
C++ S... 阅读全帖 |
|
c****p
发帖数: 6474 | 5 3.简单起见，一个格子被直接按中导致的0-1翻转称为主翻转，和它同行同列的翻转导致
的翻转称为副翻转。那么需要找到一个将主翻转和副翻转区分开来的办法。可以考虑异
或。
4.对于给定图案中的任意一点x,y，可以把它所在的行和列的所有元素相异或。对于M+N
为偶的，若结果为1，则说明该点被按过；对于M+N为奇数的，若结果为0，则说明该点被
按过。
举个例子（我自己写的一个生成图案的函数）
A是图案，D是被按过的键，也即我们要找的解
>> [A,D] = gen_pad(4,4,.2)
A =
1 0 0 1
1 0 0 1
1 1 1 1
0 0 1 0
D =
0 1 0 0
0 1 0 0
0 0 1 0
0 0 0 0
假设解为S矩阵，我们要求出S=D
假设左上角元素为A[1,1]，则
S[1,1]=xor(A[1,... 阅读全帖 |
|
h********g
发帖数: 155 | 6 把思路整理了一下，最终得到：
１ 当M和N都是偶数时，解总是存在的，列出的线性方程组可以通过MOD ２代数求解，
时间复杂度是O（M＊N）。
２ 当M和N中有一个是奇数时，问题的结构发生了变化，有的情况下可能不存在解， 但
可以通过动态编程来确定是否有解，并找到一个解，动态编程的时间复杂度是O（M＾３
N＾３），空间复杂度是O（M＾３N＾３）。
不知道情形２下面是否有更快的解法。 |
|
G******i
发帖数: 5226 | 7 ☆─────────────────────────────────────☆
lanmao (懒猫) 于 (Sat Jul 9 11:29:24 2011, 美东) 提到:
（坑已经够大了，只管挖不管填不道德，俺自个合集了。）
看了芙蓉的减肥照片和凤姐的励志围脖，也想来跟个励志潮流。满版上都是google
amazon facebook，搞得不是编程熟手不会脑筋急转弯就没好工作似的。 俺来贴个BSO
的Java面经吧，来鼓励一下正在奋斗着的童鞋们。认识俺的都不要说啊，俺那么低调~~~
个人背景：人工智能方向的，学校算top 50吧，9月答辩，读了整整八年的老博士马上
就要新鲜出炉啦！
先低调的说一下amazon经历。amazon给俺发信三四次，要求俺去面试，没理。HR打电话
过来说为啥不理，俺说你们招聘职位太entry level，没兴趣。HR说那给你找个高层次
点的职位。过两天打电话来，说有个高级程序员的活，能不能给我们的hiring manager
一个向你展示我们项目产品的机会。俺心想，说得好听，还不是又要问那种脑筋急转弯
问题，反正答不出，没必要耽误时间。于是很彪... 阅读全帖 |
|
Z*****Z
发帖数: 723 | 8 电话筛选
前缀树： 情景是命令行下做自动完成提示，就是用前缀树把所有可能的命令先存起来，
然后用户打跳格键的时候返回所有可能的命令。
树有两个操作，存储和查询。
我跟这题很有缘：
http://www.mitbbs.com/mitbbs_article_t.php?board=JobHunting&gid
昂赛特
他们搬家后还没立牌子。楼里各种安全措施，我在进去之前还被要求出示证件，进去之
后上厕所都得有人陪着刷卡。
面试开始，第一个，纯种国人，问了两个问题，算一个二叉树的直径。二叉树的直径定
义为树上任意选两个点的距离的最大值。第二个问题是给了一个整数随机数生成器零到
甲，和另外一个正整数乙，让生成一个零到乙之间的随机数。
第二个，原面试官救火去了，来个临时的。上来问排序，两个大文件，全是整数，内存
装不下，怎么办。答，把每个文件分成块，逐个排序，输出到临时文件，然后归并所有
临时文件。归并的时候详细讨论了两路归并和多路归并的区别，主要是读写次数的区别
。然后，主要问题是实现一个缓存。我说在爪哇里用链接的哈希表巨简单。说，不用那
东西自己写一个怎么办。遂从头写了一个。假设哈希表和链表... 阅读全帖 |
|
h********o
发帖数: 14 | 9 我做的跟 3sum 是一个复杂度 O(n^2); 做法也跟 3sum差不错。
1.先sort 数组S，O(nlgn);
2. 使用三个下标 i (当前下标) f(头下标) t(尾下标)
i 从0 到 n-1 遍历 // n 是数组长度
对于每一个i， 设置 f = i+1, t = n-1,
计算 sum = S[i] + S[f] + S[t], 如果比之前的sum更接近，更新。
然后，如果sum 比target 小 ， f++， 否则 t--
对于每一个 i ，以上操作循环至 f>= t, 所以每一个 i 要遍历数组一遍
最终， 第2步的复杂度是 O(n^2)>O(nlgn), 所以这个算法复杂度也是O(n^2) |
|
i*********7
发帖数: 348 | 10 电面的确太水了
就问了我三个超基本的题目：binary search的复杂度，mergesort的复杂度，
quicksort的复杂度。。。。。=。=
然后就让我做题去了。。 |
|
i*********7
发帖数: 348 | 11 电面的确太水了
就问了我三个超基本的题目：binary search的复杂度，mergesort的复杂度，
quicksort的复杂度。。。。。=。=
然后就让我做题去了。。 |
|
p*****2
发帖数: 21240 | 12 来自主题: JobHunting版 - 请问G一题
理论上应该N!/((N/2)!*(N/2)!)？ 但是我不清楚怎么写code体现这个复杂度。火鸡帮
讲讲。这个我好像一直没好好想过。
如果暴力写dfs有两种方式，一种是N!/(N/2)!的复杂度，其实大是因为成排列了。另一
个是2^N复杂度了。 |
|
p*****2
发帖数: 21240 | 13 来自主题: JobHunting版 - 请问G一题
理论上应该N!/((N/2)!*(N/2)!)？ 但是我不清楚怎么写code体现这个复杂度。火鸡帮
讲讲。这个我好像一直没好好想过。
如果暴力写dfs有两种方式，一种是N!/(N/2)!的复杂度，其实大是因为成排列了。另一
个是2^N复杂度了。 |
|
I********T
发帖数: 22 | 14 题目是leetcode上online judge的combination， 就是n个数(1,2,3,4...n)找k个数的
combination. 一般都用递归做，可是这样就会把有些combination重复算。 比如： C(
n,k) = C(n-1, k-1) + C(n-1, k) = C(n-2, k-2) + C(n-2,k-1) + C(n-2,k-1) + C(n
-2, k). 这样C(n-2,k-1)就重复了。 如果用dp做的话就可以缓存C(n-2,k-1)的结果。
这两种复杂度各是多少呢? 我觉得递归做是C(n,k)，因为复杂度公式和combination计
算公式一样。 dp做好像是N*k （假设我们用table缓存结果）。 可是由于table里每个
格子的存的元素数目大于一，所以复杂度还是C(n,k)。
这样的话是不是说dp在这个问
题上毫无优势? 谢谢 |
|
C*******n
发帖数: 24 | 15 Q: You are given a binary tree in which each node contains a value Design an
algorithm to print all paths which sum up to that value Note that it can be
any path in the tree - it does not have to start at the root.
其实这个题本身就说的不清楚，我看了一下答案解析，发现题意是：给你一个二叉树，
每个节点都有一个数，再给你一个sum，求树中所有和为sum的路径，路径的开始可以
不为root。
答案中给出的解法号称O(nlgn)的时间复杂度（其实就是最直觉化的做法，每个节点都
DFS），但是我感觉答案对时间复杂度的分析有问题，因为他分析的时候有个条件是：
There are 2^r nodes at level r。我感觉他分析的这个不是最坏情况，最坏情况应该
是每一个level只有一个节点，时间复杂度为O(n^2)
求问刷过Cracking Coding Interview的前... 阅读全帖 |
|
l****p
发帖数: 397 | 16 第一通电话：
听口音应该是老印的，有点口音，面试过程中好几次我都没听清反复问。
上来没寒暄几句就写代码：
找出一个树中最深的结点。
明显留了好多细节让我问，于是我开始clarify:
1. 是不是binary tree。答：good question, yes, assume it's a binary tree
2. 是不是balanced binary tree。答：does that matter? 我边想边说，好像没关系
然后我再也想不出其它问题了。开始想算法。想一半，他才提醒我说还有一个细节我没
问：如果有多个最深结点怎么办。回答是返回最右的。这是一个失分的点
然后解释算法，可以用深度优先遍历也可以用广度优先遍历，记录所有叶节点的深度，
然后找出最深的。他问复杂度，我说时间是O(N), 空间是O(N). 他说空间能优化吗？我
说能， 在遍历过程中只记录最深的就行。他问这下的空间复杂度，我说是O(1) 。然后
让我开始写代码，我说深度优先呢还是广度优先，他说有什么区别，我说差不多，然后
想想不对，广度优先需要一个queue，这是O(N)的空间，深度的只要O(lgN)的空间，这
... 阅读全帖 |
|
i******e
发帖数: 273 | 17
讨论一下用两种数据结构实现的时间、空间复杂度：
1）priority_queue (max heap)
2) 100个元素的链表数组
- 使用1）和2）的getPackage() 的时间复杂度都是O(1)
- 对于receive()， 使用priority_queue， 插入是O(lgN), 使用链表数组如果维护一
个指向每个priority链表结尾的指针，插入是O(1)操作。
- 使用1）和2）空间复杂度都是O(N)
- 使用2）查找当前最高priority 链表也是O(1)操作。
所以2）比1）更有效？ 这样分析对吗？ |
|
l*********8
发帖数: 4642 | 18 你说的对，done的算法，平均时间复杂度是O(nlogn)
不过，跟基本的quick sort一样，最差时间复杂度也O(n^2).
比如 1 2 3 4 5 6 7 8
我之前只想了这个例子，就误以为算法时间复杂度是O(n^2)了 ：） |
|
m****9
发帖数: 26 | 19 大概说一下面试的过程，求分析下被拒原因：
第一题：多个sorted list merge, 大致说了下思路，用最小堆。然后开始写。大概20
分钟左右写好了。中间电脑出了点问题重启了一次，google doc断了一次。然后面试官
检查了一遍代码，说ok。问了下时间复杂度，回答后说没问题。
又问如果提供了一个merge两个list的函数，如何做。我先说了每次选两个进行merge，
分析了一下时间复杂度。问有没有更好的解法，给了个hint,然后我就说了下用分治来
做的算法的思路，分析了一下时间复杂度，面试官也说ok了，没让写代码。
问有没有什么问题，随便聊了下面试官的工作。然后就结束了。
被拒是因为第二个题目，给了个hint才做出来的么？或者因为做题速度太慢么？感觉电
面总是过不了... |
|
d*********g
发帖数: 154 | 20
这个算法的复杂度不一定比用堆好吧？“给定任意一个数，有办法判断该元素是矩阵中
第几大的”，这一步应该是O(n)，n是矩阵的max{长，宽}，然后二分法找到恰好大于k
个数的数是O(lgm)，其中m是矩阵中的最大值减最小值的大小。所以总复杂度是O(n*lgm
)。而用堆的复杂度是O(k*lgn)。不知道我的理解对么？ |
|
c**s
发帖数: 159 | 21 时间复杂度为O(n)的in-place算法 可以搜perfect shuffle problem 很复杂。
还有个O(nlogn)的分治in-place算法 用到循环移位 可以比较简单的解决：
（1） 把b部分循环移 n/2 位 这样 中间的n个元素元素是a的后n/2个和b的后n/2
（2） 对中间n个元素递归完成任务 这样 中间n个满足要求了
(3) 对全体的后3/4×（2n) 的元素 循环移动 n/2位， 这样后面n个元素满足要求
前面n个元素又是一半的子问题
（4）完成前一半的n个的任务
循环移位是O(n)的
复杂度 T(n) = 2 * T(n / 2) + O(n)
总复杂度T(n) = O(nlogn) |
|
f*********d
发帖数: 140 | 22 一紧张， 递归方程都写错了，
这个题他一直催我，说应该一看就知道复杂度
1 我还没有达到一看就知道复杂度的层次
2 求稳起见，写递归方程用主定理给复杂度，可惜我不争气，方程写出了个typo，被他
揪出来了，后面用主定理再次出错，a 和 b弄反了。
总之，还是自己不争气吧 |
|
p*****2
发帖数: 21240 | 23
有人知道TreeMap higherKey的复杂度吗？如果是log(n)的话，那 TreeMap查找log(n),
合并就要n(logn)的复杂度了。那还不如ArrayList了。
ArrayList: search logn, insert n
LinkedList: search n, insert n
貌似ArrayList复杂度最好了。当然写起来更费劲些。今天有时间练练。 |
|
j*****s
发帖数: 189 | 24 我是芝加哥大学计算机的小硕，一个月前开始找工作，到目前为止phone interview有
几个，onsite interview进行过两个了，虽然第二次的结果还没出来，但应该也是挂了
。发个帖子给自己总结一下经验教训，也希望大家在面试的时候能多多注意吧。
1） 假如遇到的题目比较简单，那就要尽量一次写对，写完之后先不要忙着跟面试官说
写完了，先自己看一遍，看有没有什么明显的bug，有就及时改过来，等面试官指出来
再改就不好了。
2） 假如遇到的题目是自己没见过的，然后想出了一个解决方法之后，先不要忙着写代
码，先想一下这个方法的时间复杂度和空间复杂度，如果时间复杂度太高的话，看有没
有什么更好的方法，比如DP之类的。
3） 假如遇到设计类的题目，先不要忙着给出解决方案，一定要先跟面试官确认清楚题
目的具体含义，包括哪些部分是需要我们自己设计的，哪些部分是存在于系统的其他部
分可以直接使用的，可以有哪些假设，大概有哪些情况需要考虑。如果一边描述自己的
解决方案，一边不断根据面试官的提问改进的话，不仅自己做起来别扭，最后的实现方
案即使是可行的，也肯定是改的一塌糊涂。
4） 假如遇到需要... 阅读全帖 |
|
m******s
发帖数: 165 | 25 来自主题: JobHunting版 - G 家面经 真要虐出翔了。。。
1:
边同时遍历两个树边建一个新的，最后有可能要再遍历一次，比如：
I1 =
01
10
I2 =
10
01
则I1 intersect I2 =
00
00
即I1 intersect I2 = 0
2A:
O(n)，由于array可以随机存取所以很好写。。。
2B:
好像前面有说，根据两个人的位置dp，greedy不太对
3A:
c++ stl lower_bound
3B:
应该不用上template吧orz，意思意思行了
4A:
trie (prefix tree)，根据用户输入习惯或者是流行搜索词进行缓存
4B:
range minimum query，做法很多，在线算法评判的标准有这么几个：
空间复杂度 预处理时间复杂度 每次查询时间复杂度
可以搜索一下各种算法的不同
另外还可以扩展到多线程/多台机器
的。 |
|
x*****0
发帖数: 452 | 26 嗯嗯，明白了。是这样的
因为对java不熟，所以都是用c做的。我的想法是这样：
(1) 遍历word one by one.
(2) 每遇到一个word，有三种情况
a. 这个word不是以 A E I O U 开头的, do nothing
b. 这个word如果是，例如以A开头。那么又分两种情况。
b1 如果这是第一个以A开头的word，用变量x记录其位置。
b2 如果这不是第一个以A开头的word，将其移到上个以A开头的word之后，并更新x。
算法时间复杂度O(N^2) N是string的长度。空间复杂度O（1）
移动一个word的算法：
http://stackoverflow.com/questions/15212749/move-a-word-in-a-st
还有另一个方法，时间复杂度要低一些。
(1) 对string中的每个word进行以比较首字母的方式排序。
(2) 然后遍历原始的string。当遇到word以A E I O U开头时，比如A。从排好序的
string中输出所有以A开头的word。
这个方法应该和你的java实现本质上差不多。 |
|
S******t
发帖数: 151 | 27 我对于这个问题的理解是最好用Aho-Corasick Algorithm而不是用Suffix Tree，Aho-
Corasick就是做多串匹配用的，实现复杂度也低很多。
http://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_string_matchi
Suffix Tree的线性构造算法是非常复杂的，我的印象里面要在300行以上(以Ukkonen算
法为例)，而非线性的构造算法则毫无意义，还不如直接brute force的去匹配(比如说
CC150上的算法)。
Suffix Array的实现稍微简单一些，但是Linear Time的构造算法仍然并不好理解，我
的印象里三分法的实现复杂度应该在30-50行，而且几乎是千篇一律的模板，倍增法的
实现虽然好写一些但是复杂度就不是O(n)而是O(nlogn)的，不知道最近是不是有更好的
实现方式了，还请各位不吝指教。。。 |
|
b*****n
发帖数: 618 | 28 来自主题: JobHunting版 - RF 面经 姑且称为RF吧
申请的是fresh grad职位，2月底第一次跟hr联系到这个周拿到offer，中间经历了
online code test，onsite和一次电面。
好像不少人对他家的code test比较感兴趣，4个小时两道题，每个人遇到的题目可能不
一样，
第一题很简单，主要考察code质量，第二题稍微难一点，每个题目的要求都很详细要仔
细看，还有详细的提示也要注意。
我遇到的题：
1. 一个矩阵，从指定格子向右发射激光，每个格子有以下几种可能：激光直接穿过，
或者改变激光方向（4个方向）
问激光射出矩阵之前一共经过了多少格子，如果死循环了就输出－1
2. 一堆racer，每个racer有出发时间和到达时间，计算每个racer的score，规则如下
：score ＝ 所有出发比自己晚但是到达比自己早的racer数量之和，（所有的出发时间
和到达时间没有重复的）要求时间复杂度
code test过了之后我直接就安排onsite了，onsite本来安排6个人但实际上只面了5个
，题目如下：
1. 两个不一样长度的sorted array，求median。
leetcod... 阅读全帖 |
|
b*****n
发帖数: 618 | 29 来自主题: JobHunting版 - RF 面经 姑且称为RF吧
申请的是fresh grad职位，2月底第一次跟hr联系到这个周拿到offer，中间经历了
online code test，onsite和一次电面。
好像不少人对他家的code test比较感兴趣，4个小时两道题，每个人遇到的题目可能不
一样，
第一题很简单，主要考察code质量，第二题稍微难一点，每个题目的要求都很详细要仔
细看，还有详细的提示也要注意。
我遇到的题：
1. 一个矩阵，从指定格子向右发射激光，每个格子有以下几种可能：激光直接穿过，
或者改变激光方向（4个方向）
问激光射出矩阵之前一共经过了多少格子，如果死循环了就输出－1
2. 一堆racer，每个racer有出发时间和到达时间，计算每个racer的score，规则如下
：score ＝ 所有出发比自己晚但是到达比自己早的racer数量之和，（所有的出发时间
和到达时间没有重复的）要求时间复杂度
code test过了之后我直接就安排onsite了，onsite本来安排6个人但实际上只面了5个
，题目如下：
1. 两个不一样长度的sorted array，求median。
leetcod... 阅读全帖 |
|
f*******t
发帖数: 7549 | 30 F
电面和onsite都是在西雅图本地面的。此分部是在downtown附近租的两层，有近360度
的景观，十分漂亮。分部总共有不到200人，很多是从微软来的，从A挖来的倒不多，原
因不明。午饭质量不错，小分部就不指望有中餐咯。
电面
1. 国人大哥，问了几个常见题，最难的题具体细节记不清了，大概是01矩阵上的DFS，
随便聊了会儿直接拿到onsite。
Onsite
1. 白女，亚马逊manager出身的女工程师，主问culture fit问题，比如为什么想来FB
。Coding题是恶心的罗马数字。因为鄙视这道题所以没在leetcode上刷过，还好是简单
题，很快写出来了。
2. 一个搞后端处理data的中国哥们，问sort linked list。随手写了个merge sort过
关，merge的时候没用dummy node方法，if语句用的很多，比较蛋疼。讨论了一下具体
的算法复杂度，直接背答案的人估计会被考倒。所以说做面试题的目的主要还是掌握算
法并能灵活用于解题，不太可能所有题都能练到随手就写出最优算法bug free的程度。
3. 午饭不算正式面试，跟一个呆了六七年的fron... 阅读全帖 |
|
f*****n
发帖数: 35 | 31 一道RF的面试题：
有N个ad, (n是million级别的)
每个ad的表示为（id, value）
比如：
121 -> new
130 -> new york
145 -> new york time square
156 -> new york department store
假设有一 query = new york department store
规定ad中每个单词都包含在query中时，这个ad为valid （即ad是query的子集）
上述例子中ad 121， 130， 156是valid的，145是invalid
问：
如何设计一个solution，使得
vector getValid(string query) （返回所有valid的ad的id）这个函
数在worst case时复杂度也能小于O(n)，面试官的说法是does not depend on N.
整个solution可以分两个阶段，第一阶段是preprocessing，这个可以是O(n)的，但是
第二阶段query阶段，也即调用函数getValid()，必须小于O(n)
... 阅读全帖 |
|
f*****n
发帖数: 35 | 32 一道RF的面试题：
有N个ad, (n是million级别的)
每个ad的表示为（id, value）
比如：
121 -> new
130 -> new york
145 -> new york time square
156 -> new york department store
假设有一 query = new york department store
规定ad中每个单词都包含在query中时，这个ad为valid （即ad是query的子集）
上述例子中ad 121， 130， 156是valid的，145是invalid
问：
如何设计一个solution，使得
vector getValid(string query) （返回所有valid的ad的id）这个函
数在worst case时复杂度也能小于O(n)，面试官的说法是does not depend on N.
整个solution可以分两个阶段，第一阶段是preprocessing，这个可以是O(n)的，但是
第二阶段query阶段，也即调用函数getValid()，必须小于O(n)
... 阅读全帖 |
|
S******n
发帖数: 132 | 33 拿到x3家offer了，打算从了，见好就收，不打算明天去面x6了，省下时间给大家写面经
首先感谢编程女神，其次感谢本版大牛的资源共享，再次感谢dongfeiwww大牛给我
refer，最后感谢我同学面试前给我mock interview
终于有机会回馈本版，写一些我的个人体会，也激励一下暂时不顺利的同学
我总共面了两家半，被x5拒了，x3给了offer，x6是半途而废，唉，dream company，最
近太忙实在没啥时间准备，为免留下悲剧记录，最终决定放弃，俗话说去不了北大，去
北师大也不错，还多一个字，于是决定去x3了。x3签offer不透露题目了，NYC貌似比CA
钱少一点，有家庭的还是可以考虑去加州
我先回忆x5面经，再写感受
可能local的原因，直接一轮onsite，面试我的是一个中国人，人非常nice，给我详细
讲解了公司的情况，我因为面试之前看了王淮那本《打造facebook》，对x5有了一定的
了解，中途问了几个问题，让面试官回答的很high，目的基本达到了，
还是推荐这本书，觉得大家无聊上厕所可以看看这本书，对招人，面试有很详细介绍，
其他一些开发管理的观点也有所启... 阅读全帖 |
|
d******9
发帖数: 36 | 34 找到工作后笔记本坏了，整理的面经都没了。迟了几个月把找工作的经历记录下来，希望能给H4找工作的mm们一些信心和帮助。
个人背景：
THU CS PhD，2011.10生小孩，2012.1毕业，2012.5 H4来美国。读书期间没有实习经历，简历上基本都是课程项目还有自己写的几个小软件（后悔以前太懒了，应该多出去实习的）。
2012.9奶奶从国内过来，我开始复习找工作。
复习材料：
先是CC150，programing pearls, leetcodeOJ，这些至少要自己做2遍的。有时间就看看
版上面经。最后一个面试前两周才开始看introduction to algorithm。在面试前针对公
司类型把本科学的操作系统，编译原理，数据库课件拿出来看过。我是用C++面试，所以
C++语言也复习了一点。JAVA上过课，但是很久不用，忘了很多。用一周的时间在android上自己写了一个小的图片管理器，算是重新学JAVA了。后来证明这个小东西在面试聊项目时还是很有帮助的。
前三本书能无bug写出来是基本功，重要的还是边复习边总结。每一种类型的题目得
举一反三。争取做到看版上面经中类似题目的时候... 阅读全帖 |
|
e*******8
发帖数: 94 | 35 inner loop已经是线性复杂度了呀，用binary search反而会增加时间复杂度？而且３
sum的时间复杂度的lower bound不是已经是Omega(n^2)了么 |
|
s**********e
发帖数: 326 | 36 Given two BTs T1 and T2, return the larest common subtree
idea:
step one:
首先分别对T1, T2做预处理，求出每个subtree的nodes总个数，把得到的结果存到
hashtable里面，这一步时间复杂度O(N), N=number of nodes
step two:
从root开始从上到下对每对相对应的node pair，判断以他们为root的subtree是否相同
given node1 from t1, node2 from t2
f(node1,node2)= true if node1 == node2 && f(node1.left, node2.left) && f(
node1.right, node2.right)
这个过程可以使用dp的思想，建个hashtable存放f的值，key=node1.hashcode+"-"+
node2.hashcode， value=boolean
这一步时间复杂度O(N)
step three:
有了第一步的每个subtree 的size, 第二步的每对s... 阅读全帖 |
|
p*u
发帖数: 136 | 37 输入：
有n个人，m条关系（a, b, enemy/friend）
有2个性质：
1，朋友的朋友是朋友
2，敌人的敌人是朋友
输入不会自相矛盾。
有x个查询，每次查询(a, b)到底是什么关系？没关系，敌人或朋友
我是用类似floyd的思路去解的。f[a][b] = -1没关系, 0朋友, 1敌人
最终时间复杂度是O(n^3)的。
华人面试官，人不错挺有耐心的，超时了20分钟，讨论用floyd去解的正确性。
希望能过 :-)
------
这个问题的变形：
有很重要的条件：敌人的朋友是什么？朋友的敌人是什么？
但是题目中没有给。如果敌人的朋友或者朋友的敌人都是敌人的话，问题就简化了。以
每个节点作为起点，去做一次dfs，记录到当前节点经过了多少个敌人关系的边。奇数
个为敌人，偶数个为朋友。
最后时间复杂度是O(n^2)的
------
另外如果没有敌人这一说，只有朋友的话，就是并查集的做法。时间复杂度是O(n)的 |
|
p*u
发帖数: 136 | 38 输入：
有n个人，m条关系（a, b, enemy/friend）
有2个性质：
1，朋友的朋友是朋友
2，敌人的敌人是朋友
输入不会自相矛盾。
有x个查询，每次查询(a, b)到底是什么关系？没关系，敌人或朋友
我是用类似floyd的思路去解的。f[a][b] = -1没关系, 0朋友, 1敌人
最终时间复杂度是O(n^3)的。
华人面试官，人不错挺有耐心的，超时了20分钟，讨论用floyd去解的正确性。
希望能过 :-)
------
这个问题的变形：
有很重要的条件：敌人的朋友是什么？朋友的敌人是什么？
但是题目中没有给。如果敌人的朋友或者朋友的敌人都是敌人的话，问题就简化了。以
每个节点作为起点，去做一次dfs，记录到当前节点经过了多少个敌人关系的边。奇数
个为敌人，偶数个为朋友。
最后时间复杂度是O(n^2)的
------
另外如果没有敌人这一说，只有朋友的话，就是并查集的做法。时间复杂度是O(n)的
==========
update一下，最后给了onsite，赞国人面试官！ |
|
w*******s
发帖数: 138 | 39 这道题有两种理解方式。当输入是[1, 1]的时候，有两个sequence满足条件，可是他们
都是[1]，所以根据理解的不同，答案可以是1，或者是2。有一种O(nlogn)的方法，不过
是针对答案是2的情形。
首先得将数组中的元素排序，并按数值大小编号，此时我们将原数组变换为新数组，新
数组中的元素值是原数组中数值大小的编号，新数组中的值是从1到n（n为原数组中不同
数值的个数），长度与原数组相同，对于新数组求解等同与对于原数组求解。
举例，原数组是[9,3,6,3]，变换为新数组为[3,1,2,1]
此变换需要排序，故时间复杂度为O(nlogn)
对于此数组（设为A)，我们可以用等同与求LIS的方法来计算个数(DP)，此方法的复杂度
为O(n^2)，DP的状态是对于每一个数组中的元素，我们记录以其为结尾的不同的subseq
uence的个数，设此数组为D。
在求D中每一个元素D[i]的过程中，我们需要对每一个在此元素之前 j < i，并且A[j]
< A[i]的D[j]求和，此操作可以用树状数组（或类似结构）优化为log n，故总时间复杂
度为O(n log n)，空间复杂度为O(n)... 阅读全帖 |
|
z****u
发帖数: 41 | 40 Full-Time面试。第二轮电面，是个印度人。
面试一开始问了10分钟的简历。然后开始出code题，就是计算图里面路径的最小sum，
很简单的递归，不到3分钟敲完，然后要求分析复杂度，我一开始分析错了，他提出我
有错，让我想好了再说，然后我就仔细想想给出了正确的复杂度。之后他问没有优化
，我说可以用cache存储，然后给出复杂度，他说looks ok。Coding完之后还有20多分
钟，他让我问问题，我就问了几个。
面试中有一个不是很顺利的地方是，因为信号和口音的问题，我有三次要求他repeat，
这个会让我减分么？
面试完后一直没有收到feedback，我催了HR一下，前天收到很典型的拒信。
不明白为什么被拒？我感觉我表现的很好啊，虽然不算完美，但是不至于被拒绝。
还有在这种情况下我该怎么做？怎么和HR沟通。 |
|
y*******x
发帖数: 40 | 41 刚刚结束，面试官是三姐，囧，互相交流基本靠在collabedit上打字。
两道题目：
1. copy graph，coding完问复杂度，时间复杂度开始没答对。教训是刷题时一定要明
白复杂度等相关原理，不然很囧。
2. 假设在embed system上编程，不能malloc。给定一个int array，问如何实现
Linkedlist。
这题主要时间都花在讨论上，逐步明白她的要求是：实现insert,delete，且时空复杂
度都是O(1)
我回答为每个node申请3个数组元素，分别存储：data, next index,pre index。然后
使用free list维护空闲元素列表即可。由于交流问题，折腾了快20分钟。
最后时间不够，只让实现了insert。她觉得我假设做的太多，不满意。
总结：比第一轮发挥好一些，基础需要继续加强。英语有待提高，跪给阿三的英语了。 |
|
m*********1
发帖数: 204 | 42 我前面发过一道题了，就是String 找repeat特征那道，要求算法复杂度为O(n)，第二
题也是超级难。我都放上来。注意我的面试是SDE intern职位
第一题是一个口音极其重的烙印，几乎听不懂，还好是算法考试，要是纯聊天更完蛋。
题目如下：
1.有一种String,是把一个更短的String重复n次而构成的，那个更短的String长度至少为
2，输入一个String写代码返回T或者F
例子：
"abcabcabc" Ture 因为它把abc重复3次构成
"bcdbcdbcde" False 最后一个是bcde
"abcdabcd" True 因为它是abcd重复2次构成
"xyz" False 因为它不是某一个String重复
"aaaaaaaaaa" False 重复的短String长度应至少为2（这里不能看做aa重复5次)
要求算法复杂度为O(n)
public boolean isMultiple(String s){
}
这道题因为我开了一个单独贴了，就不在这里讨论了
第二个45分钟面试，是另外一个烙印，这个烙印的口音更重，更听不懂，但... 阅读全帖 |
|
w*****e
发帖数: 1050 | 43 sde intern
问简历的，说了十几分钟。
1.recursive 题目。 leetcode 类似题目。不难。
时间，空间复杂度。
2.实现 void Schedule(int64 timestamp, function* to_run) = 0;
多个模块会调用这个function*， 如何实现。
3.fibonacci
为啥不用recursive。分别的时间复杂度。空间复杂度，包含函数栈上的。
3.设计电梯系统。20层，3个电梯。
估计希望不大了。2、4答的不好。完全没准备过设计题，只刷了算法题。
求大牛指导如何准备。 |
|
J*****a
发帖数: 4262 | 44 你到底是指找工作呢，还是做研究？
计算机的phd和postdoc做研究时当然要用很多数学，从图像处理到信号分析，都是小波
变换，AI等方向也要数学
生物千老不算一份工作吧？不能和码工类比
学生物的去制药厂找工作，面试问你数学？
另外多说几句
你看版上面经写代码不需要数学，那是你看的层次浅。
最近版上有G家还不知哪家的一条真题说“健身房里有多个器械，还有多个障碍物，请
找出健身房里一点，使得这点到所有器械的汉密尔顿路径最短”，请问你不补补数学，
你会做这题么？可能连题目都看不懂吧？
其次，在写完代码之后，面试官都会问你复杂度，有些还会问你为什么。只不过大家写
面筋，懒得把这些写出来。你知道为什么二叉树lowest common ancestor的暴力解法（
最原始直接的解法，无parent指针）和判断二叉树is balanced的暴力解法（最原始直
接的解法）看上去差不多，但前者复杂度是O（n），而后者复杂度却至少是O（nlogn）?
我善意提醒你，你越不是cs出身，面试官越会问你这些 |
|
f******h
发帖数: 45 | 45 也找工作了一段时间了，从版上学了很多，上周G家面完了，求个bless。
之前的一些都挂了，还在继续找其他的。等定下来之后一定发面经回报本版。
谢谢大家啦！！
1. http://www.mitbbs.com/article_t/JobHunting/32005597.html
1) Implement a simple calculator (+,-,*,/);
2) Implement "+1" for a large integer;
3) How to match Ads to users;
4) How to extract useful information from a forum webpage (list all
kinds of useful signal you can think of)
5) How to detect the duplicate HTML pages (large scale);
6) Find all the paths between two places on Google map;
7)... 阅读全帖 |
|
o***g
发帖数: 2784 | 46 讨论一道题
原帖如下：
6. http://www.mitbbs.com/article_t/JobHunting/32631467.html
发信人: goodbai (八段锦), 信区: JobHunting
标 题: 热腾腾g电面 已挂
发信站: BBS 未名空间站 (Fri Feb 21 00:20:19 2014, 美东)
同胞面试官，上来就gdoc做题。
2d array ＊代表障碍物 ＃代表货物 空白就是正常的路
问
如何找到一个点为出发点 能实现总共取货路径最短？ 每次只能拿一个货物，遇到障碍
需要绕开，拿到以后要放回出发点，然后再取另一个
＊＊＊＊＊＊
＊ ＃ ＊
＊ ＊＊＊ ＊
＊ ＊
＊ ＊＊ ＊
＊ ＃ ＃＊
＊＊ ＊＊＊＊
大牛们有什么好思路？我用的bfs，但因为之前讨论题目要求花了很久，没有写完。。
我还是太弱了，move on
==================================================================
我看了原帖主题里，都在讨论... 阅读全帖 |
|
i*********e
发帖数: 9 | 47 Google(summer intern)
1.给你一个two dimensional array, array的元素是0 或者1。问能不能找到一个矩形
，矩形的4个角都是1.
leetcode里面有类似的题，我给了类似的答案，复杂度是O(n^3)，感觉面试官不是很满
意。不知道有没有复杂度更少的算法。
2.有高矮不一的一群人，随机排列。排完之后每个人记下比自己前面比自己高的人的数
目。之后把队打乱，
跟据高度和比自己高的人的数目还原原来的队列。
我给了一个O(n^2)的算法，在算法群里讨论之后有牛牛说用线段树可以实现O(nlogn)的
算法。
Bloomberg:
1. 给一个数组： 6， 3， 10， 5， 16， 8， 4， 2， 1
找出这个数组的顺序。写一个程序，input是数组里的一个数，Output是从这个数开始
的整个数组。
2. 实现一个BFS算法。
3. 一个数组，里面有成对出现的数，也有单个的数，把单个的数找出来（leetcode原
题）。
4. 一个公司有好多员工，员工之间的关系储存为（employee ID, manager ID) 这样的
pair。要求写一... 阅读全帖 |
|
l***4
发帖数: 1788 | 48 第一轮：
1.为什么喜欢CS。CS跟本专业的比较（lz转行）。
2. 基本数据结构概念：比较哈希表和二叉树，操作复杂度。电话本用什么数据结构。
前缀树查找的时间复杂度（这里差点说错）。
3. 编程题：输出字符流中频率最高的字符的频率（略拗口。。）以及扩展。
4. 对面试官提问题。
第二轮：
1. 为什么亚马逊。
2. 两个最喜欢的数据结构并说一下典型操作及其复杂度。
3. behavior问题：如果你要设计、实现和测试一个功能，如何分配时间；扩展：如果
这个功能（项目）很大很大，该怎么办
4. 编程题：大小为N的数组，所存值为1到N-1，其中有一个重复的值，如何找出这个值。
5. 编程题：atoi，并实验两个样本输入。
6. 对面试官提问题。
之前加了刷题群：229623621，收获很大，希望大家多交流。 |
|
b*****d
发帖数: 39 | 49 我觉得楼主实力很强！bless！我也一直以为min-heap是正解，刚才看了这个geek4geek
的讲解，感觉max-heap和min-heap都可以。而却好像确实当n >> k时，max-heap的时间
复杂度是(klogn)是比min-heap的时间复杂度O(nlogk)要好。当然max-heap的代价是空
间复杂度比较高。
楼主加油，一定会有好的offer的。加油。 |
|
b*****d
发帖数: 39 | 50 我觉得楼主实力很强！bless！我也一直以为min-heap是正解，刚才看了这个geek4geek
的讲解，感觉max-heap和min-heap都可以。而却好像确实当n >> k时，max-heap的时间
复杂度是(klogn)是比min-heap的时间复杂度O(nlogk)要好。当然max-heap的代价是空
间复杂度比较高。
楼主加油，一定会有好的offer的。加油。 |
|
