狗家面经 - 未名空间MITBBS历史存档

m*g2013-09-26 07:09

1 楼

【以下文字转载自 PHILADELPHIA 讨论区】
发信人: CCMMBB (聪明宝), 信区: PHILADELPHIA
标题: 今天在新川粤生了一肚子气！
发信站: BBS 未名空间站 (Thu Dec 2 00:27:28 2010, 美东)
前几天看了帖子本来不想去新川粤，我很怕也吃到剩菜，无奈老公想吃辣的，就去了。
要的回锅肉和夫妻肺片。回锅肉端上来一股腥味，生肉味道很大，咯吱咯吱的。我们
找了服务员，老公问能不能换一个，服务员很不高兴，脸一下掉下来，咣抄起菜就走
说给你再炒一下，根本不征求我们的意见。就算不能换，她至少应该问一下我们再给炒
一下可以不可以。不能这样摔打吧？
估计服务员也知道自己对我们态度过于恶劣，过了2分钟，是另外一个服务员端上来的，再吃，里面加了不知道多少辣酱，豆豉酱，里面的蒜苗也变了颜
色，不仅辣的不行简直就是剩菜的味道，猪肉还是腥，问，说，没办法
，做出来的就是这样。再问，说第一次炒得不是大师傅，这次加了点料，让大师傅又炒
了一次。问题是你换人不换料，还是那味儿阿。想加辣把味儿盖住那也不成啊。把老板
找来，上来就跟我们胡搅蛮缠，说听说过鱼腥没听说过肉也能腥的，我说你就是回锅
加猛料，这么辣怎么吃？他说回锅肉就是辣的，要不我给你上白水煮的回锅肉？问能不能换一个，说要换一个菜是不可能的。气得
我当时真的是无语，一句话说不出来，他发完火甩手就走了，把我们凉在那里，气得
我们最后夫妻肺片没吃完，还要付钱才走，饭没吃，生了一肚子气。
怪就怪我当时就应该坚持不去新川粤，上次法帖的又不是别人，是老公的球友，本来
老公踢球回来还跟我讲来者，我们倆回想从这个店开到现在2年了，去了不下100 次
，确实有些时候，干锅鱼是小碎的，根本没有成大块的鱼，辣子鸡里是渣渣，没有
大块的，估计那种情况就是遇到剩菜回锅的。看来真是不能对新川粤抱一线希望，吃
剩菜不说还受气，在美国这么久就没受过这气，我们不在乎这个菜钱，关键是他们的
态度太过分了，欺负大陆的么。
其实归根结底，新川粤的特点就是容不得顾客对他们有意见或者建议，千万不能说他们
的菜哪次炒得不对口了，否则就是对他们的大不敬。有一次我们还说大家都是中国人，
提点建议是为了让你们更好，后来，才知道是台独，并不把自己当中国人看的。

R*Q2013-09-26 07:09

2 楼

还不知道结果，披个马甲攒人品吧
1. 二叉树的序列化和反序列化，节点的value是String类型
2. 找两个排好序的list的共同元素
5 -> 6 -> 6 ->8
4 -> 4-> 6 -> 6 -> 8
答案是 6 -> 6 -> 8
两个list长度差不多是怎么做？长度相差非常大时如何做？
3. 有一个字典因为某种原因每个字符都被替换成一个别的字符了（但还是一一对应)，
但是单词的顺序没有改变，比如
cat
coffee
common
变成了
dkc
dbhhzz
dbllbq
让找出的这个替换的规则（guaranteed to have a unique one)
4. 二叉树找中序后继
设计一个算法，在分布式系统中拷贝某一个节点上的某一个文件到其他所有的节点上，
要考虑时间代价和fault tolerance
5. 给定两个list of integer，问是否他们是否互相是对方的一个从排列
follow up: 如果不停的有新的list of integer过来，问是否这一列数以前出现过。
怎么存储？怎么查询？复杂度？

c*a2013-09-26 07:09

3 楼

bless!

【在 R*Q 的大作中提到】

: 还不知道结果，披个马甲攒人品吧
: 1. 二叉树的序列化和反序列化，节点的value是String类型
: 2. 找两个排好序的list的共同元素
: 5 -> 6 -> 6 ->8
: 4 -> 4-> 6 -> 6 -> 8
: 答案是 6 -> 6 -> 8
: 两个list长度差不多是怎么做？长度相差非常大时如何做？
: 3. 有一个字典因为某种原因每个字符都被替换成一个别的字符了（但还是一一对应)，
: 但是单词的顺序没有改变，比如
: cat

