www.bestbullysticks.com, 6%, 9/15-17 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>pets - 心有所宠

www.bestbullysticks.com, 6%, 9/15-17

www.bestbullysticks.com, 6%, 9/15-17# pets - 心有所宠

i*p2010-09-15 07:09

1 楼

还是功力不够，fail了。趁着还没忘把面试题记录下来，也算回报版面。
1. multiple sorted list, 求intersection. intersection指list里的值相等。
2. 2D array, 写两个methods: 1) update一个value, 2) sub-array求和。
不同scenario, 如何优化overall performance
3. BST, 每个node知道children和parent. 给定一个node, 求next node. 注：next
node不是child node, 是指next value.
4. 1-9 9个数，取一个数列，满足以下条件：
1）数列长度 >= 4
2) 无重复
3）考虑有这样一个grid:
1 2 3
4 5 6
7 8 9
数列里不能有“中点”, e.g. 1-2-3 is valid, 1-3-2 is not valid, 因为1-3穿过了
2.
写程序找出所有这样的数列。
5. open ended discussion of system design
感想1： #4答得不好，等我理解了他要我干设么已经一半时间过去了, 没有时间
coding了。我再此小人之心，觉得可能interviewer看我不爽，故意没把问题present清
楚，或者说没往正确方向引导我理解。
感想2: 题的总体难度比以前有所下降，但是现在极其注重细节， code里的语法问题也
会被挑剔，以前好像不是这样的。
希望对正在准备的板友们有所帮助。

b*i2010-09-15 07:09

2 楼

For three days only, save 6% on your entire Best Bully Sticks order!
Just type September6 in the coupon code field when ordering. Please remember
to type the code with no spaces, exactly as you see it here, to enjoy even
more savings on our already great prices.
This code is not retroactive and expires at midnight PST on September 17th,
2010.

g*e2010-09-15 07:09

3 楼

第二题有什么特别的地方？是给定任意两个坐标，求该sub matrix的和？
第四题没看懂，不是要长度>=4么，1，2，3怎么valid了

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

: 还是功力不够，fail了。趁着还没忘把面试题记录下来，也算回报版面。
: 1. multiple sorted list, 求intersection. intersection指list里的值相等。
: 2. 2D array, 写两个methods: 1) update一个value, 2) sub-array求和。
: 不同scenario, 如何优化overall performance
: 3. BST, 每个node知道children和parent. 给定一个node, 求next node. 注：next
: node不是child node, 是指next value.
: 4. 1-9 9个数，取一个数列，满足以下条件：
: 1）数列长度 >= 4
: 2) 无重复
: 3）考虑有这样一个grid:

A*n2010-09-15 07:09

4 楼

尚未试过这个，给一个90磅的金毛是否得选
大号的那种？

i*p2010-09-15 07:09

5 楼

是的。
Sorry, 我原来想说的是任何sub数列都要满足这个条件， i.e. 1-2-3-5 is valid, 1-
3-2-5 is not valid.

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

: 第二题有什么特别的地方？是给定任意两个坐标，求该sub matrix的和？
: 第四题没看懂，不是要长度>=4么，1，2，3怎么valid了

b*i2010-09-15 07:09

6 楼

你可以挑那种12”的。
不过我现在只给我儿子吃6”一根的那种。一次最多2根。毕竟都是吃的，我正给他减肥
呢。

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

: 尚未试过这个，给一个90磅的金毛是否得选
: 大号的那种？

h*n2010-09-15 07:09

7 楼

还是没搞懂这个中点是什么意思
是说每行，每列都是个偏序集，给出的数列不能违反其中的顺序？

1-

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

:
: 是的。
: Sorry, 我原来想说的是任何sub数列都要满足这个条件， i.e. 1-2-3-5 is valid, 1-
: 3-2-5 is not valid.

t*u2010-09-15 07:09

8 楼

来福喜欢卷卷的那种

i*p2010-09-15 07:09

9 楼

hehe，看来不是光我一个人confused.
和行列都无关，1-5-9-8也是valid的。

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

: 还是没搞懂这个中点是什么意思
: 是说每行，每列都是个偏序集，给出的数列不能违反其中的顺序？
:
: 1-

y*u2010-09-15 07:09

10 楼

买了，每天２跟磨牙使

g*e2010-09-15 07:09

11 楼

