热腾腾g电面已挂 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

热腾腾g电面已挂

热腾腾g电面已挂# JobHunting - 待字闺中

p*p2014-02-21 08:02

1 楼

黄奕与姜凯闪婚、闪离的消息成为圈中的热门话题，有报道称，黄奕的密友透露，两人
目前正在冷战，还没有进入离婚程序。不过，因为性格不合而导致婚姻亮起红灯却是铁
的事实。这两天在横店拍戏的黄奕得知私人感情被传开后，禁不住再度哭泣。
http://6park.com/news/messages/72835.html

g*i2014-02-21 08:02

2 楼

同胞面试官，上来就gdoc做题。
2d array ＊代表障碍物＃代表货物空白就是正常的路
问
如何找到一个点为出发点能实现总共取货路径最短？每次只能拿一个货物，遇到障碍
需要绕开，拿到以后要放回出发点，然后再取另一个
＊＊＊＊＊＊
＊＃＊
＊＊＊＊＊
＊＊
＊＊＊＊
＊＃＃＊
＊＊＊＊＊＊
大牛们有什么好思路？我用的bfs，但因为之前讨论题目要求花了很久，没有写完。。
我还是太弱了，move on

l*e2014-02-21 08:02

3 楼

名字起的不好。
凯子。

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

: 黄奕与姜凯闪婚、闪离的消息成为圈中的热门话题，有报道称，黄奕的密友透露，两人
: 目前正在冷战，还没有进入离婚程序。不过，因为性格不合而导致婚姻亮起红灯却是铁
: 的事实。这两天在横店拍戏的黄奕得知私人感情被传开后，禁不住再度哭泣。
: http://6park.com/news/messages/72835.html

f*f2014-02-21 08:02

4 楼

DP ?

p*p2014-02-21 08:02

5 楼

还是阿姨一针见血

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

: 名字起的不好。
: 凯子。

r*c2014-02-21 08:02

6 楼

每个货物都是独立的，就是找有障碍的曼哈顿距离

J*n2014-02-21 08:02

7 楼

这男的看着真是ws啊

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

e*i2014-02-21 08:02

8 楼

取n个跟取一个没本质区别。。。即使挡路交换次序也没问题，所以可以一个一个来
bfs碰到一个就加2x的长度，碰到k个为止

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

: 同胞面试官，上来就gdoc做题。
: 2d array ＊代表障碍物＃代表货物空白就是正常的路
: 问
: 如何找到一个点为出发点能实现总共取货路径最短？每次只能拿一个货物，遇到障碍
: 需要绕开，拿到以后要放回出发点，然后再取另一个
: ＊＊＊＊＊＊
: ＊＃＊
: ＊＊＊＊＊
: ＊＊
: ＊＊＊＊

k*u2014-02-21 08:02

9 楼

梨叔涉吏广泛啊
什么都知道

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

w*s2014-02-21 08:02

10 楼

你取一个的结果计算过程是否对取下一个有用，有用的话，记录下来下一次不用那么耗
费。

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

: 取n个跟取一个没本质区别。。。即使挡路交换次序也没问题，所以可以一个一个来
: bfs碰到一个就加2x的长度，碰到k个为止

l*a2014-02-21 08:02

11 楼

mark

q*n2014-02-21 08:02

12 楼

有大牛给个具体的code吗？多谢！

r*c2014-02-21 08:02

13 楼

需要具体路径还是只要长度

g*i2014-02-21 08:02

14 楼

都不需要找出那个点

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

: 需要具体路径还是只要长度

g*i2014-02-21 08:02

15 楼

google了一下才知道啥时候曼哈顿距离

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

: 每个货物都是独立的，就是找有障碍的曼哈顿距离

l*62014-02-21 08:02

16 楼

bfs from every box. in each box , a non blocking cell(include box position ,
but exclude hazard position ) will have a weight value , stand for the
distance to the box. after bfs from all the boxes , each cell will have k
weight, k is the number of boxes. sum all the weight in each cell , and find
the cell with smallest sum of weight. One problem of this solution may lead
to a cell of a box. revision is sort the cell by sum of weight and find the
first that is not a box.
complexity k*n^2

n*a2014-02-21 08:02

17 楼