l*y2013-09-26 07:09

4 楼

这么一比，我好弱啊。

t*h2013-09-26 07:09

5 楼

还行啊非常reasonable

【在 R*Q 的大作中提到】

: 还不知道结果，披个马甲攒人品吧
: 1. 二叉树的序列化和反序列化，节点的value是String类型
: 2. 找两个排好序的list的共同元素
: 5 -> 6 -> 6 ->8
: 4 -> 4-> 6 -> 6 -> 8
: 答案是 6 -> 6 -> 8
: 两个list长度差不多是怎么做？长度相差非常大时如何做？
: 3. 有一个字典因为某种原因每个字符都被替换成一个别的字符了（但还是一一对应)，
: 但是单词的顺序没有改变，比如
: cat

M*g2013-09-26 07:09

6 楼

请问是ONSITE吗？还是电面？

m*e2013-09-26 07:09

7 楼

第一和第二题知道怎么解，剩下几个还没有idea。可不可以讲讲3，4，5都怎么解的

【在 t*********h 的大作中提到】

: 还行啊非常reasonable

p*22013-09-26 07:09

8 楼

第二题
(def a '(5 6 6 8))
(def b '(4 4 6 6 8))
(defn f [a, b, c]
(let [aa (first a) bb (first b)]
(if (and aa bb)
(cond
(< aa bb) (f (rest a) b c)
(> aa bb) (f a (rest b) c)
:default (f (rest a) b (cons aa c)))
c)))
(println (reverse (f a b ()) ))

【在 m**********e 的大作中提到】

: 第一和第二题知道怎么解，剩下几个还没有idea。可不可以讲讲3，4，5都怎么解的

w*j2013-09-26 07:09

9 楼

不算太难
bless

p*o2013-09-26 07:09

10 楼

cool. 什么编程语言？第二题, 上个c++:
using namespace std;
list intersect(list intList1, list intList2){
list::const_iterator it1 = intList1.begin();
list::const_iterator it2 = intList2.begin();
list intList3;
while((it1 != intList1.end()) && (it2 != intList2.end())) {
if (*it1 == *it2) {
intList3.push_back(*it1);
++it1;
++it2;
} else if (*it1 < *it2) {
++it1;
} else {
++it2;
}
}
return intList3;
}
};
// test case
int main()
{
int ints1[] = {5, 6, 6, 8};
int ints2[] = {4, 4, 6, 6, 8};
list list1 (ints1, ints1 + sizeof(ints1) / sizeof(int) );
list list2 (ints2, ints2 + sizeof(ints2) / sizeof(int) );
list list3 = intersect(list1, list2);
for(list::const_iterator it=list3.begin(); it!=list3.end(); ++it) {
cout << *it << endl;
}
}
第三题, 不知道有什么门道，按要求直接写了一个，不知道是不是太麻烦了
#include
#include
#include
using namespace std;
typedef map Table;
typedef list StrList;
typedef list::const_iterator ItList;
typedef string::iterator ItStr;
class Solution {
public:
Table findTable(StrList strList1, StrList strList2){
Table table;
for(ItList it1=strList1.begin(), it2=strList2.begin();
it1 != strList1.end(), it2 != strList2.end(); ++it1, ++it2) {
string str1 = *it1;
string str2 = *it2;
for(ItStr itstr1 = str1.begin(), itstr2 = str2.begin();
itstr1 != str1.end(), itstr2 != str2.end(); ++itstr1, ++
itstr2) {
table[*itstr1] = *itstr2;
}
}
return table;
}
};
// test case
int main()
{
Table table;
StrList strList1;
strList1.push_back("cat");
strList1.push_back("coffee");
strList1.push_back("common");
StrList strList2;
strList2.push_back("dkc");
strList2.push_back("dbhhzz");
strList2.push_back("dbllbq");
Solution s;
table = s.findTable(strList1, strList2);
for(Table::const_iterator it=table.begin();it!=table.end();++it) {
cout << it->first << "->" << it->second <}
}

【在 p*****2 的大作中提到】

:
: 第二题
: (def a '(5 6 6 8))
: (def b '(4 4 6 6 8))
: (defn f [a, b, c]
: (let [aa (first a) bb (first b)]
: (if (and aa bb)
: (cond
: (< aa bb) (f (rest a) b c)
: (> aa bb) (f a (rest b) c)

f*b2013-09-26 07:09

11 楼

第三题应该只给你变化后的字典吧。

【在 p****o 的大作中提到】

: cool. 什么编程语言？第二题, 上个c++:
: using namespace std;
: list intersect(list intList1, list intList2){
: list::const_iterator it1 = intList1.begin();
: list::const_iterator it2 = intList2.begin();
: list intList3;
: while((it1 != intList1.end()) && (it2 != intList2.end())) {
: if (*it1 == *it2) {
: intList3.push_back(*it1);
: ++it1;

s*w2013-09-26 07:09

12 楼

这个第二题解的很棒，我记得在哪里看过一个差点的解法：先 merge 同时加一个标签
，然后再扫一遍，看相邻标签是否不一样
一个表很长，另一个很短的情况下，似乎该用　hash table（或者 bloom filter , 如
果能容忍少量错误）　存短表，扫描长表。有没有更好的办法？
第三题估计不是要求查表，是手动找规律

【在 p****o 的大作中提到】

: cool. 什么编程语言？第二题, 上个c++:
: using namespace std;
: list intersect(list intList1, list intList2){
: list::const_iterator it1 = intList1.begin();
: list::const_iterator it2 = intList2.begin();
: list intList3;
: while((it1 != intList1.end()) && (it2 != intList2.end())) {
: if (*it1 == *it2) {
: intList3.push_back(*it1);
: ++it1;

m*e2013-09-26 07:09

13 楼

第3，第4还是没有搞清怎么做。哪位大侠指点下？
第5题我写了一个C#的：
// Determine whether 2 arrays have the same elements with different
orders.
public bool CommonArray(int[] intArrayA, int[] intArrayB)
{
Dictionary dict = new Dictionary();
int n = intArrayA.Length;
int m = intArrayB.Length;
int i;
for (i = 0; i < n; ++i)
{
int value;
if (dict.TryGetValue(intArrayA[i], out value))
{
value++;
dict[intArrayA[i]] = value;
}
else
{
dict.Add(intArrayA[i], 1);
}
}
for (i = 0; i < m; ++i)
{
int value;
if (dict.TryGetValue(intArrayA[i], out value))
{
value--;
dict[intArrayA[i]] = value;
}
else
{
return false;
}
}
foreach (var item in dict)
{
if (item.Value != 0)
{
return false;
}
}
return true;
}

【在 s*w 的大作中提到】

: 这个第二题解的很棒，我记得在哪里看过一个差点的解法：先 merge 同时加一个标签
: ，然后再扫一遍，看相邻标签是否不一样
: 一个表很长，另一个很短的情况下，似乎该用　hash table（或者 bloom filter , 如
: 果能容忍少量错误）　存短表，扫描长表。有没有更好的办法？
: 第三题估计不是要求查表，是手动找规律

l*n2013-09-26 07:09

14 楼

第三题，又见toposort。

【在 R*Q 的大作中提到】

: 还不知道结果，披个马甲攒人品吧
: 1. 二叉树的序列化和反序列化，节点的value是String类型
: 2. 找两个排好序的list的共同元素
: 5 -> 6 -> 6 ->8
: 4 -> 4-> 6 -> 6 -> 8
: 答案是 6 -> 6 -> 8
: 两个list长度差不多是怎么做？长度相差非常大时如何做？
: 3. 有一个字典因为某种原因每个字符都被替换成一个别的字符了（但还是一一对应)，
: 但是单词的顺序没有改变，比如
: cat

l*n2013-09-26 07:09

15 楼

第二题除非是ArrayList，否则怎么搞都绕不过List的O(n)限制啊。

【在 R*Q 的大作中提到】

: 还不知道结果，披个马甲攒人品吧
: 1. 二叉树的序列化和反序列化，节点的value是String类型
: 2. 找两个排好序的list的共同元素
: 5 -> 6 -> 6 ->8
: 4 -> 4-> 6 -> 6 -> 8
: 答案是 6 -> 6 -> 8
: 两个list长度差不多是怎么做？长度相差非常大时如何做？
: 3. 有一个字典因为某种原因每个字符都被替换成一个别的字符了（但还是一一对应)，
: 但是单词的顺序没有改变，比如
: cat

e*s2013-09-26 07:09

16 楼

马克

s*g2013-09-26 07:09

17 楼

学习学习
4

g*n2013-09-26 07:09

18 楼

lz,最后一题没理解,能不能举个例子?
谢谢

【在 R*Q 的大作中提到】

: 还不知道结果，披个马甲攒人品吧
: 1. 二叉树的序列化和反序列化，节点的value是String类型
: 2. 找两个排好序的list的共同元素
: 5 -> 6 -> 6 ->8
: 4 -> 4-> 6 -> 6 -> 8
: 答案是 6 -> 6 -> 8
: 两个list长度差不多是怎么做？长度相差非常大时如何做？
: 3. 有一个字典因为某种原因每个字符都被替换成一个别的字符了（但还是一一对应)，
: 但是单词的顺序没有改变，比如
: cat

m*i2013-09-26 07:09

19 楼

是不是先要得到所有Orig［x］< Orig [y] 的matrix，然后再根据它建立一个
direct graph，
最后做top sort，第一个是‘a'，第二个是’b'， and so on？

【在 l*n 的大作中提到】

: 第三题，又见toposort。

m*i2013-09-26 07:09

20 楼

但是怎么来建matrix 和graph 比较effective呢？不清楚

【在 m*******i 的大作中提到】

: 是不是先要得到所有Orig［x］< Orig [y] 的matrix，然后再根据它建立一个
: direct graph，
: 最后做top sort，第一个是‘a'，第二个是’b'， and so on？

A*g2013-09-26 07:09

21 楼

这是电面？你牛啊，一个小时能做这么多题

g*e2013-09-26 07:09

22 楼

字典那题除了这个被改动的新字典，还有其他已知信息吗？

r*j2013-09-26 07:09

23 楼

第五题可以先把每个list排序

a*a2013-09-26 07:09

24 楼

请问这个用toposort怎么解？能解释一下么？谢谢！

【在 l*n 的大作中提到】

: 第三题，又见toposort。

a*a2013-09-26 07:09

25 楼

4. 二叉树找中序后继
设计一个算法，在分布式系统中拷贝某一个节点上的某一个文件到其他所有的节点上，
要考虑时间代价和fault tolerance
这个是一个题还是两个题？
拷贝那个题，能用multicase么？
5. 给定两个list of integer，问是否他们是否互相是对方的一个从排列
follow up: 如果不停的有新的list of integer过来，问是否这一列数以前出现过。
怎么存储？怎么查询？复杂度？
还是不太明白“从排列”是怎么定义的。。。
1 2 3 4 和2 4，算从排列么？

【在 R*Q 的大作中提到】

: 还不知道结果，披个马甲攒人品吧
: 1. 二叉树的序列化和反序列化，节点的value是String类型
: 2. 找两个排好序的list的共同元素
: 5 -> 6 -> 6 ->8
: 4 -> 4-> 6 -> 6 -> 8
: 答案是 6 -> 6 -> 8
: 两个list长度差不多是怎么做？长度相差非常大时如何做？
: 3. 有一个字典因为某种原因每个字符都被替换成一个别的字符了（但还是一一对应)，
: 但是单词的顺序没有改变，比如
: cat

l*n2013-09-26 07:09

26 楼

比如
cat
coffee
common
变成了
dkc
dbhhzz
dbllbq
那么就有k需要你排出个“身高”顺序来。最小的就是a，最大的就是z。

【在 a*****a 的大作中提到】

: 请问这个用toposort怎么解？能解释一下么？谢谢！

d*n2013-09-26 07:09

27 楼

Interesting，可是原题好像没有说新的单词也是按原单词的顺序sort的呀？

【在 l*n 的大作中提到】

: 比如
: cat
: coffee
: common
: 变成了
: dkc
: dbhhzz
: dbllbq
: 那么就有k: 需要你排出个“身高”顺序来。最小的就是a，最大的就是z。

R*Q2013-09-26 07:09

28 楼

因为签了NDA，题目不便说的太细，简要回答一下上面各楼的问题
.是onsite一共五轮
.第三题topological sort是正确的方向，楼上有版友已经给出了不错的解释
.语言其实无所谓，这些题没有什么语言相关的
.第五题的重排列就是说两列数除了顺序可能不同元素完全相同
.第四个没说清楚应该说是两道题，找中序后继要求写代码，设计算法那个不用

【在 R*Q 的大作中提到】

: 还不知道结果，披个马甲攒人品吧
: 1. 二叉树的序列化和反序列化，节点的value是String类型
: 2. 找两个排好序的list的共同元素
: 5 -> 6 -> 6 ->8
: 4 -> 4-> 6 -> 6 -> 8
: 答案是 6 -> 6 -> 8
: 两个list长度差不多是怎么做？长度相差非常大时如何做？
: 3. 有一个字典因为某种原因每个字符都被替换成一个别的字符了（但还是一一对应)，
: 但是单词的顺序没有改变，比如
: cat

p*32013-09-26 07:09

29 楼

"两个排好序的list", 你确定是list不是array??
最后一题排序然后trie??

【在 R*Q 的大作中提到】

: 还不知道结果，披个马甲攒人品吧
: 1. 二叉树的序列化和反序列化，节点的value是String类型
: 2. 找两个排好序的list的共同元素
: 5 -> 6 -> 6 ->8
: 4 -> 4-> 6 -> 6 -> 8
: 答案是 6 -> 6 -> 8
: 两个list长度差不多是怎么做？长度相差非常大时如何做？
: 3. 有一个字典因为某种原因每个字符都被替换成一个别的字符了（但还是一一对应)，
: 但是单词的顺序没有改变，比如
: cat

p*22013-09-26 07:09

30 楼

第五题
(defn f [list1, list2]
(= (sort list1) (sort list2)))
(f '(1 3 2 4) '(2 4 1 3))

p*22013-09-26 07:09

31 楼

第五题第二问
(defn isPresent [lists, list]
(contains? lists (sort list)))
(defn add [lists, list]
(conj lists (sort list)))

m*e2013-09-26 07:09

32 楼

你的第四个题还是没有明白什么意思。什么是二叉树找中序后序？是给一个二叉树，让
输出一个中序序列，还有再输出一个后序序列？
第四题设计算法的题你是怎么回答的？

【在 R*Q 的大作中提到】

: 因为签了NDA，题目不便说的太细，简要回答一下上面各楼的问题
: .是onsite一共五轮
: .第三题topological sort是正确的方向，楼上有版友已经给出了不错的解释
: .语言其实无所谓，这些题没有什么语言相关的
: .第五题的重排列就是说两列数除了顺序可能不同元素完全相同
: .第四个没说清楚应该说是两道题，找中序后继要求写代码，设计算法那个不用

s*n2013-09-26 07:09

33 楼

排序的话代价略高了，如果用Hashmap来做的话是O(n)的，如果有很多很多的Incoming
list的话，最好的办法应该是先计算整个list的hash code(比如sha1, md5)，效率高很多

【在 p*****2 的大作中提到】

: 第五题
: (defn f [list1, list2]
: (= (sort list1) (sort list2)))
: (f '(1 3 2 4) '(2 4 1 3))

l*o2013-09-26 07:09

34 楼

第五题有什么理由不用minimum slide window吗？

a*a2013-09-26 07:09

35 楼

哦，明白了，多谢指点！我一开始忘记字典里词都是有序的。。。 -__-
这样确实是用toposort就可以解，也不需要旧词典信息。看了toposort还是很重要的，
需要仔细扣一下的呢。我还以为属于有点儿偏不太会考的呢。唉，学习无止境啊。

【在 l*n 的大作中提到】

: 比如
: cat
: coffee
: common
: 变成了
: dkc
: dbhhzz
: dbllbq
: 那么就有k: 需要你排出个“身高”顺序来。最小的就是a，最大的就是z。

a*92013-09-26 07:09

36 楼

原来如此！新词典也是排好了的！感谢！

【在 l*n 的大作中提到】

: 比如
: cat
: coffee
: common
: 变成了
: dkc
: dbhhzz
: dbllbq
: 那么就有k: 需要你排出个“身高”顺序来。最小的就是a，最大的就是z。

a*92013-09-26 07:09

37 楼

第一问数char的个数？
第二问先排序再放进hashtable？

【在 p*****2 的大作中提到】

: 第五题第二问
: (defn isPresent [lists, list]
: (contains? lists (sort list)))
: (defn add [lists, list]
: (conj lists (sort list)))