第二题
s(i,j) = sum of submatrix from (0,0), to (i, j).
then the sum of submatrix (a, b), (c,d) (suppose c>a, d>b) is:
sum = s(c,d) - s(c,b) - s(a,d) + s(a,b)
update操作，改变a[i,j]的同时更新s(i,j)
初始化需要的时间O(n^2)，之后的操作都是O(1)
有更好的方法吗？thanks

1-

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

: hehe，看来不是光我一个人confused.
: 和行列都无关，1-5-9-8也是valid的。

b*i2010-09-15 07:09

12 楼

咦，楼上的是你们金毛俱乐部的？呵呵。
90磅，如果不是那种体格大的品种，可有点儿超重了。

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

: 来福喜欢卷卷的那种

g*y2010-09-15 07:09

13 楼

{1, 5, 9, 8} 是有效解的话，就明白了。
就是说，任何一个点都不能在以前点形成的线段上。比如 {1, 9, 5}就违规了。
这个题还有点tricky。

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

: 还是没搞懂这个中点是什么意思
: 是说每行，每列都是个偏序集，给出的数列不能违反其中的顺序？
:
: 1-

g*y2010-09-15 07:09

14 楼

第一个intersection是指对所有sorted list都共同有的数吧？

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

h*n2010-09-15 07:09

15 楼

应该是吧
是不是每个list用一个指针，尽量同步的扫描一遍就可以了

【在 g**********y 的大作中提到】

: 第一个intersection是指对所有sorted list都共同有的数吧？

g*y2010-09-15 07:09

16 楼

应该是，复杂度就是O(N1+N2+...Nk)

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

: 应该是吧
: 是不是每个list用一个指针，尽量同步的扫描一遍就可以了

i*e2010-09-15 07:09

17 楼

第4题难道不是个简单的dfs，记录visited cells就搞定了吗？有那么复杂？请指正，
谢谢。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

i*p2010-09-15 07:09

18 楼

是的。
idea很简单，但是假如list个数未知，coding未必很容易。我最后也只写了2个list,
没有figure out k lists.

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

: 应该是吧
: 是不是每个list用一个指针，尽量同步的扫描一遍就可以了

g*s2010-09-15 07:09

19 楼

validSet 就是去掉当先这个点还有当前这个点和前一个点之间的中点（如果存在的话
并且在
validSet里）。

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

: 第4题难道不是个简单的dfs，记录visited cells就搞定了吗？有那么复杂？请指正，
: 谢谢。
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com

i*p2010-09-15 07:09

20 楼

我也是这么想的。但是则么apply“中点”rule.

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

: 第4题难道不是个简单的dfs，记录visited cells就搞定了吗？有那么复杂？请指正，
: 谢谢。
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com

i*e2010-09-15 07:09

21 楼

1-4-7-3 算对的吗？
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

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

: 我也是这么想的。但是则么apply“中点”rule.

f*42010-09-15 07:09

22 楼

2个list代码写起来还是容易的
k个list的代码想写漂亮了，不容易啊。。。

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

: 应该是吧
: 是不是每个list用一个指针，尽量同步的扫描一遍就可以了

i*p2010-09-15 07:09

23 楼

我也是这么做的。这样update操作是O(n^2).

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

: 第二题
: s(i,j) = sum of submatrix from (0,0), to (i, j).
: then the sum of submatrix (a, b), (c,d) (suppose c>a, d>b) is:
: sum = s(c,d) - s(c,b) - s(a,d) + s(a,b)
: update操作，改变a[i,j]的同时更新s(i,j)
: 初始化需要的时间O(n^2)，之后的操作都是O(1)
: 有更好的方法吗？thanks
:
: 1-

g*y2010-09-15 07:09

24 楼

题目要找出所有>=4的序列，好象编程不是很简单的样子。
按我的理解，
{1, 9, 7, 3} valid
{1, 9, 7, 3, 6} 也valid
{1, 9, 7, 3, 6, 4} 还是valid
每一步增长序列，都得算是否前面的两个数的中点。
DFS可以code, 但是一是code不简明，二是效率好象不高。
不知道有没有更好的办法。

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

: 第4题难道不是个简单的dfs，记录visited cells就搞定了吗？有那么复杂？请指正，
: 谢谢。
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com

i*p2010-09-15 07:09

25 楼

yes.

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

: 1-4-7-3 算对的吗？
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com

g*e2010-09-15 07:09

26 楼

你说的对，update是O(n^2)，我真土。

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

