G新鲜面经 - 未名空间MITBBS历史存档

f*l2013-10-10 07:10

1 楼

1.1 gas station
1.2 一个数组，找出一个solution使得1st《2nd， 2nd》3rd。。比如15462就是数组1
，2，4，5，6的一个solution。大牛指点下这个怎么弄？
2. most frequent character in a huge string (10works 1master)，如果一个big
文件在一个机子上怎么弄，如果多个小文件在多个机子上怎么弄？
3.1. return random node of a list, what if it can be modified concurrently
3.2. 1k Ads, how to make it only appear once across all servers, no master
server
4.check generalized tree, follow up:return all generalized tree of its
children，比如
1
2 3
4 5 6
这种情况下，2，4，5，6是valid的节点。
5.how to design general cache

f*l2013-10-10 07:10

2 楼

如果大家那个题我没说明白，请跟贴，讨论提高一下，我估计是跪了。。。

z*82013-10-10 07:10

3 楼

题目真心难
1.2没看懂？
4 什么是generalized tree?

J*32013-10-10 07:10

4 楼

能再说下第二题吗？没看懂啊

f*l2013-10-10 07:10

5 楼

1.2 就是说一个数组，找一个序列，使得第一个小于第二个，第二个大于第三个，第三
个小于第四个，第四个大于第五个。。一个大牛的解法是先sort，然后头尾分别取，这
个应该work。但follow up是如何返回所有的valid序列，这个我没打上来。
4. generalized tree其实就是一个list，就是说，树上任何一个节点，如果至多只有
一个child，那么就是valid的结果。很明显所有的leaf节点都满足，我上面的例子中，
2也符合，因为他只有一个child，其他节点1和3不符合，因为他们都有两个子节点。

b*52013-10-10 07:10

6 楼

5. generalized cache? 你怎么说的，就是说， array+linkedlist to resolve
collision, or array + double hashing to resolve collision?
3.2. 1k Ads, how to make it only appear once across all servers, no master
server? consistent hashing?
3.1 如果一个big文件在一个机子上怎么弄?
split up the file?
如果多个小文件在多个机子上怎么弄？
map reduce?

J*32013-10-10 07:10

7 楼

哦哦理解了感觉是LIS的变体吧第一问是找最长的吗？

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

: 1.2 就是说一个数组，找一个序列，使得第一个小于第二个，第二个大于第三个，第三
: 个小于第四个，第四个大于第五个。。一个大牛的解法是先sort，然后头尾分别取，这
: 个应该work。但follow up是如何返回所有的valid序列，这个我没打上来。
: 4. generalized tree其实就是一个list，就是说，树上任何一个节点，如果至多只有
: 一个child，那么就是valid的结果。很明显所有的leaf节点都满足，我上面的例子中，
: 2也符合，因为他只有一个child，其他节点1和3不符合，因为他们都有两个子节点。

b*e2013-10-10 07:10

8 楼

1.2, If I understand the question..
method 1. sort first, take second half intertwine first half. O(nlog(n))
speed.
method 2, (similar to method 1) use a heap, pop assign to even index, then
pop assign to odd index. O(n)
method 3, one pass, heapify, pop first assign to 1, then pop two, assign
larger one first, continue. O(n) one pass.
method 4, O(n), one pass constant space, look at i and i+1, if i is even and
A[i] > A[i+1] swap two value, if i is odd and A[i] < A[i+1] swap two value.
so method 4 is best possible...

c*p2013-10-10 07:10

9 楼

mark

g*e2013-10-10 07:10

10 楼

是onsite吗？

1
big

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

: 1.1 gas station
: 1.2 一个数组，找出一个solution使得1st《2nd， 2nd》3rd。。比如15462就是数组1
: ，2，4，5，6的一个solution。大牛指点下这个怎么弄？
: 2. most frequent character in a huge string (10works 1master)，如果一个big
: 文件在一个机子上怎么弄，如果多个小文件在多个机子上怎么弄？
: 3.1. return random node of a list, what if it can be modified concurrently
: 3.2. 1k Ads, how to make it only appear once across all servers, no master
: server
: 4.check generalized tree, follow up:return all generalized tree of its
: children，比如

