n********k
发帖数: 40 | 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 <ｎ；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);
（我正在写这里） |
l*********8
发帖数: 4642 | |
l*********8
发帖数: 4642 | 3 请问什么是Ribosome？
NV
【在 n********k 的大作中提到】
: 国内数学本科，新加坡计算机博士，读到第三年末不想读了，开始找工作。找了一年，终于找到了脸书，
: 这里面的起伏辛酸相信大家都明白的。如果按照投简历算的话，我找了将近五十多个工
: 作吧，一开始找的都在新加坡，大家应该也没什么兴趣，我就抛出几个小结论吧：1.
: amd ibm都是sb公司，你们懂的；2.我这种情况脸书给了我offer，但我就是无法在新加
: 坡找到SGD4000（相当于美元3300）一个月的工作，不得不感叹这里人工成本太低；3.
: 这里的公司更看重马上就能给公司创收，所以会要求新毕业的学生懂很多具体的技术啊
: 语言啊。
: 1.NV总部。
: >事实：我博士是做GPU的，所以加入NV一直是我的理想。我傻到第一份简历就投给了NV
: ，然后去年九月拿到了我这辈子第一个电话面试，可想而知，被拒。
|
k******I
发帖数: 238 | |
c********g
发帖数: 16 | 5 同问啊，搜了一圈都找不到
【在 l*********8 的大作中提到】
: 请问什么是Ribosome？
:
: NV
|
r******l
发帖数: 10760 | 6 lz最后拿到哪家的offer？在什么地方?
NV
【在 n********k 的大作中提到】
: 国内数学本科，新加坡计算机博士，读到第三年末不想读了，开始找工作。找了一年，终于找到了脸书，
: 这里面的起伏辛酸相信大家都明白的。如果按照投简历算的话，我找了将近五十多个工
: 作吧，一开始找的都在新加坡，大家应该也没什么兴趣，我就抛出几个小结论吧：1.
: amd ibm都是sb公司，你们懂的；2.我这种情况脸书给了我offer，但我就是无法在新加
: 坡找到SGD4000（相当于美元3300）一个月的工作，不得不感叹这里人工成本太低；3.
: 这里的公司更看重马上就能给公司创收，所以会要求新毕业的学生懂很多具体的技术啊
: 语言啊。
: 1.NV总部。
: >事实：我博士是做GPU的，所以加入NV一直是我的理想。我傻到第一份简历就投给了NV
: ，然后去年九月拿到了我这辈子第一个电话面试，可想而知，被拒。
|
n********k
发帖数: 40 | 7 楼上的各位训教的是啊，Robisome我自己也狗不到，是我错了，这就去改主贴~ |
r*******m
发帖数: 457 | 8 LZ码了好多字啊，辛苦啦。最后是来美国工作吗还是在新加坡的脸书，没看很明白。。
。。
看来面试还可以到处去旅游啊，真不错。。。哈哈 |
s******n
发帖数: 3946 | 9 同问
【在 k******I 的大作中提到】
: 变成全0矩阵的那个怎么搞
|
S******y
发帖数: 1330 | 10 印度人的口音我不仅听得懂，我自己都会说
NIU |
|
|
w****x
发帖数: 2483 | 11 我只想问Facebook最近扩张到什么程度了?? |
e***s
发帖数: 799 | |
f*******t
发帖数: 7549 | |
s*******f
发帖数: 1114 | 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
: ，然后去年九月拿到了我这辈子第一个电话面试，可想而知，被拒。
|
b****e
发帖数: 45 | 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
: ，然后去年九月拿到了我这辈子第一个电话面试，可想而知，被拒。
|
P*****f
发帖数: 2272 | 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
: ，然后去年九月拿到了我这辈子第一个电话面试，可想而知，被拒。
|
l***i
发帖数: 1309 | 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. |
b****e
发帖数: 45 | 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)
|
s******n
发帖数: 3946 | 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 (r
if (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)
|
s******n
发帖数: 3946 | 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
|
|
|
s*******f
发帖数: 1114 | 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;
|
n********k
发帖数: 40 | 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的，虽然我没有证明，但是我觉得他妈的电话面试题能有多复杂，就写了一个暴搜。
递归这么写：
每一点
判断是否已然全零，是的话返回“成功”
判断是否已然出了矩阵范围，是的话返回“失败”
叫下一个点的递归，若成功返回“成功”
按键
叫下一个点的递归，若成功返回“成功”
按键
返回“失败” |
n********k
发帖数: 40 | 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之间二分搜索” |
h*********n
发帖数: 46 | 24 首先恭喜楼主了！！！
你能写段程序更好地阐述下这个思想吗？真看的不是很明白，谢谢！！
很确定所以不敢妄议。
【在 n********k 的大作中提到】
: random(double p)我们简称为不公平硬币。
: 那个题那位仁兄的二进制数的解法是可以的。但是好像有一些精度的损失，我也不是很确定所以不敢妄议。
: 说说我的解法，没有精度损失，跟他的思路非常像。
: 比如p是1/2，我们需要扔一次硬币，就是叫一次random()，比如p是1/4，3/4，我们需
: 要扔两次硬币。。。面试官问我：那么如何能知道我们需要扔多少次呢？其实你需要扔
: 的次数等于在0-1区间内进行二分搜索找到这个p需要的搜索数。
: 很好，变种二分搜索。
: 这么写：
: 在a和b之间二分搜索
: 如果a和b都大于等于p，返回1
|
m*******p
发帖数: 141 | 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;
}
这么写可以吗？ |
m******s
发帖数: 1469 | 26 Zan and Cong!
，终于找到了脸书，
NV
【在 n********k 的大作中提到】
: 国内数学本科，新加坡计算机博士，读到第三年末不想读了，开始找工作。找了一年，终于找到了脸书，
: 这里面的起伏辛酸相信大家都明白的。如果按照投简历算的话，我找了将近五十多个工
: 作吧，一开始找的都在新加坡，大家应该也没什么兴趣，我就抛出几个小结论吧：1.
: amd ibm都是sb公司，你们懂的；2.我这种情况脸书给了我offer，但我就是无法在新加
: 坡找到SGD4000（相当于美元3300）一个月的工作，不得不感叹这里人工成本太低；3.
: 这里的公司更看重马上就能给公司创收，所以会要求新毕业的学生懂很多具体的技术啊
: 语言啊。
: 1.NV总部。
: >事实：我博士是做GPU的，所以加入NV一直是我的理想。我傻到第一份简历就投给了NV
: ，然后去年九月拿到了我这辈子第一个电话面试，可想而知，被拒。
|
c****p
发帖数: 6474 | 27 想到个O(m*n)的算法，好像是对的，
没有明确的证明。
【在 k******I 的大作中提到】
: 变成全0矩阵的那个怎么搞
|
t****t
发帖数: 6806 | 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);
|
l*********8
发帖数: 4642 | 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的，虽然我没有证明，但是我觉得他妈的电话面试题能有多复杂，就写了一个暴搜。
: 递归这么写：
: 每一点
: 判断是否已然全零，是的话返回“成功”
: 判断是否已然出了矩阵范围，是的话返回“失败”
: 叫下一个点的递归，若成功返回“成功”
|
l*********8
发帖数: 4642 | 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的，虽然我没有证明，但是我觉得他妈的电话面试题能有多复杂，就写了一个
: 暴搜。
|
|
|
b******v
发帖数: 1493 | 31 愿闻其详
【在 c****p 的大作中提到】
: 想到个O(m*n)的算法，好像是对的，
: 没有明确的证明。
|
s******n
发帖数: 3946 | 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
|
c****p
发帖数: 6474 | 33 O(M*N)时间+O(M+N)空间就能解
【在 l*********8 的大作中提到】
: 写错了，高斯法解n元线性方程组的时间是O(n^3).
: 所以这道题目可以在O( (N*M)^3 )时间解出
|
l*********8
发帖数: 4642 | 34 how to do that?
【在 c****p 的大作中提到】
: O(M*N)时间+O(M+N)空间就能解
|
b******v
发帖数: 1493 | 35 虽然是M*N个变量，但是是binary的，高斯法不适用吧？
【在 l*********8 的大作中提到】
: 写错了，高斯法解n元线性方程组的时间是O(n^3).
: 所以这道题目可以在O( (N*M)^3 )时间解出
|
l*********8
发帖数: 4642 | 36 没问题，计算加法按 1+1 = 0 算就可以了
【在 b******v 的大作中提到】
: 虽然是M*N个变量，但是是binary的，高斯法不适用吧？
|
