g*********e
发帖数: 14401 | 1 【 以下文字转载自 SanFrancisco 讨论区 】
发信人: glowinglake (湖清霞远), 信区: SanFrancisco
标 题: FB电面求分析
发信站: BBS 未名空间站 (Wed Apr 18 20:11:16 2012, 美东)
昨天面的。上来先问我简历上的OS project。
之后开始coding，问了一个走迷宫的问题。在一个bool array里面寻找两点的path，并
打印。
我写了一个DFS递归+visited array寻找。
之后他问我complexity。我说空间时间都是O(mn)。
他说我的code时间不是O(mn),我看了下发现我的是exponential，就跟他说了，然后忙
改了下，就是visited set以后不再reset。这样就是polynomial time。他还算满意。
之后他问我如果这个迷宫很大，该怎么处理。我想了下说就分成若干小block,每台机器
算每个小block里可能的boundry to boundry path,并存在一个list里面。这样相邻的
block就可以交流对方的path，然后拓展当前path(我也没完全想出个solution）
他让我写每台机器算block里path和互相交流的过程的伪代码。说类似remote
procedure call。
我瞎写了下，大致就是对每个block边界上的点每对pair求path, 并且有个优化，在寻
找path的过程中如果路径其他边界点，直接添加该path.
然后写机器间交流的伪代码，我更乱写了，大致是根据相邻机器的path list拓展当前
机器的global path.并不停的expand global path list.
最后我问了他几个technical问题。
求分析我这样还有戏吗？ | p*****2
发帖数: 21240 | | g*********e
发帖数: 14401 | | g*********e
发帖数: 14401 | | p*****2
发帖数: 21240 | | g*********e
发帖数: 14401 | | l*****a
发帖数: 14598 | 7 牛人你都拒了好几个offer
给别人留点活路吧
不过谢谢share experience
我记在小本上慢慢看
【在 g*********e 的大作中提到】
: 没实力啊 move on 了
| g*********e
发帖数: 14401 | | s******n
发帖数: 3946 | 9 这没法优化吧？
int targetx;
int targety;
BYTE array[m][n];
char output[m*n];
bool visit(int x, int y, int output_idx)
{
if (x<0 || y<0 || x>=m || y>=n) return false;
if (array[x][y]) return false;
if (x==targetx && y==targety) {
output[output_idx]=0;
printf("%s\n", output);
return true;
}
array[x][y]=1;
output[output_idx]='R';
if (visit(x+1,y, output_idx+1)) return true;
output[output_idx]='D';
if (visit(x,y+1, output_idx+1)) return true;
output[output_idx]='U';
if (visit(x,y-1, output_idx+1)) return true;
output[output_idx]='L';
if (visit(x-1,y, output_idx+1)) return true;
return false;
} | w****x
发帖数: 2483 | 10 面试官第二题的考点是什么???
如果是RPC: bool GetIndex(int x, int y),
这个RPC是由比如master机器映射到不同机器上读取数据, 主要问题是Map太大了不能放
到一台机器上??
如果考分布式计算那么每台计算机计算一个block, 给每个block的端口编号, 每个编号
不同从 1...n, 然后计算所有两两之间的通路, 然后再把block连起来??
如果是这样的话既然不同block的端口不一样, 那么知道端口号也知道了block号, 也知
道这两点间怎么走.
把所有的端口到端口的pair混在一起来做一个3元组PORT_PATH:
1. 根据start point 和 end point 找到最近的端口ptBeg & ptEnd, 问题就是在<
port1, port2, path>这一堆3元组中找到通路让ptBeg ..... --> ptEnd
2. bool FindPath(int ptBeg, int ptEnd, map> mp, bRec[
n])
{
if (ptBeg == ptEnd) return true;
bRec[ptBeg] = true;
vector& vec = mp[ptBeg];
for (vector::iterator it = vec.begin();
it != vec.end(); it++)
{
if (!bRec[it->ptEnd] && FindPath(it->ptEnd, ptEnd))
return true;
}
bRec[ptBeg] = false;
return false;
} | | | g*********e
发帖数: 14401 | 11
path>
他没说怎么做。这些都是我自己的想法。肯定要分布式计算，除了分成block一个个
solve，想不出其他好办法了。RPC也是因为我之前提到过在project里用过。
【在 w****x 的大作中提到】
: 面试官第二题的考点是什么???
: 如果是RPC: bool GetIndex(int x, int y),
: 这个RPC是由比如master机器映射到不同机器上读取数据, 主要问题是Map太大了不能放
: 到一台机器上??
: 如果考分布式计算那么每台计算机计算一个block, 给每个block的端口编号, 每个编号
: 不同从 1...n, 然后计算所有两两之间的通路, 然后再把block连起来??
: 如果是这样的话既然不同block的端口不一样, 那么知道端口号也知道了block号, 也知
: 道这两点间怎么走.
: 把所有的端口到端口的pair混在一起来做一个3元组PORT_PATH:
: 1. 根据start point 和 end point 找到最近的端口ptBeg & ptEnd, 问题就是在<
| f******n
发帖数: 264 | | S*****e
发帖数: 229 | 13 bless!!!
【在 g*********e 的大作中提到】
:
: path>
: 他没说怎么做。这些都是我自己的想法。肯定要分布式计算，除了分成block一个个
: solve，想不出其他好办法了。RPC也是因为我之前提到过在project里用过。
| y******8
发帖数: 12 | | s*******f
发帖数: 1114 | 15 //码遍本版
//need more boundary check and a wrapper function for interview.
namespace maze{
struct Info{
int idx;
};
int di[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
bool InRange(int row, int col, int xx, int yy){
return 0 <= xx && xx < row && 0 <= yy && yy < col;
}
template
void MazeRoute(int m[][col], int row, int x0, int y0, int x1, int y1){
//static Info *info = new Info[row * col];
static vector > path;
path.push_back(make_pair(x0, y0));
m[x0][y0] = 8;
if (x0 == x1 && y0 == y1){
for (vector >::iterator it = path.begin(); it !=
path.end(); ++it){
printf("(%d, %d) ", it->first, it->second);
}
return;
} else {
for (int i = 0; i < 4; ++i){
int xx = x0 + di[i][0];
int yy = y0 + di[i][1];
if (InRange(row, col, xx, yy)){
if (m[xx][yy] == 0){
MazeRoute(m, 4, xx, yy, x1, y1);
}
} else {
//RPC call MazeRoute(m, 4, xx, yy, x1, y1);
}
}
}
path.pop_back();
//delete[] info;
return;
}
void TestMazeRoute(){
int m[4][4] = {{0,0,1,0},{0,0,0,0},{0,1,0,1},{0,1,0,0}};
MazeRoute<4>(m, 4, 0, 0, 0, 3);
}
};
//for RPC. it is better to call 1 time for 1 machine, that is, find out all
nodes in the bound that have path and send all calls together to the remote
machine.
【在 g*********e 的大作中提到】
:
: path>
: 他没说怎么做。这些都是我自己的想法。肯定要分布式计算，除了分成block一个个
: solve，想不出其他好办法了。RPC也是因为我之前提到过在project里用过。
|
|