正解，这个题目就是从起点（默认的左上角那个）做bfs好了，时间复杂度就是矩阵的
单元格的数量

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

: 取n个跟取一个没本质区别。。。即使挡路交换次序也没问题，所以可以一个一个来
: bfs碰到一个就加2x的长度，碰到k个为止

f*e2014-02-21 08:02

18 楼

只是一个电面题，应该不难，心理上不要有包袱。

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

: 正解，这个题目就是从起点（默认的左上角那个）做bfs好了，时间复杂度就是矩阵的
: 单元格的数量

j*n2014-02-21 08:02

19 楼

从#开始做BFS

f*n2014-02-21 08:02

20 楼

map[7][6]
000000
012110
000010
011110
010010
021120
000000
//Assume 2 is product, 1 is blank, 0 is block. 2 is also block before
fetching
use BFS
result start at map[4][4]
order map[1][2] map[5][4] map[5][1] total 20 steps

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

: 从#开始做BFS

w*f2014-02-21 08:02

21 楼

这个方法肯定是对的，唯一可以优化的是，可以在每个节点中存一个距离的array,
vector d(k, 0). 存该点到每个box的最小距离。这样的话，在bfs一开始就把所
有的box先放进queue里一起做bfs。应该扫一遍就可以了。最后在扫一遍整个matrix，
每个节点求个和，找最小的distance
typedef struct node {
bool visited;
vector d(k, 0);
int x;
int y;
} node;

,
find
lead
the

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

: bfs from every box. in each box , a non blocking cell(include box position ,
: but exclude hazard position ) will have a weight value , stand for the
: distance to the box. after bfs from all the boxes , each cell will have k
: weight, k is the number of boxes. sum all the weight in each cell , and find
: the cell with smallest sum of weight. One problem of this solution may lead
: to a cell of a box. revision is sort the cell by sum of weight and find the
: first that is not a box.
: complexity k*n^2

o*n2014-02-21 08:02

22 楼

同意14楼。LZ估计是太紧张了。

g*i2014-02-21 08:02

23 楼

谢谢你！还是需要多练习

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

: 同意14楼。LZ估计是太紧张了。

g*i2014-02-21 08:02

24 楼

受教了！多谢！
图片是05年的伊斯坦布尔吧我也是米兰球迷

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

: map[7][6]
: 000000
: 012110
: 000010
: 011110
: 010010
: 021120
: 000000
: //Assume 2 is product, 1 is blank, 0 is block. 2 is also block before
: fetching

n*a2014-02-21 08:02

25 楼

这个是对的，我原来看错题目了，以为从一个设定好的点出发，求到所有货物的最短距
离了，不好意思。

,
find
lead
the

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

b*t2014-02-21 08:02

26 楼

这题是O（m+n）吧，穷举法，先算x再算y，因为曼哈顿距离是可以投影得，
带入法，先算在列上，那个点到所有货物点得横坐标距离和最小，得到横坐标值；同理
得到纵坐标值，如果该点不能访问，比较x次优，x最优，y次优，y最优的坐标组合，选
没有block的最小结果。

t*j2014-02-21 08:02

27 楼

虽然这题不算太难，我的想法也是对每个货物BFS，然后扫描算最小sum。
可是咱同胞，还只是个电面就面这个，说实话，我想骂人。

e*32014-02-21 08:02

28 楼