l*n2013-10-10 07:10

11 楼

1.2应该是个combination题目吧。任选三个数，比如156,然后1<6,6>5，但是要求5，2},所以fail之，继续新组合。recursion+backtracking。

1
big

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

: 1.1 gas station
: 1.2 一个数组，找出一个solution使得1st《2nd， 2nd》3rd。。比如15462就是数组1
: ，2，4，5，6的一个solution。大牛指点下这个怎么弄？
: 2. most frequent character in a huge string (10works 1master)，如果一个big
: 文件在一个机子上怎么弄，如果多个小文件在多个机子上怎么弄？
: 3.1. return random node of a list, what if it can be modified concurrently
: 3.2. 1k Ads, how to make it only appear once across all servers, no master
: server
: 4.check generalized tree, follow up:return all generalized tree of its
: children，比如

l*n2013-10-10 07:10

12 楼

我觉得每个题目都要从数学上去找精细的optimum信息，就真变成数学题了。还是保持
cs思维的好。

and
value.

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

: 1.2, If I understand the question..
: method 1. sort first, take second half intertwine first half. O(nlog(n))
: speed.
: method 2, (similar to method 1) use a heap, pop assign to even index, then
: pop assign to odd index. O(n)
: method 3, one pass, heapify, pop first assign to 1, then pop two, assign
: larger one first, continue. O(n) one pass.
: method 4, O(n), one pass constant space, look at i and i+1, if i is even and
: A[i] > A[i+1] swap two value, if i is odd and A[i] < A[i+1] swap two value.
: so method 4 is best possible...

f*b2013-10-10 07:10

13 楼

老见你mark，工作找的怎么样了？

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

: mark

x*u2013-10-10 07:10

14 楼

非牛人. 供讨论.
1.2 一个数组，找出一个solution使得1st《2nd， 2nd》3rd。。比如15462就是数组1
，2，4，5，6的一个solution。
从结果到条件往前推:
结果: aceg
分开来看:
ab>c>e>g
明显, b是一个特殊的数, 它大于一半的数, 小于一半的数. 所以b应该是中数. a应该
是b之前的一个数.
d and f 应该是中数后面的数; c,e,g 应该是中数前面的数.
那这样的分析后, 我们可以这么做:
1. 把input array先sort.
2. 把中数和中数前的数挑出来, 做b and a.
3. 中数后面的数挑出来做 d, f, ...
4. 中数前面的数挑出来做 c, e, g, ...
5. interleave 3 and 4
example:
1，2，3, 4，5，6, 7, 8
A. let b be 5, a be 4
B. 4<5<6<7<8
C. 5>3>2>1
interleave 后.
4<5>3<6>2<7>1<8

l*n2013-10-10 07:10

15 楼

1
b>c && c
【在 x********u 的大作中提到】

: 非牛人. 供讨论.
: 1.2 一个数组，找出一个solution使得1st《2nd， 2nd》3rd。。比如15462就是数组1
: ，2，4，5，6的一个solution。
: 从结果到条件往前推:
: 结果: aceg
: 分开来看:
: a: b>c>e>g
: 明显, b是一个特殊的数, 它大于一半的数, 小于一半的数. 所以b应该是中数. a应该
: 是b之前的一个数.

t*r2013-10-10 07:10

16 楼

这是onsite?

1
big

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

: 1.1 gas station
: 1.2 一个数组，找出一个solution使得1st《2nd， 2nd》3rd。。比如15462就是数组1
: ，2，4，5，6的一个solution。大牛指点下这个怎么弄？
: 2. most frequent character in a huge string (10works 1master)，如果一个big
: 文件在一个机子上怎么弄，如果多个小文件在多个机子上怎么弄？
: 3.1. return random node of a list, what if it can be modified concurrently
: 3.2. 1k Ads, how to make it only appear once across all servers, no master
: server
: 4.check generalized tree, follow up:return all generalized tree of its
: children，比如

x*u2013-10-10 07:10

17 楼

3.1. return random node of a list, what if it can be modified concurrently
每个node上有个object lock.

x*u2013-10-10 07:10

18 楼

