Redian新闻
>
NV Paypal G F面经(F G onsite我不能透题 对不起)
avatar
NV Paypal G F面经(F G onsite我不能透题 对不起)# JobHunting - 待字闺中
n*k
1
国内数学本科,新加坡计算机博士,读到第三年末不想读了,开始找工作。找了一年,终于找到了脸书,
这里面的起伏辛酸相信大家都明白的。如果按照投简历算的话,我找了将近五十多个工
作吧,一开始找的都在新加坡,大家应该也没什么兴趣,我就抛出几个小结论吧:1.
amd ibm都是sb公司,你们懂的;2.我这种情况脸书给了我offer,但我就是无法在新加
坡找到SGD4000(相当于美元3300)一个月的工作,不得不感叹这里人工成本太低;3.
这里的公司更看重马上就能给公司创收,所以会要求新毕业的学生懂很多具体的技术啊
语言啊。
1.NV总部。
>事实:我博士是做GPU的,所以加入NV一直是我的理想。我傻到第一份简历就投给了NV
,然后去年九月拿到了我这辈子第一个电话面试,可想而知,被拒。
>题:讲讲你自己;讲讲这一个你做过的项目;你给我讲讲shared memory是什么,应该
怎么用;你给我讲讲atomic operation是什么,怎么用;你会什么语言,各个语言的自
信程度;C++里面的virtual function是什么,pure virtual function是什么;你用过
C++ STL吗;你写过C++样子的CUDA程序吗;你写CUDA怎么debug。
>结论:各位,这话无数人说过,但我是真的有体会,一定不要过早申这种好公司。
2.paypal新加坡
>事实:HR电面,问behaviorial question,忘了。然后onsite,上来写卷子,等卷子打
分,有几个哥们儿就被送走了,然后拉你到小黑屋单面,有cafeteria但不给饭吃。HM
第二轮电面,问behaviorial question。给offer,按新本科生给钱,一个月SGD3800(
USD3100吧),我没去。
>题:SQL操作,我全不会;一堆C++ OOP,忘了;位操作,很简单不说了;单链表排序;
给两个区间,返回boolean是否相交;单链表找环儿;写qsort。
>结论:面试前要吃饱,十点到三点,饿死我了。
3.google悉尼
>事实:这个google真是有趣,十月投的,一周后就有电面,电面我的人是google加州的
。问了三个问题,我胡说了一个,表示不会一个,当时觉得完蛋了。电面后一个半月通
知我去悉尼onsite。google悉尼地点真好。真漂亮。遥望悉尼大桥。澳洲人口音也比较
好理解,比印度人好多了。五轮面试,都是白板写题。他们的笔写到一半没水儿了,
幸好我有自带。中午有个工程师带你吃饭,饭不好吃,你可以趁机问他很多大胆的问题,他对你的
结果没有任何影响。
>题:电面的第一题,你给我讲讲这一段C++程序会输出什么(就是用一个父类的指针指子类然后调overloaded function,我不想蒙就说我不会,我当时恨死C++了);电面的第二题,你最喜欢的语言是什么,如果
你可以自由地改进这个语言,你有什么建议(我瞎扯说我不喜欢malloc,怎么怎么样改
善它,没有说得很好,说了很久后来被打断);电面的第三题,给你一个M*N boolean
矩阵,定义一个操作叫做“在x,y处按键”,这一按将导致x行所有元素和y行所有元素
0变1,1变0,现在给你任意一个矩阵,写个程序打印出任意一系列“按键”操作把它变
成全0矩阵。onsite我签了NDA不能说,但估计各位都见过。一共五轮六道大题,要考你算法
设计和系统设计,基本的套路是:算法设计——给我写一个什么什么,好,给我改善,少一些时间复杂度,少一些空间复杂度,不要用这个,必须用那个一类的;系统设计——给我写一个什么什么,好,现在有十亿用户同时用这个服务,你怎么办,哦分布式是吧,怎么分布啊,服务器间如何沟通啊,我要是给你一些cache你怎么用呢一类的。语法错误没问题。其中有一个面试官一定要让我用java写,弄得我不太开心。
>结论:一定要自带笔!还有就是不管什么情况都要花上三分钟先写下最暴力的解决方案
,以防万一时间不够写不完复杂的,你可以说:吾每次写程序都先写下暴力方案作为
gold,这是吾的习惯。还有想的时候要大声说出来,即便是一个你不确定的解决方案,
你可以说:吾正在想用hash,待吾想一想这能不能用在这个场合。我有一个面试就有五
分钟的寂静,很尴尬的。
4.脸书总部
>事实:我的朋友内推了我,HR给我电话,让我做interview street的一个字符串的题,
叫Ribosome,我很快做出来了。给HR发信,HR通知我第二天他们会来我的学校面试,在此称为一
面。一面是两轮,两个总部来的,问题很弱,应该是小丑测试。通知我一个月后他们会
来脸书新加坡面试,在此称为二面。二面是两轮技术面,非常难,一轮motivation
interview。面试完了就完了,半个月后的现在我拿到了电邮offer。
>题:Ribosome,说白了就是给你一个字典,里面有从DNA到蛋白质的对应,给你一堆输入字符串,都是DNA序列,要你输出蛋白质序列,要求一个小时做出来,还是挺弱的。一面第一题,给你一个函数random(),他是一个完美
的随机数生成函数,1/2 返回0,1/2 返回1,现在你给我写一个random(double p),要
求它以概率p 返回0,概率1-p 返回1,你只能调用random();一面第二题,顺时针打印矩阵。
二面我签了NDA不能说,都是白板写题。但是两个技术面都是程序写的不长,但他会很
不爽语法错误。motivation interview很感人,因为面我的面试官是对脸书的使命深信
不疑的,眼里有光,我被他感染地也深情款款了起来。感叹一下来新加坡的面试官都是
印度人,我见到的只有一个是白人,好在我在新加坡见的惯了,印度人的口音我不仅听
得懂,我自己都会说,所以交流没什么问题。
>结论:带笔带笔带笔。如果你写了一段代码,面试官说哦很好但是我想让你用少一些空
间复杂度,或者不要用递归,或是不要用队列一类的大家都懂吧,这个时候保险的做法
是(如果你觉得有时间的话)再在旁边重新写一遍,不要在原程序上改,很容易错的。
因为当时很紧张,改了这里那里我就忘了,有一个bug,他说你这个不对,我说让我找
找,我找了一下,表示没找到,这应该是我这次二面最大的失误了。还有一个小技巧,
你可以上网查到一个公司的口号,然后写题的时候顺便说出来,我说"done is better
than perfect"的时候面试官笑了,他说我第一次听到有人在面试里说这个。
目前能想到的就是这些了,谢谢版上的老少爷们兄弟姐们,我长期潜水,学到的知识难
以粒数。
祝大家求职之路一帆风顺!
【更新】自己总结的面试的一些小技巧,什么想到了就补上来
1.用C的话写 0 == p, 不要写 p==0,然后无耻地吹嘘一番自己是多么小心谨慎啊~
2.为了防止忘大括号,考虑每写一个{,就在其后加一个//,每写一个},就把最近一个//擦掉,比如:
for(int i = 0; i (我正在写这里)
再比如:
for (int i = 0; i < n; i++){//
if (isTree(i, n))
{
...
...
}else{//
(我正在写这里)
3.跟上一条很像,如果你new了,也做个记号,如果你malloc了,做个记号。每次free或delete就把记号抹掉。
比如:
int* a = new int[n];//delete[]
(我正在写这里)
再比如:
int* a = (int*)malloc(sizeof(int)*n);//free
int* b = (int*)malloc(sizeof(int)*n);
free(b);
(我正在写这里)
avatar
l*8
2
cong & zan!
avatar
l*8
3
请问什么是Ribosome?

NV

【在 n********k 的大作中提到】
: 国内数学本科,新加坡计算机博士,读到第三年末不想读了,开始找工作。找了一年,终于找到了脸书,
: 这里面的起伏辛酸相信大家都明白的。如果按照投简历算的话,我找了将近五十多个工
: 作吧,一开始找的都在新加坡,大家应该也没什么兴趣,我就抛出几个小结论吧:1.
: amd ibm都是sb公司,你们懂的;2.我这种情况脸书给了我offer,但我就是无法在新加
: 坡找到SGD4000(相当于美元3300)一个月的工作,不得不感叹这里人工成本太低;3.
: 这里的公司更看重马上就能给公司创收,所以会要求新毕业的学生懂很多具体的技术啊
: 语言啊。
: 1.NV总部。
: >事实:我博士是做GPU的,所以加入NV一直是我的理想。我傻到第一份简历就投给了NV
: ,然后去年九月拿到了我这辈子第一个电话面试,可想而知,被拒。

avatar
k*I
4
变成全0矩阵的那个怎么搞
avatar
c*g
5
同问啊,搜了一圈都找不到

【在 l*********8 的大作中提到】
: 请问什么是Ribosome?
:
: NV

avatar
r*l
6
lz最后拿到哪家的offer?在什么地方?

NV

【在 n********k 的大作中提到】
: 国内数学本科,新加坡计算机博士,读到第三年末不想读了,开始找工作。找了一年,终于找到了脸书,
: 这里面的起伏辛酸相信大家都明白的。如果按照投简历算的话,我找了将近五十多个工
: 作吧,一开始找的都在新加坡,大家应该也没什么兴趣,我就抛出几个小结论吧:1.
: amd ibm都是sb公司,你们懂的;2.我这种情况脸书给了我offer,但我就是无法在新加
: 坡找到SGD4000(相当于美元3300)一个月的工作,不得不感叹这里人工成本太低;3.
: 这里的公司更看重马上就能给公司创收,所以会要求新毕业的学生懂很多具体的技术啊
: 语言啊。
: 1.NV总部。
: >事实:我博士是做GPU的,所以加入NV一直是我的理想。我傻到第一份简历就投给了NV
: ,然后去年九月拿到了我这辈子第一个电话面试,可想而知,被拒。

avatar
n*k
7
楼上的各位训教的是啊,Robisome我自己也狗不到,是我错了,这就去改主贴~
avatar
r*m
8
LZ码了好多字啊,辛苦啦。最后是来美国工作吗还是在新加坡的脸书,没看很明白。。
。。
看来面试还可以到处去旅游啊,真不错。。。哈哈
avatar
s*n
9
同问

【在 k******I 的大作中提到】
: 变成全0矩阵的那个怎么搞
avatar
S*y
10
印度人的口音我不仅听得懂,我自己都会说
NIU
avatar
w*x
11
我只想问Facebook最近扩张到什么程度了??
avatar
e*s
12
感觉楼主满世界跑啊
avatar
f*t
13
各种题都不会……楼主肯定是大牛
avatar
s*f
14
//zzzz回报本版,码遍本版zzzz
//给你一个函数random(),他是一个完美
//的随机数生成函数,1/2 返回0,1/2 返回1,现在你给我写一个random(double p),要
//求它以概率p 返回0,概率1-p 返回1,你只能调用random();
int RandomOneZero(){
return rand() % 2;
}
int MyRandom(double p){
assert (0 <= p && p <= 1);
if (abs(p - 0.5) < 0.00001)
return RandomOneZero();
else if (p > 0.5){
if (0 == RandomOneZero()){
return 0;
} else {
return MyRandom(2 * (p - 0.5));
}
} else {
if (1 == RandomOneZero()){
return 1;
} else {
return MyRandom(2 * p);
}
}
}
void TestMyRandom(){
for (int i = 0; i < 100; ++i){
printf("%d\t", MyRandom(0.25));
}
}

,终于找到了脸书,
NV

【在 n********k 的大作中提到】
: 国内数学本科,新加坡计算机博士,读到第三年末不想读了,开始找工作。找了一年,终于找到了脸书,
: 这里面的起伏辛酸相信大家都明白的。如果按照投简历算的话,我找了将近五十多个工
: 作吧,一开始找的都在新加坡,大家应该也没什么兴趣,我就抛出几个小结论吧:1.
: amd ibm都是sb公司,你们懂的;2.我这种情况脸书给了我offer,但我就是无法在新加
: 坡找到SGD4000(相当于美元3300)一个月的工作,不得不感叹这里人工成本太低;3.
: 这里的公司更看重马上就能给公司创收,所以会要求新毕业的学生懂很多具体的技术啊
: 语言啊。
: 1.NV总部。
: >事实:我博士是做GPU的,所以加入NV一直是我的理想。我傻到第一份简历就投给了NV
: ,然后去年九月拿到了我这辈子第一个电话面试,可想而知,被拒。

avatar
b*e
15
Biased Random Number Generator 那道题我只想到利用Random()产生一个整数,
然后将其跟 p * INT_MAX比较确定返回0还是1.但这个办法会损失一些精度,有不损失
精度的办法吗?

,终于找到了脸书,
NV

【在 n********k 的大作中提到】
: 国内数学本科,新加坡计算机博士,读到第三年末不想读了,开始找工作。找了一年,终于找到了脸书,
: 这里面的起伏辛酸相信大家都明白的。如果按照投简历算的话,我找了将近五十多个工
: 作吧,一开始找的都在新加坡,大家应该也没什么兴趣,我就抛出几个小结论吧:1.
: amd ibm都是sb公司,你们懂的;2.我这种情况脸书给了我offer,但我就是无法在新加
: 坡找到SGD4000(相当于美元3300)一个月的工作,不得不感叹这里人工成本太低;3.
: 这里的公司更看重马上就能给公司创收,所以会要求新毕业的学生懂很多具体的技术啊
: 语言啊。
: 1.NV总部。
: >事实:我博士是做GPU的,所以加入NV一直是我的理想。我傻到第一份简历就投给了NV
: ,然后去年九月拿到了我这辈子第一个电话面试,可想而知,被拒。

avatar
P*f
16
why you dislike amd and ibm so much? just move on

,终于找到了脸书,
NV
子打
HM
序;
州的
题,他对你的
指子类然后调overloaded function,我不想蒙就说我不会,我当时恨死C++了);电面
的第二题,你最喜欢的语言是什么,如果
boolean
你算法
,少一些时间复杂度,少一些空间复杂度,不要用这个,必须用那个一类的;系统设计
——给我写一个什么什么,好,现在有十亿用户同时用这个服务,你怎么办,哦分布式
是吧,怎么分布啊,服务器间如 >结论:一定要自带笔!还有就是不管什么情况都要
花上三分钟先写下最暴力的解决方案
题,
在此称为一
输入字符串,都是DNA序列,要你输出蛋白质序列,要求一个小时做出来,还是挺弱的
。一面第一题,给你一个函数random(),他是一个完美
打印矩阵。
些空
better
个//擦掉,比如:
free或delete就把记号抹掉。

【在 n********k 的大作中提到】
: 国内数学本科,新加坡计算机博士,读到第三年末不想读了,开始找工作。找了一年,终于找到了脸书,
: 这里面的起伏辛酸相信大家都明白的。如果按照投简历算的话,我找了将近五十多个工
: 作吧,一开始找的都在新加坡,大家应该也没什么兴趣,我就抛出几个小结论吧:1.
: amd ibm都是sb公司,你们懂的;2.我这种情况脸书给了我offer,但我就是无法在新加
: 坡找到SGD4000(相当于美元3300)一个月的工作,不得不感叹这里人工成本太低;3.
: 这里的公司更看重马上就能给公司创收,所以会要求新毕业的学生懂很多具体的技术啊
: 语言啊。
: 1.NV总部。
: >事实:我博士是做GPU的,所以加入NV一直是我的理想。我傻到第一份简历就投给了NV
: ,然后去年九月拿到了我这辈子第一个电话面试,可想而知,被拒。

avatar
l*i
17
The matrix problem.
If the matrix is not too big, then you can treat all possible 0,1 matrix as
a node and do BFS.
If the matrix is big but one of its dimension is small, say, it is m rows
and n columns, and let n<=m and n <=20
then you can enumerate the first row with 2^20, which maps to a 20 bit
integer, each bit indicates whether button mat[0][j] is pushed or not. Once
you have the first row, the rest rows are determined. This algorithm can do
20 x 1000 within seconds.
Useful observations are: you never push a button more than once, and once
you decide the set of buttons to push, the order of push does not matter.
avatar
b*e
18
赞!

,要

【在 s*******f 的大作中提到】
: //zzzz回报本版,码遍本版zzzz
: //给你一个函数random(),他是一个完美
: //的随机数生成函数,1/2 返回0,1/2 返回1,现在你给我写一个random(double p),要
: //求它以概率p 返回0,概率1-p 返回1,你只能调用random();
: int RandomOneZero(){
: return rand() % 2;
: }
: int MyRandom(double p){
: assert (0 <= p && p <= 1);
: if (abs(p - 0.5) < 0.00001)

avatar
s*n
19
用iteration更简洁, 思路是生成一个random的2进制小数,与p的2进制相比较,比p小return 0, 比p大return 1
int rand2(); // return 0/1
int myrandom(double p) {
if (p<0 || p>1) throw exception();
while (p) {
p = p*2;
int bit = floor(p); // 0 or 1
int r = rand2();
if (rif (r>bit) return 1;
p= p-bit;
}
return 1;
}

,要

【在 s*******f 的大作中提到】
: //zzzz回报本版,码遍本版zzzz
: //给你一个函数random(),他是一个完美
: //的随机数生成函数,1/2 返回0,1/2 返回1,现在你给我写一个random(double p),要
: //求它以概率p 返回0,概率1-p 返回1,你只能调用random();
: int RandomOneZero(){
: return rand() % 2;
: }
: int MyRandom(double p){
: assert (0 <= p && p <= 1);
: if (abs(p - 0.5) < 0.00001)

avatar
s*n
20
除了暴力还有其他的方法吗

as
Once
do

【在 l***i 的大作中提到】
: The matrix problem.
: If the matrix is not too big, then you can treat all possible 0,1 matrix as
: a node and do BFS.
: If the matrix is big but one of its dimension is small, say, it is m rows
: and n columns, and let n<=m and n <=20
: then you can enumerate the first row with 2^20, which maps to a 20 bit
: integer, each bit indicates whether button mat[0][j] is pushed or not. Once
: you have the first row, the rest rows are determined. This algorithm can do
: 20 x 1000 within seconds.
: Useful observations are: you never push a button more than once, and once

avatar
s*f
21
很强大。只是看不懂,惭愧,难道是因为不懂 ”2进制小数“ ?

小return 0, 比p大return 1

【在 s******n 的大作中提到】
: 用iteration更简洁, 思路是生成一个random的2进制小数,与p的2进制相比较,比p小return 0, 比p大return 1
: int rand2(); // return 0/1
: int myrandom(double p) {
: if (p<0 || p>1) throw exception();
: while (p) {
: p = p*2;
: int bit = floor(p); // 0 or 1
: int r = rand2();
: if (r: if (r>bit) return 1;

avatar
n*k
22
来说说我自己的解法吧,呵呵,仅供参考啊。
矩阵置零的题思路是这个样子:
1.对于任何一点(x0,y0),“在x0,y0处按键”这个操作或者你不做,或者你只做一次,因为做了n次和做了n-2次效果一样
2.对于任何两点(x0,y0),(x1,y1),“在x0,y0处按键”然后“在x1,y1处按键”和“在x1,y1处按键”然后“在x0,y0处按键”效果一样
3.由于1和2,我们可以从左上角一行一行遍历这个矩阵,用递归;我有种感觉这个问题是NPC的,虽然我没有证明,但是我觉得他妈的电话面试题能有多复杂,就写了一个暴搜。
递归这么写:
每一点
判断是否已然全零,是的话返回“成功”
判断是否已然出了矩阵范围,是的话返回“失败”
叫下一个点的递归,若成功返回“成功”
按键
叫下一个点的递归,若成功返回“成功”
按键
返回“失败”
avatar
n*k
23
random(double p)我们简称为不公平硬币。
那个题那位仁兄的二进制数的解法是可以的。但是好像有一些精度的损失,我也不是很确定所以不敢妄议。
说说我的解法,没有精度损失,跟他的思路非常像。
比如p是1/2,我们需要扔一次硬币,就是叫一次random(),比如p是1/4,3/4,我们需
要扔两次硬币。。。面试官问我:那么如何能知道我们需要扔多少次呢?其实你需要扔
的次数等于在0-1区间内进行二分搜索找到这个p需要的搜索数。
很好,变种二分搜索。
这么写:
在a和b之间二分搜索
如果a和b都大于等于p,返回1
如果a和b都小于等于p,返回0
让c等于a和b的中间数
叫random(),如果结果为1,返回“在c和b之间二分搜索”;如果结果为0,返回“在a和c之间二分搜索”
avatar
h*n
24
首先恭喜楼主了!!!
你能写段程序更好地阐述下这个思想吗?真看的不是很明白,谢谢!!

很确定所以不敢妄议。

【在 n********k 的大作中提到】
: random(double p)我们简称为不公平硬币。
: 那个题那位仁兄的二进制数的解法是可以的。但是好像有一些精度的损失,我也不是很确定所以不敢妄议。
: 说说我的解法,没有精度损失,跟他的思路非常像。
: 比如p是1/2,我们需要扔一次硬币,就是叫一次random(),比如p是1/4,3/4,我们需
: 要扔两次硬币。。。面试官问我:那么如何能知道我们需要扔多少次呢?其实你需要扔
: 的次数等于在0-1区间内进行二分搜索找到这个p需要的搜索数。
: 很好,变种二分搜索。
: 这么写:
: 在a和b之间二分搜索
: 如果a和b都大于等于p,返回1

avatar
m*p
25
int r(double p)
{
if( isEqual(p, 0.0))
return 0;
if( isEqual(p, 1.0))
return 1;
if( isEqual(p, 0.5))
return random();
if(p < 0.5)
return random() && r( (0.5 - p) * 2);
if(p > 0.5)
return random() || r((p - 0.5) * 2);
return -1;
}
这么写可以吗?
avatar
m*s
26
Zan and Cong!

,终于找到了脸书,
NV

【在 n********k 的大作中提到】
: 国内数学本科,新加坡计算机博士,读到第三年末不想读了,开始找工作。找了一年,终于找到了脸书,
: 这里面的起伏辛酸相信大家都明白的。如果按照投简历算的话,我找了将近五十多个工
: 作吧,一开始找的都在新加坡,大家应该也没什么兴趣,我就抛出几个小结论吧:1.
: amd ibm都是sb公司,你们懂的;2.我这种情况脸书给了我offer,但我就是无法在新加
: 坡找到SGD4000(相当于美元3300)一个月的工作,不得不感叹这里人工成本太低;3.
: 这里的公司更看重马上就能给公司创收,所以会要求新毕业的学生懂很多具体的技术啊
: 语言啊。
: 1.NV总部。
: >事实:我博士是做GPU的,所以加入NV一直是我的理想。我傻到第一份简历就投给了NV
: ,然后去年九月拿到了我这辈子第一个电话面试,可想而知,被拒。

avatar
c*p
27
想到个O(m*n)的算法,好像是对的,
没有明确的证明。

【在 k******I 的大作中提到】
: 变成全0矩阵的那个怎么搞
avatar
t*t
28
不要画蛇添足, 楼主讲得很清楚了, 照着写就好了.
int rand_any(double p)
{
double l=0, r=1;
while (1) {
if (l>=p) return 1;
if (r<=p) return 0;
double m=(l+r)/2;
int x=random();
if (x) l=m;
else r=m;
}
}

【在 m*******p 的大作中提到】
: int r(double p)
: {
: if( isEqual(p, 0.0))
: return 0;
: if( isEqual(p, 1.0))
: return 1;
: if( isEqual(p, 0.5))
: return random();
: if(p < 0.5)
: return random() && r( (0.5 - p) * 2);

avatar
l*8
29
这个题目相当于解一个 N*M 元线性方程组,是可以 O( (N*M)^2 ) 解出的,不是NPC。

,因为做了n次和做了n-2次效果一样
在x1,y1处按键”然后“在x0,y0处按键”效果一样
题是NPC的,虽然我没有证明,但是我觉得他妈的电话面试题能有多复杂,就写了一个
暴搜。

【在 n********k 的大作中提到】
: 来说说我自己的解法吧,呵呵,仅供参考啊。
: 矩阵置零的题思路是这个样子:
: 1.对于任何一点(x0,y0),“在x0,y0处按键”这个操作或者你不做,或者你只做一次,因为做了n次和做了n-2次效果一样
: 2.对于任何两点(x0,y0),(x1,y1),“在x0,y0处按键”然后“在x1,y1处按键”和“在x1,y1处按键”然后“在x0,y0处按键”效果一样
: 3.由于1和2,我们可以从左上角一行一行遍历这个矩阵,用递归;我有种感觉这个问题是NPC的,虽然我没有证明,但是我觉得他妈的电话面试题能有多复杂,就写了一个暴搜。
: 递归这么写:
: 每一点
: 判断是否已然全零,是的话返回“成功”
: 判断是否已然出了矩阵范围,是的话返回“失败”
: 叫下一个点的递归,若成功返回“成功”

avatar
l*8
30
写错了,高斯法解n元线性方程组的时间是O(n^3).
所以这道题目可以在O( (N*M)^3 )时间解出

【在 l*********8 的大作中提到】
: 这个题目相当于解一个 N*M 元线性方程组,是可以 O( (N*M)^2 ) 解出的,不是NPC。
:
: ,因为做了n次和做了n-2次效果一样
: 在x1,y1处按键”然后“在x0,y0处按键”效果一样
: 题是NPC的,虽然我没有证明,但是我觉得他妈的电话面试题能有多复杂,就写了一个
: 暴搜。

avatar
b*v
31
愿闻其详

【在 c****p 的大作中提到】
: 想到个O(m*n)的算法,好像是对的,
: 没有明确的证明。

avatar
s*n
32
p可以表示为0.100111010011 ...
随机生成二进制小数X =0.abcdefghijk.... (a,b,c都用random2(),0或者1)
a,b,c依次与p的每位比较,一旦发现不同就知道p比X小或者p比x大,终止循环
想要知道p的每位小数只要乘2取整,比如
0.100111010011 * 10 = 1.00111010011。取整后得到1

【在 s*******f 的大作中提到】
: 很强大。只是看不懂,惭愧,难道是因为不懂 ”2进制小数“ ?
:
: 小return 0, 比p大return 1

avatar
c*p
33
O(M*N)时间+O(M+N)空间就能解

【在 l*********8 的大作中提到】
: 写错了,高斯法解n元线性方程组的时间是O(n^3).
: 所以这道题目可以在O( (N*M)^3 )时间解出

avatar
l*8
34
how to do that?

【在 c****p 的大作中提到】
: O(M*N)时间+O(M+N)空间就能解
avatar
b*v
35
虽然是M*N个变量,但是是binary的,高斯法不适用吧?

【在 l*********8 的大作中提到】
: 写错了,高斯法解n元线性方程组的时间是O(n^3).
: 所以这道题目可以在O( (N*M)^3 )时间解出

avatar
l*8
36
没问题,计算加法按 1+1 = 0 算就可以了

【在 b******v 的大作中提到】
: 虽然是M*N个变量,但是是binary的,高斯法不适用吧?
相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。