BFS+DP,而且需要maintain两个距离，一个是到终点的最小距离，一个是到起点的最小
距离，计算终点的距离需要backtrack,到起点的简单比较保存最小值就行了，类似
Dijkstra算法。电面就考这个有点偏难了，尤其还是同胞就操蛋了，要是老中这么考老
印我绝对赞成。简单的实现还可以把障碍物那个的距离设成100啥的，这样自然就知道
要绕过了。
这个题目的难度比reverse linkedlist, atoi难了几个数量级。。。
我贴两个我自己写的代码抛砖引玉一下，第一个是Harry Potter最小的strength通关，
第二个是经典的Dijkstra algorithm,都是附带了测试数据自动生成的方法，你把这两
个组合一下基本就能解这道题了,过两天我有空了来写一下这道题的具体实现。
import java.util.*;
public class HarryPotter{
private static Random rand = new Random();
private static int[][] matrix;
private static Map cache = new HashMapInteger>();

static class CacheKey{
private int x, y;
public CacheKey(int x, int y){
this.x = x;
this.y = y;
}

@Override
public boolean equals(Object obj){
CacheKey key = (CacheKey) obj;
return this.x == key.x && this.y == key.y;
}

@Override
public int hashCode(){
return ((Integer) (this.x+this.y)).hashCode();
}
}

public static int[][] createMatrix(int width, int height){
int[][] matrix = new int[height][width];
for (int i=0; ifor (int j=0; jmatrix[i][j] = rand.nextInt(50);
if (rand.nextBoolean()){
matrix[i][j] *= -1;
}
}
}
return matrix;
}

public static void printMatrix(int[][] matrix){
for (int i=0; iint j = 0;
for (; jSystem.out.print(matrix[i][j] + ", ");
}
System.out.println(matrix[i][j]);
}
}

public static int minimumStrength(int x, int y){
int strength = 0;
if (x == matrix[0].length-1 && y == matrix.length-1){
if (matrix[y][x] < 0){
strength = -1 * matrix[y][x];
}
} else if (x == matrix[0].length-1){

int nextStrength = cachedStrength(x, y+1);
strength = calcStrength(nextStrength, x, y);
} else if (y == matrix[0].length-1){
int nextStrength = cachedStrength(x+1, y);
strength = calcStrength(nextStrength, x, y);
} else {
int nextStrength = Math.min(cachedStrength(x, y+1),
cachedStrength(x+1, y));
strength = calcStrength(nextStrength, x, y);
}
System.out.println(x + ", " + y + " needs minimum strength of " +
strength);
return strength;
}

public static int cachedStrength(int x, int y){
CacheKey key = new CacheKey(x, y);
if (cache.containsKey(key)){
return cache.get(key);
} else {
int strength = minimumStrength(x, y);
cache.put(key, strength);
return strength;
}
}

private static int calcStrength(int nextStrength, int x, int y){
int strength = 0;
if (nextStrength == 0){
if (matrix[y][x] < 0) strength = -1 * matrix[y][x];
} else {
if (matrix[y][x] - nextStrength >= 0){
strength = 0;
} else {
strength = nextStrength - matrix[y][x];
}
}
return strength;
}
public static void main(String []args){
int size = 3;
matrix = createMatrix(size,size);
printMatrix(matrix);
cachedStrength(0,0);
}
}
-------------------------------------------------------------------------
import java.util.*;
public class Dijkstra{

private static Random rand = new Random();
private static int[][] matrix;
private static Map distances;

public static int[][] randomMatrix(int size){
matrix = new int[size][size];
for (int i=0; ifor (int j=i+1; jmatrix[i][j] = rand.nextInt(20) + 1;
if (i == 0) {
//Applies weight, otherwise, the final distance is
usually the same as the first row.
matrix[i][j] += (j-1) * 15;
}
}
}
return matrix;
}

public static void printMatrix(int[][] matrix){
for (int i=0; ifor (int j=0; jSystem.out.print(Math.abs(matrix[i][j]) + ", ");
}
System.out.println(matrix[i][matrix[i].length-1]);
}
System.out.println("-----------------------------");
}

public static void minPath() throws RuntimeException{
distances = new HashMap();
distances.put((Integer) 0, (Integer) 0);
for (int i=0; ifor (int j=i+1; jif (matrix[i][j] > 0){
if (distances.get((Integer) j) == null){
distances.put((Integer) j, distances.get((Integer) i
) + matrix[i][j]);
} else {
if (distances.get((Integer) i) == null) {
throw new RuntimeException();
} else {
if (distances.get((Integer) i) + matrix[i][j] <
distances.get((Integer) j)){
distances.put((Integer) j, distances.get((
Integer) i) + matrix[i][j]);
}
}
}
}
}
}
System.out.println(distances.toString());
}
public static void main(String []args){
printMatrix(randomMatrix(5));
minPath();

matrix = new int[6][6];
matrix[0][1] = 7;
matrix[0][2] = 9;
matrix[0][5] = 14;
matrix[1][2] = 10;
matrix[1][3] = 15;
matrix[2][3] = 11;
matrix[2][5] = 2;
matrix[3][4] = 6;
matrix[4][5] = 9;
printMatrix(matrix);
minPath();
}
}

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