b***e
发帖数: 15201 | 1 1：
给两个stack，怎样建个queue,写出dequeue,enqueue.
这个简单，写完了，问是否thread safe，如果不safe怎样处理。
public interface IStack {
public void push(E e);
public E pop();
public Boolean isEmpty();
}
public interface IQueue {
public void enqueue(E e);
public E dequeue();
}
public class Queue implements IQueue {}
2：
给一个2维数组，里面是0,1值表示不相邻或者相邻
问题：
查找这个数组里面所有的connected components |
k***t
发帖数: 276 | 2 BFS ?
【在 b***e 的大作中提到】
: 1：
: 给两个stack，怎样建个queue,写出dequeue,enqueue.
: 这个简单，写完了，问是否thread safe，如果不safe怎样处理。
: public interface IStack {
: public void push(E e);
: public E pop();
: public Boolean isEmpty();
: }
: public interface IQueue {
: public void enqueue(E e);
|
d********t
发帖数: 9628 | 3 what's connected comp.?
【在 b***e 的大作中提到】
: 1：
: 给两个stack，怎样建个queue,写出dequeue,enqueue.
: 这个简单，写完了，问是否thread safe，如果不safe怎样处理。
: public interface IStack {
: public void push(E e);
: public E pop();
: public Boolean isEmpty();
: }
: public interface IQueue {
: public void enqueue(E e);
|
Y**B
发帖数: 144 | |
b***e
发帖数: 15201 | 5 [1 0 1]
[1 0 1]
[1 1 1]
这里只有一个connect component
[1 0 1]
[1 0 1]
[1 0 1]
这里有2个component |
f*******t
发帖数: 7549 | |
z****c
发帖数: 602 | 7 try blob analysis in computer vision. |
i**d
发帖数: 357 | 8 这个可以用floyd-warshall来做吧。复杂度O(N^3) |
g**********y
发帖数: 14569 | |
b***e
发帖数: 15201 | |
|
|
d********t
发帖数: 9628 | 11 有没有不用graph theory做component题目的办法？
【在 b***e 的大作中提到】
: 1：
: 给两个stack，怎样建个queue,写出dequeue,enqueue.
: 这个简单，写完了，问是否thread safe，如果不safe怎样处理。
: public interface IStack {
: public void push(E e);
: public E pop();
: public Boolean isEmpty();
: }
: public interface IQueue {
: public void enqueue(E e);
|
q****x
发帖数: 7404 | 12 这个不会让写代码吧。
【在 b***e 的大作中提到】
: 看了，还是没能在规定时间写完code..
|
b***e
发帖数: 15201 | 13 public int countComps(int[][] a) {}
让写出这个函数的body.....
【在 q****x 的大作中提到】
: 这个不会让写代码吧。
|
q****x
发帖数: 7404 | 14 1. 图的邻接矩阵表示，反复做乘法可得连通分支。图论定理，但是公式记不清了。
2. 转邻边表，BFS。这个笨办法。
不过电面谈谈思路就差不多了吧？如果提示1的公式倒是也可以写。
【在 b***e 的大作中提到】
: public int countComps(int[][] a) {}
: 让写出这个函数的body.....
|
a*******d
发帖数: 85 | 15 我的看法:
可以把二维数组中的每一个元素看成是图的一个node, 1可以看成是edge. 然后用DFS找
strongly connected components. |
b***e
发帖数: 15201 | 16 我后来做出来的解法：
public static int countComps(int[][] a)
{
int m=a.length;//row length
int n=a[0].length; //col length
int label=2;
HashSet equal_labels = new HashSet();
int west=0;
int north=0;
for (int i=0;i
for (int j=0;j
{
if (a[i][j]!=0)
{
if (i==0 && j==0)
{
a[i][j]=label;
}
else
{
if (i==0) {north=0;west=a[i][j-1];}
else
if (j==0) {west=0;north=a[i-1][j];}
else
{
north=a[i-1][j];
west=a[i][j-1];
}
//check left/west
if (west>a[i][j])
{
if (north==0) a[i][j]=west;
else
if (north>a[i][j] && north!=west)
{
a[i][j]=Math.min(north,west);
//we know label of north and west are
in the same set
TreeSet tmp=new TreeSet();
tmp.add(north);
tmp.add(west);
equal_labels.add(tmp);
System.out.println("find n=w .");
}
else a[i][j]=north; //when north=west
}
else
//check north only since west is not good
{
if (north>a[i][j])
{
a[i][j]=north;
}
else
{
//now, we need a new label, so label++
label++;
a[i][j]=label;
}
}
}
}
}
System.out.println(Arrays.deepToString(a));
System.out.println(equal_labels);
int result = label-1-equal_labels.size();
System.out.println("result comps = "+result);
return result;
}
|
a*****n
发帖数: 158 | |
b***e
发帖数: 15201 | 18 前面贴出来的解法还有个Bug,数组前几行都是0的时候，返回值差1：
这个是改正的版本。
public static int countComps(int[][] a)
{
int m=a.length;//row length
int n=a[0].length; //col length
int label=1;//label init value is 1 but will start with 2,increase
by 1 when find 1 possible new component
HashSet equal_labels = new HashSet();//to save equivalent label
pairs,no duplicates
//return result would be
int west=0;
int north=0;
for (int i=0;i
for (int j=0;j
{
if (a[i][j]!=0)
{
if (i==0 && j==0)
{
a[i][j]=++label;
//use ++label here to match the case when 1st a
few rows are all 0s
}
else
{
if (i==0) {north=0;west=a[i][j-1];}
else
if (j==0) {west=0;north=a[i-1][j];}
else
{
north=a[i-1][j];
west=a[i][j-1];
}
//check left/west
if (west>a[i][j])
{
if (north==0) a[i][j]=west;
else
if (north>a[i][j] && north!=west)
{
a[i][j]=Math.min(north,west);
//we know label of north and west are
in the same set
TreeSet tmp=new TreeSet();
tmp.add(north);
tmp.add(west);
equal_labels.add(tmp);
System.out.println("find n=w .");
}
else a[i][j]=north; //when north=west
}
else
//check north only since west is not good
{
if (north>a[i][j])
{
a[i][j]=north;
}
else
{
//now, we need a new label, so label++
label++;
a[i][j]=label;
}
}
}
}
}
System.out.println(Arrays.deepToString(a));
System.out.println(equal_labels);
int result = label-1-equal_labels.size();
System.out.println("result comps = "+result);
return result;
}
【在 a*****n 的大作中提到】
: 电面题目就这么难啊。。。。惨了。。
|
z***e
发帖数: 209 | 19 MS要求有点过分,简历里面是不是提到vision相关的东西?
Amazon什么组做vision? |
b***e
发帖数: 15201 | 20 没有任何vision的，这个哥们说他是做catlog清除duplicate那个组的。。。
【在 z***e 的大作中提到】
: MS要求有点过分,简历里面是不是提到vision相关的东西?
: Amazon什么组做vision?
|
|
|
i**********e
发帖数: 1145 | 21 你这样写貌似复杂了些，面试不会写那么复杂的代码的。
这题可以用 flood fill 的啊，递归十多行就能搞定。
基本就用一个二维数组记录哪些格子是访问过的，然后每一个格子如果还没访问过就进
行flood fill。
increase
【在 b***e 的大作中提到】
: 前面贴出来的解法还有个Bug,数组前几行都是0的时候，返回值差1：
: 这个是改正的版本。
: public static int countComps(int[][] a)
: {
: int m=a.length;//row length
: int n=a[0].length; //col length
: int label=1;//label init value is 1 but will start with 2,increase
: by 1 when find 1 possible new component
:
: HashSet equal_labels = new HashSet();//to save equivalent label
|
z***e
发帖数: 209 | 22 能给点细节吗?
【在 i**********e 的大作中提到】
: 你这样写貌似复杂了些，面试不会写那么复杂的代码的。
: 这题可以用 flood fill 的啊，递归十多行就能搞定。
: 基本就用一个二维数组记录哪些格子是访问过的，然后每一个格子如果还没访问过就进
: 行flood fill。
:
: increase
|
i**********e
发帖数: 1145 | |
d********t
发帖数: 9628 | 24 第一题是CC上的原题啊，楼主写的是什么啊？
【在 b***e 的大作中提到】
: 1：
: 给两个stack，怎样建个queue,写出dequeue,enqueue.
: 这个简单，写完了，问是否thread safe，如果不safe怎样处理。
: public interface IStack {
: public void push(E e);
: public E pop();
: public Boolean isEmpty();
: }
: public interface IQueue {
: public void enqueue(E e);
|
z****u
发帖数: 104 | 25 第二题是不是这个思路
假设我们只需要找出 connected component 的数目：从左上角开始扫描，如果遇到 1
的话，cc 数目 + 1，同时递归的把它的值为 1 的邻居置 0。继续扫描直到末尾。
扫描一遍就够了。同时每个点最多被扫描两次，值为 1 时一次，为 0 时一次，复杂度
应该是 O(n)
【在 b***e 的大作中提到】
: 1：
: 给两个stack，怎样建个queue,写出dequeue,enqueue.
: 这个简单，写完了，问是否thread safe，如果不safe怎样处理。
: public interface IStack {
: public void push(E e);
: public E pop();
: public Boolean isEmpty();
: }
: public interface IQueue {
: public void enqueue(E e);
|
b***e
发帖数: 15201 | 26 第2题我看到的基本解法是从左上开始，对任意元素，查找正上和左边的邻居，然后依
照一些rule来决定当前元素的label值。如果你把邻居都标0的话，恐怕会影响后续元素
的标定。因为一个很重要的rule就是当正上和左边都是相邻元素，但是标定值不同，那
这两个label就是等价的，而当前元素取二者label的最小值。
1
【在 z****u 的大作中提到】
: 第二题是不是这个思路
: 假设我们只需要找出 connected component 的数目：从左上角开始扫描，如果遇到 1
: 的话，cc 数目 + 1，同时递归的把它的值为 1 的邻居置 0。继续扫描直到末尾。
: 扫描一遍就够了。同时每个点最多被扫描两次，值为 1 时一次，为 0 时一次，复杂度
: 应该是 O(n)
|
z****u
发帖数: 104 | 27 递归的标记为 0，就是把整个 component 都标记为 0 了，这样就不会重复计算了，你
在纸上画一画就可以了，没有你想的那么复杂的。
void eliminate_component(map *m, int w, int h)
{
/* eliminate_component eliminates non-zero valued pixel and its non-
zero valued neighbour.
*/
if(get_map(m, w, h)) {
set_map(m, w, h, 0);
/* set its left neighbour to 0 */
if(w > 0)
if(get_map(m, w - 1, h))
eliminate_component(m, w - 1, h);
/* set its right neighbour to 0 */
if(w < m->width - 1)
if(get_map(m, w + 1, h))
eliminate_component(m, w + 1, h);
/* set its top neighbour to 0 */
if(h > 0)
if(get_map(m, w, h - 1))
eliminate_component(m, w, h - 1);
/* set its bottom neighbour to 0 */
if(h < m->height -1)
if(get_map(m, w, h + 1))
eliminate_component(m, w, h + 1);
}
else
/* this should not happen */
;
}
int connected_component(map *m)
{
int w, h, count = 0;
for(w = 0; w < m->width; ++w)
for(h = 0; h < m->height; ++h)
if (get_map(m, w, h)) {
count++;
eliminate_component(m, w, h);
}
return count;
}
【在 b***e 的大作中提到】
: 第2题我看到的基本解法是从左上开始，对任意元素，查找正上和左边的邻居，然后依
: 照一些rule来决定当前元素的label值。如果你把邻居都标0的话，恐怕会影响后续元素
: 的标定。因为一个很重要的rule就是当正上和左边都是相邻元素，但是标定值不同，那
: 这两个label就是等价的，而当前元素取二者label的最小值。
:
: 1
|
b***e
发帖数: 15201 | 28 恩我觉得你说的这个应该是面试官想要的解法，可惜我当时没想到标记为0，用递归的
办法。当时他提示我了，可以改原数组的值，我说比如-1,他说-1不好，比如2之类的，
我就接着递增的这个方向去想了。
估计他也不好直接告诉我标记0就好。
这个写起来也更方便，直接。
【在 z****u 的大作中提到】
: 递归的标记为 0，就是把整个 component 都标记为 0 了，这样就不会重复计算了，你
: 在纸上画一画就可以了，没有你想的那么复杂的。
: void eliminate_component(map *m, int w, int h)
: {
: /* eliminate_component eliminates non-zero valued pixel and its non-
: zero valued neighbour.
: */
: if(get_map(m, w, h)) {
: set_map(m, w, h, 0);
: /* set its left neighbour to 0 */
|
