avatar
NIU是什么东东?# EB23 - 劳工卡
a*r
1
总被问到,总不能让interviewer高兴,请达人指教
Given an array of integers, there is only one integer duplicated, how do you
find this duplicated integer?
avatar
H*i
2
正:NIU是一个工具,需要的时候拿来用。
错:NIU是保姆、保镖、党组织,有义务照顾我。
正:NIU是个空壳,你加入进去出力气才能做点事情。
错:NIU上有四大护法,中有三十六个九袋长老,下有数百员工每天工作八小时。
正:NIU的理事会负责延续组织存在、维护网站、募捐、招聘、协调。
错:NIU的理事会应该干这干那。NIU的理事会啥也不干。如果理事会有美女就奔一个给
我看。
正:NIU还不成熟,会逐渐加强自我监督机制和组织协调能力。
错:NIU真TM操蛋。
我和NIU的关系:我要用NIU的时候就出钱出力、加入NIU、拿着NIU的头衔至少行事方便
一些。我黔马技穷了之后就退出NIU把位子空出来给新鲜血液。
图羊图森破,太傻太天真, 你行你上啊,且行且珍惜!
这二十个字是咱们这个时代的精华浓缩。跟NIU没关系。
以上是我对NIU赤裹裹的概括。
avatar
d*u
3
do you know the range of the data in the array or they can be any integers?
avatar
G*n
4
其实没有绿潮每天看水灌水也很开心的 苦中作乐
avatar
j*l
5
hashmap o(n)
不然排序就要o(nlgn)了吧。
如果要更小的空间时间俺还没想出来或是忘记了。
avatar
K*s
6
湿在人间。。。。。
avatar
h*e
7
我觉得是问问题的人漏了一些附加条件吧,通常的是说数字是
1到N,数组大小是N+1。这样就可以用求和的办法解出。

you

【在 a********r 的大作中提到】
: 总被问到,总不能让interviewer高兴,请达人指教
: Given an array of integers, there is only one integer duplicated, how do you
: find this duplicated integer?

avatar
d*2
8
re

【在 H******i 的大作中提到】
: 正:NIU是一个工具,需要的时候拿来用。
: 错:NIU是保姆、保镖、党组织,有义务照顾我。
: 正:NIU是个空壳,你加入进去出力气才能做点事情。
: 错:NIU上有四大护法,中有三十六个九袋长老,下有数百员工每天工作八小时。
: 正:NIU的理事会负责延续组织存在、维护网站、募捐、招聘、协调。
: 错:NIU的理事会应该干这干那。NIU的理事会啥也不干。如果理事会有美女就奔一个给
: 我看。
: 正:NIU还不成熟,会逐渐加强自我监督机制和组织协调能力。
: 错:NIU真TM操蛋。
: 我和NIU的关系:我要用NIU的时候就出钱出力、加入NIU、拿着NIU的头衔至少行事方便

avatar
p*2
9
XOR就可以了吧?
avatar
b*r
10
Ding

【在 H******i 的大作中提到】
: 正:NIU是一个工具,需要的时候拿来用。
: 错:NIU是保姆、保镖、党组织,有义务照顾我。
: 正:NIU是个空壳,你加入进去出力气才能做点事情。
: 错:NIU上有四大护法,中有三十六个九袋长老,下有数百员工每天工作八小时。
: 正:NIU的理事会负责延续组织存在、维护网站、募捐、招聘、协调。
: 错:NIU的理事会应该干这干那。NIU的理事会啥也不干。如果理事会有美女就奔一个给
: 我看。
: 正:NIU还不成熟,会逐渐加强自我监督机制和组织协调能力。
: 错:NIU真TM操蛋。
: 我和NIU的关系:我要用NIU的时候就出钱出力、加入NIU、拿着NIU的头衔至少行事方便

avatar
c*p
11
xor咋搞

【在 p*****2 的大作中提到】
: XOR就可以了吧?
avatar
f*e
12
老賀,頂!說得好!