: 我也是这么做的。这样update操作是O(n^2).

i*e2010-09-15 07:09

27 楼

那可不可以这样呢？
每次 DFS 的时候把中点的 pass 进递归函数里。
例如：
1->9 中点 = 5.
那下次 DFS 的时候就不会选 5 了，因为是之前的中点。
因为是3x3，所以好做，每个最多就只有一个中点。
好像 4->3，应该是没有中点对吧？
那这样子，1->7->5->4 也算答案。
如果之前的中点都不能接触的话，那只能传所有中点进去了，然后对所有中点之外的进
行 DFS.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

【在 g**********y 的大作中提到】

: 题目要找出所有>=4的序列，好象编程不是很简单的样子。
: 按我的理解，
: {1, 9, 7, 3} valid
: {1, 9, 7, 3, 6} 也valid
: {1, 9, 7, 3, 6, 4} 还是valid
: 每一步增长序列，都得算是否前面的两个数的中点。
: DFS可以code, 但是一是code不简明，二是效率好象不高。
: 不知道有没有更好的办法。

g*y2010-09-15 07:09

28 楼

抛砖引玉吧，
public ArrayList findIntersection(int[][] a) {
ArrayList list = new ArrayList();
int[] p = new int[a.length];

boolean endSearch = false;
do {
int min = 0;
boolean equals = true;
for (int i=1; iif (a[min][p[min]] > a[i][p[i]]) {
min = i;
equals = false;
continue;
}

if (equals && a[min][p[min]] < a[i][p[i]]) {
equals = false;
}
}

if (equals) {
list.add(a[min][p[min]]);
for (int i=0; ip[i]++;
if (p[i] == a[i].length) endSearch = true;
}
}
else {
p[min]++;
if (p[min] == a[min].length) endSearch = true;
}

} while (!endSearch);

return list;
}

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

: 2个list代码写起来还是容易的
: k个list的代码想写漂亮了，不容易啊。。。

g*y2010-09-15 07:09

29 楼

每次算中点要把已经在栈里的数拎出来算，比如
现在栈里有 {1, 9, 7, 3}, 添个6进去，就要算{1,6}, {9,6}, {7,6}, {3,6}
最后写code感觉很不clean, 我在interview里写这样的code，肯定写出一堆bug来。
最理想的是这个题有什么数学特性，能够很简洁地概括那个中点，写递归就容易了。
每次我一看到有很多条件的递归，头就大了，太容易写错了。
应该这么说吧，递归回溯时，要是有很多状态要维护，是一件很头疼的事。

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

: 那可不可以这样呢？
: 每次 DFS 的时候把中点的 pass 进递归函数里。
: 例如：
: 1->9 中点 = 5.
: 那下次 DFS 的时候就不会选 5 了，因为是之前的中点。
: 因为是3x3，所以好做，每个最多就只有一个中点。
: 好像 4->3，应该是没有中点对吧？
: 那这样子，1->7->5->4 也算答案。
: 如果之前的中点都不能接触的话，那只能传所有中点进去了，然后对所有中点之外的进
: 行 DFS.

g*s2010-09-15 07:09

30 楼

这题中点的定义是前面任两点还是两点必须是相邻？例如你的例子里面，如果只是相邻
，那么就
只要考虑{3,6}.
如果是后者，那么编程简单；如果是前者，剪枝快。程序写下来也不会复杂。
【在 gloomyturkey (一只郁闷的火鸡) 的大作中提到: 】

i*e2010-09-15 07:09

31 楼

LZ,
第二题感觉很多定义没搞清楚，这样很容易想偏的啦，说不定是很简单的题。
之前一个中点还是所有之前的中点都不能接触？
例如：
1->7->4 不可以
但是
1->7->5->4 是可以还是不可以？
还有，
1->4->3，这里到底是有中点还是没有？感觉 4->3 好像没有中点。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

i*e2010-09-15 07:09

32 楼

你传的应该是 List 的数组才对吧 (ArrayList[] a)，为什么传的是二维数组？
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

【在 g**********y 的大作中提到】