3.2. 1k Ads, how to make it only appear once across all servers, no master
server
1K % numberOfMachine => index of machine to save the Ads.
每个机器上同时 maintain 一份(AdsIndex, machineIndex)的hashtable.
这个需要做syncrhonization的.

l*n2013-10-10 07:10

19 楼

仔细考虑了下，1.2这么做比较简单：就是把数组遍历一遍，但是每次要调头，如果调
头的时候没有候选了就fail.
写了个java的code
[1,2,4,5,6]给出的所有结果是
[1, 4, 2, 6, 5]
[1, 5, 4, 6, 2]
[1, 5, 2, 6, 4]
[1, 6, 4, 5, 2]
[1, 6, 2, 5, 4]
[2, 4, 1, 6, 5]
[2, 5, 4, 6, 1]
[2, 5, 1, 6, 4]
[2, 6, 4, 5, 1]
[2, 6, 1, 5, 4]
[4, 5, 2, 6, 1]
[4, 5, 1, 6, 2]
[4, 6, 2, 5, 1]
[4, 6, 1, 5, 2]
[5, 6, 2, 4, 1]
[5, 6, 1, 4, 2]
List> reorder(int[] arr) {
assert (arr != null);
Arrays.sort(arr);
List> ol = new ArrayList>();
for (int i = 0; i < arr.length; i++) {
boolean[] visited = new boolean[arr.length];
List curr = new ArrayList();
visited[i] = true;
curr.add(arr[i]);
traverse(arr, i, true, visited, curr, ol);
}
return ol;
}
void traverse(int[] arr, int i, boolean toRight, boolean[] visited,
List curr, List> ol) {
if (curr.size() == arr.length) {
ol.add(new ArrayList(curr));
return;
}
if (toRight) {
int j = i + 1;
while (j < arr.length) {
if (!visited[j]) {
visited[j] = true;
curr.add(arr[j]);
traverse(arr, j, !toRight, visited, curr, ol);
curr.remove(curr.size() - 1);
visited[j] = false;
}
j++;
}
} else {
int j = i - 1;
while (j >= 0) {
if (!visited[j]) {
visited[j] = true;
curr.add(arr[j]);
traverse(arr, j, !toRight, visited, curr, ol);
curr.remove(curr.size() - 1);
visited[j] = false;
}
j--;
}
}
}

1
big

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

: 1.1 gas station
: 1.2 一个数组，找出一个solution使得1st《2nd， 2nd》3rd。。比如15462就是数组1
: ，2，4，5，6的一个solution。大牛指点下这个怎么弄？
: 2. most frequent character in a huge string (10works 1master)，如果一个big
: 文件在一个机子上怎么弄，如果多个小文件在多个机子上怎么弄？
: 3.1. return random node of a list, what if it can be modified concurrently
: 3.2. 1k Ads, how to make it only appear once across all servers, no master
: server
: 4.check generalized tree, follow up:return all generalized tree of its
: children，比如

b*52013-10-10 07:10

20 楼

why do we need to maintain a hashtable? if we already know which machine we
will save the ad?

【在 x********u 的大作中提到】

: 3.2. 1k Ads, how to make it only appear once across all servers, no master
: server
: 1K % numberOfMachine => index of machine to save the Ads.
: 每个机器上同时 maintain 一份(AdsIndex, machineIndex)的hashtable.
: 这个需要做syncrhonization的.

c*p2013-10-10 07:10

21 楼

找不到。

【在 f*******b 的大作中提到】

:
: 老见你mark，工作找的怎么样了？

f*l2013-10-10 07:10

22 楼

First of all，是onsite，被5人轮虐。。。好在lunch哥们比较腼腆，没问问题，就
扯扯淡。

@beefcurtain5
5.不好意思没说清楚，generialezed cahce只是design方法的signature，比如get
(K), put(K,V)，这个我也是乱答，感觉出了get，put，clear之类不需要别的。。
3.2 我答的也是consistent hashing
3.1 这个题分之前需要做hash吗，不用话貌似得check所有的文件每一行，做了的
话貌似只看每个最大就可以。

@Jc2013
不是找最长。。就是找一个符合要求的序列就行，要求所有数组元素都在。