【在 H******i 的大作中提到】
: 正:NIU是一个工具,需要的时候拿来用。
: 错:NIU是保姆、保镖、党组织,有义务照顾我。
: 正:NIU是个空壳,你加入进去出力气才能做点事情。
: 错:NIU上有四大护法,中有三十六个九袋长老,下有数百员工每天工作八小时。
: 正:NIU的理事会负责延续组织存在、维护网站、募捐、招聘、协调。
: 错:NIU的理事会应该干这干那。NIU的理事会啥也不干。如果理事会有美女就奔一个给
: 我看。
: 正:NIU还不成熟,会逐渐加强自我监督机制和组织协调能力。
: 错:NIU真TM操蛋。
: 我和NIU的关系:我要用NIU的时候就出钱出力、加入NIU、拿着NIU的头衔至少行事方便

avatar
w*x
13

......... -_-! ..................

【在 p*****2 的大作中提到】
: XOR就可以了吧?
avatar
a*m
14
re

【在 H******i 的大作中提到】
: 正:NIU是一个工具,需要的时候拿来用。
: 错:NIU是保姆、保镖、党组织,有义务照顾我。
: 正:NIU是个空壳,你加入进去出力气才能做点事情。
: 错:NIU上有四大护法,中有三十六个九袋长老,下有数百员工每天工作八小时。
: 正:NIU的理事会负责延续组织存在、维护网站、募捐、招聘、协调。
: 错:NIU的理事会应该干这干那。NIU的理事会啥也不干。如果理事会有美女就奔一个给
: 我看。
: 正:NIU还不成熟,会逐渐加强自我监督机制和组织协调能力。
: 错:NIU真TM操蛋。
: 我和NIU的关系:我要用NIU的时候就出钱出力、加入NIU、拿着NIU的头衔至少行事方便

avatar
L*k
15
XOR的复杂度怎么看,O(1)?

【在 p*****2 的大作中提到】
: XOR就可以了吧?
avatar
x*0
16
zan
avatar
c*p
17
两个元素之间的xor操作是O1的,,一堆元素嘛,,,肯定不是O1的

【在 L*****k 的大作中提到】
: XOR的复杂度怎么看,O(1)?
avatar
m*s
18
都同意,但是那要牛干嘛?
niu是大家支持起来的民间组织,大家支持niu是为了啥?
这都没想清楚。
我不是黑,我也想为大家做事。可是你要我们做啥?
来实在的别老喊口号,而且这么多niu的帖子,怎么版主不合贴了?

【在 H******i 的大作中提到】
: 正:NIU是一个工具,需要的时候拿来用。
: 错:NIU是保姆、保镖、党组织,有义务照顾我。
: 正:NIU是个空壳,你加入进去出力气才能做点事情。
: 错:NIU上有四大护法,中有三十六个九袋长老,下有数百员工每天工作八小时。
: 正:NIU的理事会负责延续组织存在、维护网站、募捐、招聘、协调。
: 错:NIU的理事会应该干这干那。NIU的理事会啥也不干。如果理事会有美女就奔一个给
: 我看。
: 正:NIU还不成熟,会逐渐加强自我监督机制和组织协调能力。
: 错:NIU真TM操蛋。
: 我和NIU的关系:我要用NIU的时候就出钱出力、加入NIU、拿着NIU的头衔至少行事方便

avatar
L*k
19
记得一个说法是即使大量数据做XOR,也是很快,但不知道具体到什么级别~

【在 c****p 的大作中提到】
: 两个元素之间的xor操作是O1的,,一堆元素嘛,,,肯定不是O1的
avatar
l*e
20
回答问号1:NIU目前的主要工作是EB2 SO.
回答问号2:大家支持NIU是因为NIU为中国移民争取权益。
回答问号3:你可以参与NIU的工作,帮助他人帮助自己。
回答问号4:啥叫合贴?

【在 m*****s 的大作中提到】
: 都同意,但是那要牛干嘛?
: niu是大家支持起来的民间组织,大家支持niu是为了啥?
: 这都没想清楚。
: 我不是黑,我也想为大家做事。可是你要我们做啥?
: 来实在的别老喊口号,而且这么多niu的帖子,怎么版主不合贴了?

