Redian新闻
>
485 receipt 上priority date 框可以是空吗?
avatar
485 receipt 上priority date 框可以是空吗?# EB23 - 劳工卡
b*e
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
avatar
y*1
2
好像听说要四岁才能坐。 要超过四十磅。娃也快四十磅了。可以上了吗?主要是比较
方便,跟别人出去,带个booster ,就可以坐人家的车了。
avatar
b*r
3
刚收到485receipt,发现priority date框是空。这个正常吗?这个框里是不是应该有
date和类别(eb2 or eb3)
avatar
k*t
4
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);

avatar
x*t
5
For your kid's safety, keep him/her in the 5-point harness seat as long as
possible. 3 year old is too young to sit in a booster seat, he/she can get
out of the seat too easily.
Also, check your state law about child carseats. each state is different.

【在 y**1 的大作中提到】
: 好像听说要四岁才能坐。 要超过四十磅。娃也快四十磅了。可以上了吗?主要是比较
: 方便,跟别人出去,带个booster ,就可以坐人家的车了。

avatar
d*t
6
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);

avatar
j*e
7
建议不要
avatar
Y*B
8
不大明白题意...
avatar
p*z
9
我家老大7岁半了还在坐5harness 的car seat, 而且打算能坐多久就多久, 安全最重
要。
avatar
b*e
10
[1 0 1]
[1 0 1]
[1 1 1]
这里只有一个connect component
[1 0 1]
[1 0 1]
[1 0 1]
这里有2个component
avatar
l*u
11
那他/她没有超重吗?

【在 p******z 的大作中提到】
: 我家老大7岁半了还在坐5harness 的car seat, 而且打算能坐多久就多久, 安全最重
: 要。

avatar
f*t
12
union find?
avatar
b*d
13
.......i did.......we also helped to pick up friend's child with booster in
emergency....
feel so guilty a ....

【在 y**1 的大作中提到】
: 好像听说要四岁才能坐。 要超过四十磅。娃也快四十磅了。可以上了吗?主要是比较
: 方便,跟别人出去,带个booster ,就可以坐人家的车了。

avatar
z*c
14
try blob analysis in computer vision.
avatar
p*z
15
她现在50多磅, 用的是BRITAX MARATHON, 可以坐到65磅。

【在 l******u 的大作中提到】
: 那他/她没有超重吗?
avatar
i*d
16
这个可以用floyd-warshall来做吧。复杂度O(N^3)
avatar
n*p
17
有没有超身高? Marathon最多身高49英寸。

【在 p******z 的大作中提到】
: 她现在50多磅, 用的是BRITAX MARATHON, 可以坐到65磅。
avatar
p*z
19
没有超身高, 只要坐着的时候肩膀不超过坐椅后背就没问题

【在 n***p 的大作中提到】
: 有没有超身高? Marathon最多身高49英寸。
avatar
n*p
21
我怎么觉得头不能超过座椅后背?
如果只是肩膀不超过座椅后背,头往哪里放?没有头枕的话要是追尾脖子不就断了?

【在 p******z 的大作中提到】
: 没有超身高, 只要坐着的时候肩膀不超过坐椅后背就没问题
avatar
d*t
22
有没有不用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);

avatar
b*c
23
我儿子班上个子大点的娃这么大的时候什么都不用,直接坐车了。我听说的是坐着脚能
着地(整个脚掌)的话,boostseat就不需要了。我儿子8岁的时候直接坐了。

【在 p******z 的大作中提到】
: 我家老大7岁半了还在坐5harness 的car seat, 而且打算能坐多久就多久, 安全最重
: 要。

avatar
q*x
24
这个不会让写代码吧。

【在 b***e 的大作中提到】
: 看了,还是没能在规定时间写完code..
avatar
n*p
25
I did some research and found the following. I think it
does make sense. Hope it provides some useful information for parents.
Your child has outgrown his convertible seat and needs to
switch car seats when he has reached ONE of these 4 factors:
1. The weight limit of the seat. Check the label on your car
seat or owner's manual.
2. The height limit of the seat. Check the label on your car
seat or owner's manual.
3. When his shoulders have reached the top harness slot of
the car seat.
4. When the top of his ears have reached the top of the car seat.
http://www.carseat-safety.com/switchcarseats.html

【在 p******z 的大作中提到】
: 没有超身高, 只要坐着的时候肩膀不超过坐椅后背就没问题
avatar
b*e
26
public int countComps(int[][] a) {}
让写出这个函数的body.....

【在 q****x 的大作中提到】
: 这个不会让写代码吧。
avatar
q*x
27
1. 图的邻接矩阵表示,反复做乘法可得连通分支。图论定理,但是公式记不清了。
2. 转邻边表,BFS。这个笨办法。
不过电面谈谈思路就差不多了吧?如果提示1的公式倒是也可以写。

【在 b***e 的大作中提到】
: public int countComps(int[][] a) {}
: 让写出这个函数的body.....

avatar
a*d
28
我的看法:
可以把二维数组中的每一个元素看成是图的一个node, 1可以看成是edge. 然后用DFS找
strongly connected components.
avatar
b*e
29
我后来做出来的解法:
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;ifor (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;

}
avatar
a*n
30
电面题目就这么难啊。。。。惨了。。
avatar
b*e
31
前面贴出来的解法还有个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;ifor (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 的大作中提到】
: 电面题目就这么难啊。。。。惨了。。
avatar
z*e
32
MS要求有点过分,简历里面是不是提到vision相关的东西?
Amazon什么组做vision?
avatar
b*e
33
没有任何vision的,这个哥们说他是做catlog清除duplicate那个组的。。。

【在 z***e 的大作中提到】
: MS要求有点过分,简历里面是不是提到vision相关的东西?
: Amazon什么组做vision?

avatar
i*e
34
你这样写貌似复杂了些,面试不会写那么复杂的代码的。
这题可以用 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

avatar
z*e
35
能给点细节吗?

【在 i**********e 的大作中提到】
: 你这样写貌似复杂了些,面试不会写那么复杂的代码的。
: 这题可以用 flood fill 的啊,递归十多行就能搞定。
: 基本就用一个二维数组记录哪些格子是访问过的,然后每一个格子如果还没访问过就进
: 行flood fill。
:
: increase

avatar
d*t
37
第一题是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);

avatar
z*u
38
第二题是不是这个思路
假设我们只需要找出 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);

avatar
b*e
39
第2题我看到的基本解法是从左上开始,对任意元素,查找正上和左边的邻居,然后依
照一些rule来决定当前元素的label值。如果你把邻居都标0的话,恐怕会影响后续元素
的标定。因为一个很重要的rule就是当正上和左边都是相邻元素,但是标定值不同,那
这两个label就是等价的,而当前元素取二者label的最小值。

1

【在 z****u 的大作中提到】
: 第二题是不是这个思路
: 假设我们只需要找出 connected component 的数目:从左上角开始扫描,如果遇到 1
: 的话,cc 数目 + 1,同时递归的把它的值为 1 的邻居置 0。继续扫描直到末尾。
: 扫描一遍就够了。同时每个点最多被扫描两次,值为 1 时一次,为 0 时一次,复杂度
: 应该是 O(n)

avatar
z*u
40
递归的标记为 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

avatar
b*e
41
恩我觉得你说的这个应该是面试官想要的解法,可惜我当时没想到标记为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 */

相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。