@bladehaze
这么多解法，眼花缭乱啊，不过方法4怎么感觉不是O（n），数组swap貌似代价粉
大。。用堆的想法不错，学习了，呵呵。

@xiaofenglu
1.2 分析过程很清晰！赞一个！
3.1 这个不要用lock。。。用了就掉进陷阱。。。就try catch一下，如果
exception继续取一次就好。
3.2 万一某个server挂了，如何让他负责的Ad继续由别的server发？你那个
hashtable维护起来很tricky的。。。所以我觉得consisten hashing应该是对的。

@Icn
1.2 上代码就比谈想法更进一步，呵呵，interviewer自己说的。。。

f*l2013-10-10 07:10

23 楼

继续召唤大牛指点4和5。。。

b*e2013-10-10 07:10

24 楼

Thanks for sharing..
code for question 1.2
void transform(int A[], int n){
if(n<=1) return;
for(int i = 0 ; i < n-1 ; ++i)
if((i%2=0 && A[i] > A[i+1]) ||(i%2=1 && A[i] < A[i+1]))
std::swap(A[i],A[i+1]);
}
A couple of questions though.
question 2 producer-consumer? producer read files by chunks, push to a queue
, a couple of consumer record statistics and combine result when done?
question 3.1, "random" means 1)any, 2)uniformly distributed, or 3) any
specified index.
Still don't understand question 4...
given the example, what's the correct output? a list of valid nodes?

s*e2013-10-10 07:10

25 楼

1.2 暴力加剪枝
vector used;
void transform(vector A, vector& vec){
int i=vec.size()-1;
if (i>0) {
if (( i&1 && vec[i] < vec[i-1]) ||
(!(i&1) && vec[i] > vec[i-1])) return;
}
if (vec.size()==A.size()) {
for(int i = 0 ; i < vec.size() ; ++i) cout<cout<return;
}
for(int i = 0 ; i < A.size() ; ++i) {
if (!used[i]) {
used[i] = true;
vec.push_back(A[i]);
transform(A, vec);
vec.pop_back();
used[i] = false;
}
}
}
1 4 2 6 5
1 5 2 6 4
1 5 4 6 2
1 6 2 5 4
1 6 4 5 2
2 4 1 6 5
2 5 1 6 4
2 5 4 6 1
2 6 1 5 4
2 6 4 5 1
4 5 1 6 2
4 5 2 6 1
4 6 1 5 2
4 6 2 5 1
5 6 1 4 2
5 6 2 4 1

1
big

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

: 1.1 gas station
: 1.2 一个数组，找出一个solution使得1st《2nd， 2nd》3rd。。比如15462就是数组1
: ，2，4，5，6的一个solution。大牛指点下这个怎么弄？
: 2. most frequent character in a huge string (10works 1master)，如果一个big
: 文件在一个机子上怎么弄，如果多个小文件在多个机子上怎么弄？
: 3.1. return random node of a list, what if it can be modified concurrently
: 3.2. 1k Ads, how to make it only appear once across all servers, no master
: server
: 4.check generalized tree, follow up:return all generalized tree of its
: children，比如

h*a2013-10-10 07:10

26 楼

请问为什么3.1,lock是陷阱？
这种情况下我首先想到的就是用lock的思路？

get

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

: First of all，是onsite，被5人轮虐。。。好在lunch哥们比较腼腆，没问问题，就
: 扯扯淡。
:
: @beefcurtain5
: 5.不好意思没说清楚，generialezed cahce只是design方法的signature，比如get
: (K), put(K,V)，这个我也是乱答，感觉出了get，put，clear之类不需要别的。。
: 3.2 我答的也是consistent hashing
: 3.1 这个题分之前需要做hash吗，不用话貌似得check所有的文件每一行，做了的
: 话貌似只看每个最大就可以。
:

f*42013-10-10 07:10

27 楼

1.2
a_1 < a_2 > a_3, 这里a_1和a_3应该没有大小关系
可用顺序统计数分为前后两半,前半5
hash + double linked list

1
big

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