avatar
c*p
21
那是用了SIMD这类东西吧?

【在 L*****k 的大作中提到】
: 记得一个说法是即使大量数据做XOR,也是很快,但不知道具体到什么级别~
avatar
P*1
22
re
avatar
L*k
23
不确定~~但估计是这种parallel类似的操作

【在 c****p 的大作中提到】
: 那是用了SIMD这类东西吧?
avatar
m*s
24

不太懂意义有多大
多谢再次感谢
我不知道能为组织做什么,多数人进去不知所措反而添乱。
如果牛不嫌麻烦,麻烦列格需要志愿者的工作列表,如果能做,一定申请。
就是不让新开铁讨论

【在 l**********e 的大作中提到】
: 回答问号1:NIU目前的主要工作是EB2 SO.
: 回答问号2:大家支持NIU是因为NIU为中国移民争取权益。
: 回答问号3:你可以参与NIU的工作,帮助他人帮助自己。
: 回答问号4:啥叫合贴?

avatar
p*2
25

还没想好。

【在 c****p 的大作中提到】
: xor咋搞
avatar
c*y
26
你行你上
avatar
c*p
27
有range的话可以用xor搞吧。。
或者是每个元素都是俩,有一个是一个的。。。

【在 p*****2 的大作中提到】
:
: 还没想好。

avatar
i*4
28
不懂就好好做点功课再发言。
自从07年大潮后这么多年中国人EB2/3排期一直停滞不前,就是因为中印捆绑,每年的
SO(多至上万的名额)基本都被老印独吞造成的。
知道每年中国EB2/EB3自己才多少名额吗?2800而已, 有些时候每年实批的甚至还不到
2800。 所以如果按正常人思维,中印统一按排期分配SO,中国人早就没有排期了啊!
不要啥都不懂还整天上窜下跳, 胡搅蛮缠!

【在 m*****s 的大作中提到】
:
: 不太懂意义有多大
: 多谢再次感谢
: 我不知道能为组织做什么,多数人进去不知所措反而添乱。
: 如果牛不嫌麻烦,麻烦列格需要志愿者的工作列表,如果能做,一定申请。
: 就是不让新开铁讨论

avatar
p*2
29

是。刚才没怎么仔细看,以为是这样的问题。
不过我怎么印象这题以前讨论过呀。

【在 c****p 的大作中提到】
: 有range的话可以用xor搞吧。。
: 或者是每个元素都是俩,有一个是一个的。。。

avatar
H*5
30
本来以为是个新人小姑娘来卖萌发问,没想到是赫老湿来给大家讲课
avatar
c*p
31
没idea。。。
找缺元素的题有很多,一般都会给很多条件,
像这道这么general的题不常见。

【在 p*****2 的大作中提到】
:
: 是。刚才没怎么仔细看,以为是这样的问题。
: 不过我怎么印象这题以前讨论过呀。

avatar
H*i
32
新人小姑娘另有其人,又美又聪明又能干。现在正在忙着从USCIS那里企图再为大家抢
几个名额出来。

【在 H***5 的大作中提到】
: 本来以为是个新人小姑娘来卖萌发问,没想到是赫老湿来给大家讲课
avatar
p*2
33

印象中上次也没讨论出所以然来。我再回忆一下。

【在 c****p 的大作中提到】
: 没idea。。。
: 找缺元素的题有很多,一般都会给很多条件,
: 像这道这么general的题不常见。