: 抛砖引玉吧，
: public ArrayList findIntersection(int[][] a) {
: ArrayList list = new ArrayList();
: int[] p = new int[a.length];
:
: boolean endSearch = false;
: do {
: int min = 0;
: boolean equals = true;
: for (int i=1; i

i*p2010-09-15 07:09

33 楼

这是我的理解。 as I've said, 当时跟interviewer的交流好像有点问题。

不可以
没有中点

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

: LZ,
: 第二题感觉很多定义没搞清楚，这样很容易想偏的啦，说不定是很简单的题。
: 之前一个中点还是所有之前的中点都不能接触？
: 例如：
: 1->7->4 不可以
: 但是
: 1->7->5->4 是可以还是不可以？
: 还有，
: 1->4->3，这里到底是有中点还是没有？感觉 4->3 好像没有中点。
: 一些常见面试题的答案与总结 -

g*y2010-09-15 07:09

34 楼

二维数组也可以是不等长的吧。

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

: 你传的应该是 List 的数组才对吧 (ArrayList[] a)，为什么传的是二维数组？
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com

g*y2010-09-15 07:09

35 楼

在车上又想了一下DFS:
我觉得让code麻烦的是回溯，比如{1,3}之后，2被从avaialbe set里排除掉，那3退栈的时候，相应应该恢复available set里的2, 这个情况复杂的时候用code写起来很不清爽.

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

: 这题中点的定义是前面任两点还是两点必须是相邻？例如你的例子里面，如果只是相邻
: ，那么就
: 只要考虑{3,6}.
: 如果是后者，那么编程简单；如果是前者，剪枝快。程序写下来也不会复杂。
: 【在 gloomyturkey (一只郁闷的火鸡) 的大作中提到: 】

i*e2010-09-15 07:09

36 楼

bless，理解，相信每个人都碰到过这样的情况。
另外，如果是这样理解的话，那题只要把中点也列为 visited cell 就可以了。然后就
是普通的 dfs，应该不难实现。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

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

: 这是我的理解。 as I've said, 当时跟interviewer的交流好像有点问题。
:
: 不可以
: 没有中点

g*y2010-09-15 07:09

37 楼

嗯，要是只是visited cell, 题目就简单多了。

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

: bless，理解，相信每个人都碰到过这样的情况。
: 另外，如果是这样理解的话，那题只要把中点也列为 visited cell 就可以了。然后就
: 是普通的 dfs，应该不难实现。
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com

i*e2010-09-15 07:09

38 楼

我写的代码如下。
这样打印出来的所有路线还真不是一般的多，
我在想题目的原意是不是指只要路线有相交就不允许？
例如：
1->9->7->3 就不允许，因为 7->3 与 1->9 相交。
如果有以上的条件的话，用 visited cells 就不能解决了。
似乎比较复杂。
#include
#include
using namespace std;
int crossPoint[10][10] = {
{0},
{0, 0, 0, 2, 0, 0, 0, 4, 0, 5},
{0, 0, 0, 0, 0, 0, 0, 0, 5, 0},
{0, 2, 0, 0, 0, 0, 0, 5, 0, 6},
{0, 0, 0, 0, 0, 0, 5, 0, 0, 0},
{0},
{0, 0, 0, 0, 5, 0, 0, 0, 0, 0},
{0, 4, 0, 5, 0, 0, 0, 0, 0, 8},
{0, 0, 5, 0, 0, 0, 0, 0, 0, 0},
{0, 5, 0, 6, 0, 0, 0, 8, 0, 0}
};
void dfs(int grid[][3], int row, int col, vector &path, bool visited[])
{
int val = grid[row][col];
if (visited[val]) return;
path.push_back(val);
if (path.size() >= 4) {
for (int i = 0; i < path.size(); i++)
cout << path[i] << ((i == path.size()-1) ? "" : "->");
cout << endl;
}
visited[val] = true;
for (int r = 0; r < 3; r++) {
for (int c = 0; c < 3; c++) {
int cross = crossPoint[val][grid[r][c]];
if (cross != 0 && visited[cross]) continue;
visited[cross] = true;
dfs(grid, r, c, path, visited);
visited[cross] = false;
}
}
path.pop_back();
visited[val] = false;
}
void dfs(int grid[][3]) {
for (int row = 0; row < 3; row++) {
for (int col = 0; col < 3; col++) {
bool visited[10] = { false };
dfs(grid, row, col, vector(), visited);
}
}
}
int main() {
int grid[3][3] = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
dfs(grid);
return 0;
}
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

s*n2010-09-15 07:09

39 楼

foreach item i in list 1.
for all other list l_s,
if peak(i,l_s), then add i into result list.
bool peak(i,l_s)
begin
do scan l_s from p_l_s while * p_l_s++ < i
if *(p_l_s -1) == i, return true;
end

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

: 应该是吧
: 是不是每个list用一个指针，尽量同步的扫描一遍就可以了

i*t2010-09-15 07:09

40 楼

第4题, 我理解是:对矩阵里任何一个横,竖, 斜方向上的三元组(a,b,c),
在结果里如果有头尾两个数(a,c) 或者(c,a), 那中间的数b 要末不出现, 要末出现a和
c之间.
比如 2,x,1,x,3 是非法的, 3,x,1,x,2 也是非法的. 同理, 对(3,5,7)这个元组, 数列
里不能有 3,x,7,x,5等等
如果按我这个理解, 只要作一个map,int> 记录所有不允许的组合
, 然后对所有长度4-9的permutation检查就可以了

p*w2010-09-15 07:09

41 楼

4一共有31684种可能

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

y*g2010-09-15 07:09

42 楼

g 还是 f啊

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

r*n2010-09-15 07:09

43 楼

第3题怎么做呢？按照bst走一边，把queue记录下来，然后再去搜索这个node的下一个
值是多少？这样子似乎不用parent指针。

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

m*q2010-09-15 07:09

44 楼

就是找successor
具体可以看CLRS BST那一章的TREE-SUCCESSOR()

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

: 第3题怎么做呢？按照bst走一边，把queue记录下来，然后再去搜索这个node的下一个
: 值是多少？这样子似乎不用parent指针。

g*y2010-09-15 07:09

45 楼

一点小改进：不需要grid[][], 1~9的单层循环是一样的。反正你有cross矩阵。

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

: 我写的代码如下。
: 这样打印出来的所有路线还真不是一般的多，
: 我在想题目的原意是不是指只要路线有相交就不允许？
: 例如：
: 1->9->7->3 就不允许，因为 7->3 与 1->9 相交。
: 如果有以上的条件的话，用 visited cells 就不能解决了。
: 似乎比较复杂。
: #include
: #include
: using namespace std;

l*i2010-09-15 07:09

46 楼

O(logn) for both query and update
fenwick tree or any balanced binary tree
Mihai Patrascu proved that O(logn) is best possible

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

: 你说的对，update是O(n^2)，我真土。

f*42010-09-15 07:09

47 楼

没测试过，假设node value是int
该函数不能处理：所有lists都是循环list
#define MININTEGER -32767
typedef struct Node
{
int value;
Node *next;
} Node;
void KListInte(Node ** klists)
{
if (klists == NULL) return;
int currentMax = MININTEGER;
int k = sizeof(klists) / sizeof(Node **);
while (1)
{
for (int i = 0; i < k; i++)
{
if (klists[i] == NULL) return;
if (klists[i]->value > currentMax)
currentMax = klists[i]->value;
}
for (int i = 0; i < k; i++)
{
while (klists[i] && klists[i]->value < currentMax)
klists[i] = klists[i]->next;
}
bool intersection = true;
for (int i = 0; i < k; i++)
{
if (klists[i] == NULL) return;
if (klists[i]->value != currentMax)
{
intersection = false;
break;
}
}
if (intersection) printf("%d\t",klists[0]->value);
for (int i = 0; i < k; i++)
klists[i] = klists[i]->next;
}
}

,

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

: 是的。
: idea很简单，但是假如list个数未知，coding未必很容易。我最后也只写了2个list,
: 没有figure out k lists.

P*c2010-09-15 07:09

48 楼

是每次找出k个里面最大的，其他所有的都前进一步吗？这样的话复杂度是(nk^2)

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

: 应该是吧
: 是不是每个list用一个指针，尽量同步的扫描一遍就可以了

q*x2010-09-15 07:09

49 楼

第四题看不懂。grid和数列的关系是什么？
比如数列长度为5，你怎么摆成grid？

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

P*c2010-09-15 07:09

50 楼

grid是定死的，就是那么多数。从这些数里找数列。grid的作用只是告诉你哪些点是中
点。

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

: 第四题看不懂。grid和数列的关系是什么？
: 比如数列长度为5，你怎么摆成grid？

P*c2010-09-15 07:09

51 楼

grid是定死的，就是那么多数。从这些数里找数列。grid的作用只是告诉你哪些点是中
点。

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

: 第四题看不懂。grid和数列的关系是什么？
: 比如数列长度为5，你怎么摆成grid？