: 1.1 gas station
: 1.2 一个数组，找出一个solution使得1st《2nd， 2nd》3rd。。比如15462就是数组1
: ，2，4，5，6的一个solution。大牛指点下这个怎么弄？
: 2. most frequent character in a huge string (10works 1master)，如果一个big
: 文件在一个机子上怎么弄，如果多个小文件在多个机子上怎么弄？
: 3.1. return random node of a list, what if it can be modified concurrently
: 3.2. 1k Ads, how to make it only appear once across all servers, no master
: server
: 4.check generalized tree, follow up:return all generalized tree of its
: children，比如

e*l2013-10-10 07:10

28 楼

thx

m*n2013-10-10 07:10

29 楼

对1.2有个想法：
首先做1到n-1，然后把这个模式用上去。举个例子：
已经有了14253，要加6
最后一位是3，所以后面的要比3大。
把4换出来（比4大的都+1），成为：15263，在后面加4：152634
把5换出来（比5大的都+1），成为：14263，在后面加5：142635

1
big

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

: 1.1 gas station
: 1.2 一个数组，找出一个solution使得1st《2nd， 2nd》3rd。。比如15462就是数组1
: ，2，4，5，6的一个solution。大牛指点下这个怎么弄？
: 2. most frequent character in a huge string (10works 1master)，如果一个big
: 文件在一个机子上怎么弄，如果多个小文件在多个机子上怎么弄？
: 3.1. return random node of a list, what if it can be modified concurrently
: 3.2. 1k Ads, how to make it only appear once across all servers, no master
: server
: 4.check generalized tree, follow up:return all generalized tree of its
: children，比如

j*i2013-10-10 07:10

30 楼

1.2可以用toposort做吧。每个位置代表一个节点，大于号代表有向线段。整个图肯定
是无环的。做完拓扑排序之后按照节点的排序顺序从大到小填数就行了，O(n)复杂度。

v*n2013-10-10 07:10

31 楼

不是很明白这个解法，可以详细说一下吗？

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

: 1.2可以用toposort做吧。每个位置代表一个节点，大于号代表有向线段。整个图肯定
: 是无环的。做完拓扑排序之后按照节点的排序顺序从大到小填数就行了，O(n)复杂度。

j*i2013-10-10 07:10

32 楼

用[x]表示第x个空位，假设要填入的数已经排序（这里直接用从1到n几个数表示）
将[1] < [2] > [3] < [4]转化为有向无环图[1] [3] 将此图拓扑排序，排序的结果是对每一个箭头其起始端的节点都在其终端节点前出现。
一种排序结果是
[2] [4] [1] [3]
因为箭头起点的位置放的数一定比箭头终点放的数大，只要将数从大到小和排序结果对
应起来就行
[2] [4] [1] [3]
4 3 2 1
转化回原来的不等式
2 < 4 > 1 < 3
具体到这个题，因为节点之间的关系很简单，拓扑排序的方式也很简单，如果计算每个
节点的indegree，可以发现是
1 0 2 0 2 0 ... 2 0 1
因此数字从大到小首先填入indegree是0的节点，一次更新indegree后发现所有剩下来
的节点的
indegree都成了0，于是剩下的数再填入余下的节点。
如果要求打印出所有的可能，这道题就转化为了
如果n = 2m，将n个数中较大的m个做permutation放在第2、4、6...2m个节点，将剩下
来较小的m个数做permutation放在第1、3、5...2m-1个节点
如果n = 2m + 1，将较大的m+1个数做permutation放在第2、4、6...2m节点，剩下的m
个数做permutation放在1、3、5...2m+1节点。

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

: 不是很明白这个解法，可以详细说一下吗？

j*i2013-10-10 07:10

33 楼

不好意思刚才说错了，将入度0的节点填满之后剩下的节点应该也都是入度0了，所以直
接把剩下来的数放进去就行了，已经改了。
而且我理解入度2的数永远存在的啊，按照lz的说法就是往
< > < > < > < .... >
这些空档里面填数啊，只要大于四个空位肯定就有入度2的数了。

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

: 仔细考虑了下，1.2这么做比较简单：就是把数组遍历一遍，但是每次要调头，如果调
: 头的时候没有候选了就fail.
: 写了个java的code
: [1,2,4,5,6]给出的所有结果是
: [1, 4, 2, 6, 5]
: [1, 5, 4, 6, 2]
: [1, 5, 2, 6, 4]
: [1, 6, 4, 5, 2]
: [1, 6, 2, 5, 4]
: [2, 4, 1, 6, 5]