avatar
H*5
34
那你就给我们多上课多讲笑话好了
avatar
l*o
35
新手初到,写了几行,请大家指点
// this is to produce an integer array with one number duplicated
import java.util.*;
import java.io.*;
public class proAnArray{
public static void main(String[] args) throws IOException{
FileWriter fw = new FileWriter("Array.txt");
int N = 30000;
fw.write(N + "\n");
for(int i = 0; i < N; i++){
fw.write(i + " ");
if (i % 10 == 0) fw.write("\n");
}
int j = 400;
fw.write(j + "\n");
fw.flush();
fw.close();
}
}
// this is to find the duplicated integer from an array
import java.util.*;
import java.io.*;
public class findIt{
public static void main(String[] args) throws IOException{

Scanner in = new Scanner(new File("Array.txt"));
FileWriter fw = new FileWriter("result.txt");
int N = in.nextInt();
boolean[] find = new boolean[N];
boolean stop = false;

while(!stop) {
int i = in.nextInt();
if (find[i]) {
fw.write("This is the duplicated number " + i);
stop = true;
}
else find[i] = true;
}
fw.flush();
fw.close();
}
}
avatar
z*8
36
求和overflow怎么解决?
上次被问到了

【在 h****e 的大作中提到】
: 我觉得是问问题的人漏了一些附加条件吧,通常的是说数字是
: 1到N,数组大小是N+1。这样就可以用求和的办法解出。
:
: you

avatar
a*r
37
The interviewer didn't give any range, so I assume it is any integers.

【在 d******u 的大作中提到】
: do you know the range of the data in the array or they can be any integers?
avatar
N*8
38
google搜了一下的答案,前提是有range,而且是n+1的元素,但是不用加法解,不会溢
出:
Solution: (by Ovidiu Gheorghioiu at Google) Treat the values of the array as
pointers into the same array. Let us call a chain of pointers a “linked
list”. The linked list starting with the last entry must have the shape of
a “lollipop” with a stick and a cycle. Our goal is to identify that node
in the linked list that joins the stick to the cycle. We do so in two phases:
Phase I: maintain two pointers, one ‘slow’ and one ‘fast’. In one round,
the slow pointer advances one step and the fast pointer advances two steps
along the linked list — both pointers advance simultaneously. Phase I comes
to an end when the two pointers become equal at the end of a round.
Phase II: maintain two pointers, both ‘slow’. The first slow pointer
starts where Phase I ended. The second slow pointer starts at the beginning
of the linked list. Phase II ends when these two pointers become equal at
the end of a round. This node, magically, is the duplicate (in other words,
that node in the linked list where the stick joins the cycle)!
但是没看懂怎么从array转化为链表。
avatar
h*3
39
如果range,而且是n+1的元素,xor不就可以了?
要不bitmap?
avatar
s*5
40
这个解法漏掉了一个重要的点,就是要记住beginning node, 来查当前的link是否是
circle还是lollipop. 如果只是简单的circle, 就give up. 而且其中遍历过的数字
,要变成负数,这样不用再把这个数当成linked list的head再查一遍。
比如, 2, 1, 4, 3, 6, 5, 8, 7, 8
会有3个circle, 1个lollipop
2<=>1
4<=>3
6<=>5
8<=>7Phase I needs to find the lollipop entrance
Proof: Let s and c denote the lengths of the stick and the cycle portions of
the lollipop. If the slow pointer in Phase I ends in s + x rounds, then 2(s
+x) = s+x + mc, where m is a positive integer. In other words, s+x = mc. So
in Phase II, by the time the second slow pointer (which starts at the node
where Phase I ended) traverses s nodes, the first slow pointer traverses mc
– x nodes. So both slow pointers become equal at that node where the stick
attaches to the cycle.

as
of
phases:
round,
steps
comes

【在 N*****8 的大作中提到】
: google搜了一下的答案,前提是有range,而且是n+1的元素,但是不用加法解,不会溢
: 出:
: Solution: (by Ovidiu Gheorghioiu at Google) Treat the values of the array as
: pointers into the same array. Let us call a chain of pointers a “linked
: list”. The linked list starting with the last entry must have the shape of
: a “lollipop” with a stick and a cycle. Our goal is to identify that node
: in the linked list that joins the stick to the cycle. We do so in two phases:
: Phase I: maintain two pointers, one ‘slow’ and one ‘fast’. In one round,
: the slow pointer advances one step and the fast pointer advances two steps
: along the linked list — both pointers advance simultaneously. Phase I comes

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