s*n2013-10-10 07:10

34 楼

1.1 gas station
leetcode 原题，找最低谷的点，如果总和大于等于0,则从之后开始，否则－1
1.2 一个数组，找出一个solution使得1st《2nd， 2nd》3rd。。比如15462就是数组1
，2，4，5，6的一个solution。大牛指点下这个怎么弄？
sort后，2,3对换，4,5对换。。。
如果要输出所有的，用递归，然后多加一个parameter bar，第一个元素要小于等于bar
transfer(bar, n) = random1 + random2 + transfer(random2, n-2) (random1<=
random2, random1<=bar)
2. most frequent character in a huge string (10works 1master)，如果一个big
文件在一个机子上怎么弄，如果多个小文件在多个机子上怎么弄？
在一个机子（单核的意思吧？）上就硬来，多个机子就map reduce
3.1. return random node of a list, what if it can be modified concurrently
用hash可以，每个node一个lock也行
我觉得exception不对啊，如果被remove但是没有set to NULL，就没有exception了
3.2. 1k Ads, how to make it only appear once across all servers, no master
server
hash function
4.check generalized tree, follow up:return all generalized tree of its
children，比如
1
2 3
4 5 6
recursive即可
这种情况下，2，4，5，6是valid的节点。
5.how to design general cache
design the number of sets, size of block. Then based on tag, if all sets are
full, use certain mechanism to replace one(LRU)

C*y2013-10-10 07:10

35 楼

3.2求detail
有master的话，可以把hash table放在master上维护。
但是没有master, server之间如何通信，想来想去可以用zookeeper,但是zookeeper也
有master.
大神的意思是？

1
bar
big

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

: 1.1 gas station
: leetcode 原题，找最低谷的点，如果总和大于等于0,则从之后开始，否则－1
: 1.2 一个数组，找出一个solution使得1st《2nd， 2nd》3rd。。比如15462就是数组1
: ，2，4，5，6的一个solution。大牛指点下这个怎么弄？
: sort后，2,3对换，4,5对换。。。
: 如果要输出所有的，用递归，然后多加一个parameter bar，第一个元素要小于等于bar
: transfer(bar, n) = random1 + random2 + transfer(random2, n-2) (random1<=
: random2, random1<=bar)
: 2. most frequent character in a huge string (10works 1master)，如果一个big
: 文件在一个机子上怎么弄，如果多个小文件在多个机子上怎么弄？

e*32013-10-10 07:10

36 楼

new grad?

m*p2013-10-10 07:10

37 楼

楼主真背，应该和HR抱怨一下，太他妈的难了。
这要能全做出来，G能给多少钱？如果没多少钱，你问这么难，不是断自己后路吗。

n*12013-10-10 07:10

38 楼

1.2 奇偶区分有几个高点然后从高到低填满高点剩下的点全排列即可奇数点的时候
注意特殊情况（最大值是最后一个高点第二大值可以不在高点而在数组最后）无需
暴力解法

b*e2013-10-10 07:10

39 楼

-- here's a Haskell solution for 1.2
split [] = [];
split (x:xs) =
[([], x, xs)] ++ [ (x:left, pivot, right) | (left, pivot, right) xs]
up pre [] [] = [pre]
up pre left [] = []
up pre left right =
[ r | (l1, p, r1) down pre [] [] = [pre]
down pre [] right = []
down pre left right =
[ r | (l1, p, r1) go n = down [] [1..n] []

1
big

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

: 1.1 gas station
: 1.2 一个数组，找出一个solution使得1st《2nd， 2nd》3rd。。比如15462就是数组1
: ，2，4，5，6的一个solution。大牛指点下这个怎么弄？
: 2. most frequent character in a huge string (10works 1master)，如果一个big
: 文件在一个机子上怎么弄，如果多个小文件在多个机子上怎么弄？
: 3.1. return random node of a list, what if it can be modified concurrently
: 3.2. 1k Ads, how to make it only appear once across all servers, no master
: server
: 4.check generalized tree, follow up:return all generalized tree of its
: children，比如