logo
Redian新闻
>未名空间
>Biology - 生物学
>
博后申请面试完了就没消息了，求指导
avatar
博后申请面试完了就没消息了，求指导# Biology - 生物学
h*e
1 楼
LeetCode上的据说是Facebook的面试题：
Divide two integers without using multiplication, division and mod operator.
这要考虑正负数，还要考虑溢出的情况。看了解答还是觉得头大。
avatar
m*h
3 楼
方向是生信，复杂疾病遗传学这一块儿。
我只联系了两个老板，都是很想去的地方。第一个回复我说他没有在找博后，推荐我联
系另外俩教授（一个在澳洲一个在欧洲，我比较倾向于去美国就没联系）。另一个是在
MGH的老板，1月底联系的，他去年7月发了一个职位A的广告，1月又转发了一下，然后
说还有另一个职位B。我发了邮件，申请的是A，附上了CV。隔了一周多回邮件，说我们
找个时间聊一下。然后跟他助理约时间约在了2月底电话面试。收到面试之后因为忙着
改文章投文章又忙着写毕业论文又忙着准备面试，我就没联系其他人了。
电话面试只有30min。美国老板一开始就说他发的那个职位已经招到人了，但是呢觉得
我简历不错想先跟我聊聊看，然后看看能不能有别的啥法子work it out。先问了一些
很基础的问题，比如自我介绍啊、职业规划之类的。然后我准备了两个很短的slides，
一个是介绍我刚结束的项目，一个是介绍我正参加的项目因为这个项目正好也和这个老
板想招人的方向有关，也顺便包含了一些：比如我为啥对他的项目感兴趣，以及结合他
最新发的文章我后期想做的课题的思路。因为都正好问到了就都讲了。结果时间很赶，
讲完这个就到时间了。然后老板说：“嗯，我感觉你有很多idea，还有一些情况想跟
你聊一下但是时间来不及了，我们再约个时间再聊一下。” 然后又说：“这样吧，先
让你的推荐人把推荐信发给我。” 我主动提了一个问题比较像了解的关于项目的问题
，然后老板问了一下我的名字怎么发音就结束了。
整体面试下来感觉表现还好。唯一一个地方是我的课题里面有一个变量对面提了一个问
题因为没听懂一个单词感觉没答好。我联系了推荐人，有两封推荐信是确保已经发过去
了，还有一个推荐人答应了我近期会发。但是感觉不太好频繁地确认就没有再核对他发
了没。
3月初跟美国老板那边发邮件问他有没有收到推荐信，没有收到回复。隔了一周之后我
又发了一次想确认一下有没有收到，还是没有回复。其实整个面试互动和对方给的反馈
感觉都是positive的，但是不知道为啥一直不回复，就很尴尬。
已经开始在找别的博后职位了，但是这个位置确实是我的首选，所以一直惦记……
emmmmm 贵版有没有人经历过这种情况呀？求分析，算是被默拒了么= =
avatar
w*x
4 楼

operator.
恩, 除了这题还有一道电面题是字符串乘法, 15分钟
谁能在15分钟内写完那题我立马从图书馆8楼跳下去

【在 h****e 的大作中提到】
: LeetCode上的据说是Facebook的面试题：
: Divide two integers without using multiplication, division and mod operator.
: 这要考虑正负数，还要考虑溢出的情况。看了解答还是觉得头大。
avatar
g*0
6 楼
MGH/哈佛医学院的老板招人还需要登广告吗？都是靠故旧门生内部推荐的，顺序是先定
好了人，才登广告的。广告里的要求都是为那个内定好的人量身定制的，因为根据公平
雇佣法不允许不登广告就招人，因为HR少这一步没法走手续。
你连备胎都不是，move on吧。
avatar
l*8
7 楼
整数除法为什么会有溢出？

operator.

【在 h****e 的大作中提到】
: LeetCode上的据说是Facebook的面试题：
: Divide two integers without using multiplication, division and mod operator.
: 这要考虑正负数，还要考虑溢出的情况。看了解答还是觉得头大。
avatar
H*7
8 楼
认真点，有包子

【在 a9 的大作中提到】
: 剪刀？
avatar
m*h
9 楼
嗯，我的推荐人就是他们同事，也算是内部推荐吧。
广告也不是在naturejobs上面打的，是他发在twitter上面的。
而且他那个位置已经招了人了，如果按照你这个思路就没有必要再面试我了吧……

【在 g********0 的大作中提到】
: MGH/哈佛医学院的老板招人还需要登广告吗？都是靠故旧门生内部推荐的，顺序是先定
: 好了人，才登广告的。广告里的要求都是为那个内定好的人量身定制的，因为根据公平
: 雇佣法不允许不登广告就招人，因为HR少这一步没法走手续。
: 你连备胎都不是，move on吧。
avatar
g*y
10 楼
你买降落伞吧。
在topcoder那儿做比赛的人，我可以肯定地说，至少1000人能在15分钟内写出无错可运
行代码。万一有一个逛到这个版。。。

【在 w****x 的大作中提到】
:
: operator.
: 恩, 除了这题还有一道电面题是字符串乘法, 15分钟
: 谁能在15分钟内写完那题我立马从图书馆8楼跳下去
avatar
a9
11 楼
我理解错了，哈哈。我以为你是光要把管子拿下来。

【在 H******7 的大作中提到】
: 认真点，有包子
avatar
F*Q
12 楼
十有八九是推荐人的推荐力度不够。
avatar
a*g
13 楼
似乎对runtime还有要求
我写过一个，judge large超时了。。。
球大牛完美版code

operator.

【在 h****e 的大作中提到】
: LeetCode上的据说是Facebook的面试题：
: Divide two integers without using multiplication, division and mod operator.
: 这要考虑正负数，还要考虑溢出的情况。看了解答还是觉得头大。
avatar
C*d
14 楼
你这个管子和阀门没有任何正常的上紧方式，也不像那种Sharkbite自咬的管子。所以
，我认为它们二者本来就是一体的，要卸这个阀门才可以。
avatar
g*0
15 楼
同时有好几个内部推荐的话，拼推荐人的名气和面子。

【在 F*Q 的大作中提到】
: 十有八九是推荐人的推荐力度不够。
avatar
p*2
16 楼
public int divide(int dividend, int divisor) // return c=a/b;
{
long a = dividend;
long b = divisor;
if (b == 0)
throw new ArithmeticException();
boolean neg = false;
if (a < 0)
neg = !neg;
if (b < 0)
neg = !neg;
a = Math.abs(a);
b = Math.abs(b);
int d = 0;
while (b << d <= a)
{
d++;
}
int c = 0;
for (int i = d; i >= 0; i--)
{
if (b << i <= a)
{
c |= 1 << i;
a -= b << i;
}
}
if (neg)
c = -c;
return c;
}
avatar
H*7
17 楼
卸阀门不容易啊，是胶水胶的，而且贴着墙，锯下来后面的不够长没法上了。

【在 C*******d 的大作中提到】
: 你这个管子和阀门没有任何正常的上紧方式，也不像那种Sharkbite自咬的管子。所以
: ，我认为它们二者本来就是一体的，要卸这个阀门才可以。
avatar
d*m
18 楼
对你感兴趣，但不是必须招你，他自己已经说了很明确了吧。HMS里稍微像样的老板，
如果遇到真心想招的，是不可能弄不到钱的。付工资的来源很多的
接着找吧

【在 m**h 的大作中提到】
: 嗯，我的推荐人就是他们同事，也算是内部推荐吧。
: 广告也不是在naturejobs上面打的，是他发在twitter上面的。
: 而且他那个位置已经招了人了，如果按照你这个思路就没有必要再面试我了吧……
avatar
p*2
19 楼

对鸡牛来说就是3分钟的事情呀。

【在 g**********y 的大作中提到】
: 你买降落伞吧。
: 在topcoder那儿做比赛的人，我可以肯定地说，至少1000人能在15分钟内写出无错可运
: 行代码。万一有一个逛到这个版。。。
avatar
C*d
20 楼
我看水管是铁的，应该可以把朔料的阀门毁掉重装（最后砂纸打平）。
一个问题，你为什么要卸掉这个管子呢？是这个管子漏了吗？

【在 H******7 的大作中提到】
: 卸阀门不容易啊，是胶水胶的，而且贴着墙，锯下来后面的不够长没法上了。
avatar
d*m
21 楼
如果真的觉得背景还行，你这块在longwood区域或是河对面应该不难找。多投几个试试
吧。
我认识几个生信背景，文章一般的都在还不错的实验室做博后。
avatar
L*Q
22 楼
二爷也是大牛……

【在 p*****2 的大作中提到】
:
: 对鸡牛来说就是3分钟的事情呀。
avatar
H*7
23 楼
这不装洗PP的东西么，Suppose把水管旋下来就行了。
看来是这样的：
This is ACCOR, one piece angle stop & water supply. They make them in Female
Thread or Push On types.
Close water to the house. Disconnect water supply from toilet tank. Put your
hand on angle stop and try to turn it clock wise. See if it spins around
the pipe it that direction. If positive, than it is Push On type angle stop.
It operates on same principle as SharkBite fittings. Go to Home Depot,
purchase 1/2" orange Removal Ring, slip that ring over the copper pipe and
behind the valve and pull towards you. Angle stop will slide out from the
pipe.
If angle stop feels solid and won't move to the right at all than you have
Female Thread angle stop. It is screwed over Male Adaptor. Unscrew it in
counter clock wise motion.
BrassCraft now sells in Home Depot brass/chrome Push On angle stops. They
come in 1/2" COMP x 3/8" COMP size. Get one of those. Also buy new flexible,
ss, braided toilet supply: 3/8" COMP x 7/8" because x 12".
Angle stop just slips over the pipe. No tools needed here. You will need
small channel locks to tighten up water supply line. You can do it all
yourself. If you need help, come back ....
Let me know how you did...

【在 C*******d 的大作中提到】
: 我看水管是铁的，应该可以把朔料的阀门毁掉重装（最后砂纸打平）。
: 一个问题，你为什么要卸掉这个管子呢？是这个管子漏了吗？
avatar
m*h
24 楼
是的。我觉得可能是我面试表现还不够突出吧。
anyway，谢谢回复。
我再找找其他老板

【在 d********m 的大作中提到】
: 对你感兴趣，但不是必须招你，他自己已经说了很明确了吧。HMS里稍微像样的老板，
: 如果遇到真心想招的，是不可能弄不到钱的。付工资的来源很多的
: 接着找吧
avatar
g*e
25 楼
问一个无关的，leetcode上现在还能看出来是哪个公司的题吗？好像从某一时间开始，
公司的tag的删了。
avatar
C*d
26 楼
能旋下来最好了。
我看你的管子像在洗手池下面，为什么不用马桶旁边的管子？

Female
your
stop.

【在 H******7 的大作中提到】
: 这不装洗PP的东西么，Suppose把水管旋下来就行了。
: 看来是这样的：
: This is ACCOR, one piece angle stop & water supply. They make them in Female
: Thread or Push On types.
: Close water to the house. Disconnect water supply from toilet tank. Put your
: hand on angle stop and try to turn it clock wise. See if it spins around
: the pipe it that direction. If positive, than it is Push On type angle stop.
: It operates on same principle as SharkBite fittings. Go to Home Depot,
: purchase 1/2" orange Removal Ring, slip that ring over the copper pipe and
: behind the valve and pull towards you. Angle stop will slide out from the
avatar
c*y
27 楼
说实在话，觉得这个老板挺恶心的
回复下有那么难吗

【在 m**h 的大作中提到】
: 方向是生信，复杂疾病遗传学这一块儿。
: 我只联系了两个老板，都是很想去的地方。第一个回复我说他没有在找博后，推荐我联
: 系另外俩教授（一个在澳洲一个在欧洲，我比较倾向于去美国就没联系）。另一个是在
: MGH的老板，1月底联系的，他去年7月发了一个职位A的广告，1月又转发了一下，然后
: 说还有另一个职位B。我发了邮件，申请的是A，附上了CV。隔了一周多回邮件，说我们
: 找个时间聊一下。然后跟他助理约时间约在了2月底电话面试。收到面试之后因为忙着
: 改文章投文章又忙着写毕业论文又忙着准备面试，我就没联系其他人了。
: 电话面试只有30min。美国老板一开始就说他发的那个职位已经招到人了，但是呢觉得
: 我简历不错想先跟我聊聊看，然后看看能不能有别的啥法子work it out。先问了一些
: 很基础的问题，比如自我介绍啊、职业规划之类的。然后我准备了两个很短的slides，
avatar
L*Q
28 楼
除了leetcode，这儿还有一个我觉得挺有帮助的网站，也是有详细解答和code
http://www.geeksforgeeks.org/

【在 g*****e 的大作中提到】
: 问一个无关的，leetcode上现在还能看出来是哪个公司的题吗？好像从某一时间开始，
: 公司的tag的删了。
avatar
H*7
29 楼
这是网上的照片。我的是在马桶边，而且不是铜管，是PEX管

【在 C*******d 的大作中提到】
: 能旋下来最好了。
: 我看你的管子像在洗手池下面，为什么不用马桶旁边的管子？
:
: Female
: your
: stop.
avatar
d*m
30 楼
good luck

【在 m**h 的大作中提到】
: 是的。我觉得可能是我面试表现还不够突出吧。
: anyway，谢谢回复。
: 我再找找其他老板
avatar
y*u
31 楼
一般来说不会溢出把。。。

operator.

【在 h****e 的大作中提到】
: LeetCode上的据说是Facebook的面试题：
: Divide two integers without using multiplication, division and mod operator.
: 这要考虑正负数，还要考虑溢出的情况。看了解答还是觉得头大。
avatar
c*e
32 楼
看来在铜管出来的、白色塑料盖住的里头应该是螺纹，先把蛇皮管的上头卸下来试试
avatar
g*0
33 楼
这个老板很正常，根本没做什么出格的事，这种老板每天几百个email，连看都看不过
来，就别说回了。
哈佛医学院系统真正恶心的地方在于无时不刻有争名夺利的宫斗剧上演，老板和老板斗
，老板和学生斗，学生和学生斗。。。。。。

【在 c***y 的大作中提到】
: 说实在话，觉得这个老板挺恶心的
: 回复下有那么难吗
avatar
L*Q
34 楼
这种情况会溢出：
a / b
a = INT_MIN
b = -1
得到的结果是INT_MAX + 1

【在 y**********u 的大作中提到】
: 一般来说不会溢出把。。。
:
: operator.
avatar
d*m
36 楼
主要是老板和老板直接斗争相当激烈
不过这种宫斗剧，哪里都一样

【在 g********0 的大作中提到】
: 这个老板很正常，根本没做什么出格的事，这种老板每天几百个email，连看都看不过
: 来，就别说回了。
: 哈佛医学院系统真正恶心的地方在于无时不刻有争名夺利的宫斗剧上演，老板和老板斗
: ，老板和学生斗，学生和学生斗。。。。。。
avatar
y*u
37 楼
嗯，对的。。。
要考虑到这种情况，很不容易啊。。。

【在 L***Q 的大作中提到】
: 这种情况会溢出：
: a / b
: a = INT_MIN
: b = -1
: 得到的结果是INT_MAX + 1
avatar
H*7
38 楼
明天去买个新的angle stop，周末停水再拆。唉，亏大了
avatar
a*e
39 楼
不能算生物的，但是沾边，经常来这个版看看，看到这个帖子想起自己的经历了。觉得
找博后真的是很humilating的事情。。。。。。
之前找了一个老板，因为实验室广告说在actively招人，有很多fellowship可申请，我
就联系了。因为邻近城市，让我先去聊天，在cafe聊了一个小时左右吧，感觉挺好的，
老板当天下午就直接自己发信给我的推荐人联系了。三天后让我去做talk，感觉应该也
还不错，因为talk后跟我的三个推荐人一个个打电话聊了（非常确定至少我的老板肯定
只讲我的好话）。然后居然就一声不吭了，一直过了超过三周，来了封信跟我说因为没
钱所以不能接受我。因为是很match的地方，感觉整个过程也挺好的，所以被拒了真的
很伤心，也没有去找其它的博后了。
P.S. 过了大概半年，忽然好奇招了个什么样的博后，就去实验室看了看。发现广告还
在，但是一个博后都没新招（不是很差的学校招不到人的那种，John hopkins, UCSF这
种档次的）真的不知道这些老板到底想干嘛。
不好意思忽然想起这段经历了，不吐不快。希望楼主好运！
avatar
L*Q
40 楼
受leetcode大牛的启发，function内部结果用long long保存，方便判断溢出，返回时
候转换成int

【在 y**********u 的大作中提到】
: 嗯，对的。。。
: 要考虑到这种情况，很不容易啊。。。
avatar
h*n
41 楼
楼主还真花血本，呵护其PP来了～～
avatar
y*u
42 楼
但是long long也会溢出啊
哦，你的意思是用大的变量类型来保存

【在 L***Q 的大作中提到】
: 受leetcode大牛的启发，function内部结果用long long保存，方便判断溢出，返回时
: 候转换成int
avatar
w*r
43 楼
这个老胡有的时候真是匪夷所思，人有钱就是不一样

【在 h******n 的大作中提到】
: 楼主还真花血本，呵护其PP来了～～
avatar
L*Q
44 楼
你如果是计算两个整数除法，function的参数是int，返回值也是int，内部就用一个更
大，能确保不溢出的变量。leetcode上面atoi的题就是如此，返回值是int，那么就用
long long来计算，返回前判断long long的值是不是已经超过int的范围。

【在 y**********u 的大作中提到】
: 但是long long也会溢出啊
: 哦，你的意思是用大的变量类型来保存
avatar
C*d
45 楼
你能不能把水管的另一端拆开，加个2分头？这样可能要容易得多。

【在 H******7 的大作中提到】
: 明天去买个新的angle stop，周末停水再拆。唉，亏大了
avatar
l*o
46 楼
高精度乘法是原来搞竞赛时候热手用的。。。
avatar
l*a
47 楼
老胡，生命在于折腾！而且一切为了pp~~

【在 H******7 的大作中提到】
: 明天去买个新的angle stop，周末停水再拆。唉，亏大了
avatar
l*b
48 楼

同意。 至少还得搞几个垫子。 不需要编译运行的话我甚至觉得有人15秒能写出来。看
看那些最好纪录，简直太恐怖。

【在 g**********y 的大作中提到】
: 你买降落伞吧。
: 在topcoder那儿做比赛的人，我可以肯定地说，至少1000人能在15分钟内写出无错可运
: 行代码。万一有一个逛到这个版。。。
avatar
w*r
49 楼
哦，你是想说，老胡的生命在于折腾pp？

【在 l******a 的大作中提到】
: 老胡，生命在于折腾！而且一切为了pp~~
avatar
N*N
50 楼
15秒，光敲键盘的速度都没那么快把。。。。

【在 l*********b 的大作中提到】
:
: 同意。 至少还得搞几个垫子。 不需要编译运行的话我甚至觉得有人15秒能写出来。看
: 看那些最好纪录，简直太恐怖。
avatar
k*e
51 楼
我拆过。这个白色的阀和银白色的蛇皮管是连成一体的。白色的阀是套在里面的铜管上
的。没有螺纹。
先停水，把蛇皮管的另外一头解开。然后握着白色的阀一边旋转，一边向外拉。就会慢
慢的从铜管上拉下来。

【在 l******a 的大作中提到】
: 老胡，生命在于折腾！而且一切为了pp~~
avatar
y*g
52 楼
那些都是有template的

【在 l*********b 的大作中提到】
:
: 同意。 至少还得搞几个垫子。 不需要编译运行的话我甚至觉得有人15秒能写出来。看
: 看那些最好纪录，简直太恐怖。
avatar
j*o
53 楼
我卸过几个，用锯子把塑料阀体锯开。
这个鸟东西设计的及其脑残，阀体和铜管间有锯齿状的倒钩铁片。千万别拧，一拧，铜
管上就划出一圈沟。

【在 H******7 的大作中提到】
: http://www.askmehelpdesk.com/attachment.php?attachmentid=1767&s
avatar
i*7
54 楼
int divide(int a, int b)
{
bool flag = false;
if(((1 << 31) & a) != 0){
flag = !flag;
a = ~a + 1;
}
if(((1 << 31) & b) != 0){
flag = !flag;
b = ~b + 1;
}
int digitA = log2(a);
int digitB = log2(b);
cout<int q = 0;
int msb = (digitA - digitB + 1);
for(int i = msb; i >= 0; i--)
{
if((b << i) > a)
{
continue;
}
q |= (1 << i);
a -= (b << i);
}
if(flag){
q = ~q + 1;
}
return q;
}
我原本做的用Bit operation来做的除法，刚才改了一下能跑正负数了。
至于考虑溢出。。不知道是不是要考虑long long int的情况？不然我还能改改？
avatar
H*7
55 楼
昨天整这个东西，上来发问之前，把那软管那头拆下来，然后从stop上硬扯了几下试图
扯下来，又绕着转圈，结果悲剧了，发完帖发现漏水了。只好把stop关掉
avatar
h*e
56 楼
LeetCode上的据说是Facebook的面试题：
Divide two integers without using multiplication, division and mod operator.
这要考虑正负数，还要考虑溢出的情况。看了解答还是觉得头大。
avatar
C*d
57 楼
我估计你把这个阀门已经毁了。不过我觉得这个脑残的阀门就是应该毁掉的，你还是一
鼓作气乘胜追击换个标准的阀门吧，呵呵呵。

【在 H******7 的大作中提到】
: 昨天整这个东西，上来发问之前，把那软管那头拆下来，然后从stop上硬扯了几下试图
: 扯下来，又绕着转圈，结果悲剧了，发完帖发现漏水了。只好把stop关掉
avatar
w*x
58 楼

operator.
恩, 除了这题还有一道电面题是字符串乘法, 15分钟
谁能在15分钟内写完那题我立马从图书馆8楼跳下去

【在 h****e 的大作中提到】
: LeetCode上的据说是Facebook的面试题：
: Divide two integers without using multiplication, division and mod operator.
: 这要考虑正负数，还要考虑溢出的情况。看了解答还是觉得头大。
avatar
l*8
59 楼
整数除法为什么会有溢出？

operator.

【在 h****e 的大作中提到】
: LeetCode上的据说是Facebook的面试题：
: Divide two integers without using multiplication, division and mod operator.
: 这要考虑正负数，还要考虑溢出的情况。看了解答还是觉得头大。
avatar
g*y
60 楼
你买降落伞吧。
在topcoder那儿做比赛的人，我可以肯定地说，至少1000人能在15分钟内写出无错可运
行代码。万一有一个逛到这个版。。。

【在 w****x 的大作中提到】
:
: operator.
: 恩, 除了这题还有一道电面题是字符串乘法, 15分钟
: 谁能在15分钟内写完那题我立马从图书馆8楼跳下去
avatar
a*g
61 楼
似乎对runtime还有要求
我写过一个，judge large超时了。。。
球大牛完美版code

operator.

【在 h****e 的大作中提到】
: LeetCode上的据说是Facebook的面试题：
: Divide two integers without using multiplication, division and mod operator.
: 这要考虑正负数，还要考虑溢出的情况。看了解答还是觉得头大。
avatar
p*2
62 楼
public int divide(int dividend, int divisor) // return c=a/b;
{
long a = dividend;
long b = divisor;
if (b == 0)
throw new ArithmeticException();
boolean neg = false;
if (a < 0)
neg = !neg;
if (b < 0)
neg = !neg;
a = Math.abs(a);
b = Math.abs(b);
int d = 0;
while (b << d <= a)
{
d++;
}
int c = 0;
for (int i = d; i >= 0; i--)
{
if (b << i <= a)
{
c |= 1 << i;
a -= b << i;
}
}
if (neg)
c = -c;
return c;
}
avatar
p*2
63 楼

对鸡牛来说就是3分钟的事情呀。

【在 g**********y 的大作中提到】
: 你买降落伞吧。
: 在topcoder那儿做比赛的人，我可以肯定地说，至少1000人能在15分钟内写出无错可运
: 行代码。万一有一个逛到这个版。。。
avatar
L*Q
64 楼
二爷也是大牛……

【在 p*****2 的大作中提到】
:
: 对鸡牛来说就是3分钟的事情呀。
avatar
g*e
65 楼
问一个无关的，leetcode上现在还能看出来是哪个公司的题吗？好像从某一时间开始，
公司的tag的删了。
avatar
L*Q
66 楼
除了leetcode，这儿还有一个我觉得挺有帮助的网站，也是有详细解答和code
http://www.geeksforgeeks.org/

【在 g*****e 的大作中提到】
: 问一个无关的，leetcode上现在还能看出来是哪个公司的题吗？好像从某一时间开始，
: 公司的tag的删了。
avatar
y*u
67 楼
一般来说不会溢出把。。。

operator.

【在 h****e 的大作中提到】
: LeetCode上的据说是Facebook的面试题：
: Divide two integers without using multiplication, division and mod operator.
: 这要考虑正负数，还要考虑溢出的情况。看了解答还是觉得头大。
avatar
L*Q
68 楼
这种情况会溢出：
a / b
a = INT_MIN
b = -1
得到的结果是INT_MAX + 1

【在 y**********u 的大作中提到】
: 一般来说不会溢出把。。。
:
: operator.
avatar
y*u
69 楼
嗯，对的。。。
要考虑到这种情况，很不容易啊。。。

【在 L***Q 的大作中提到】
: 这种情况会溢出：
: a / b
: a = INT_MIN
: b = -1
: 得到的结果是INT_MAX + 1
avatar
L*Q
70 楼
受leetcode大牛的启发，function内部结果用long long保存，方便判断溢出，返回时
候转换成int

【在 y**********u 的大作中提到】
: 嗯，对的。。。
: 要考虑到这种情况，很不容易啊。。。
avatar
y*u
71 楼
但是long long也会溢出啊
哦，你的意思是用大的变量类型来保存

【在 L***Q 的大作中提到】
: 受leetcode大牛的启发，function内部结果用long long保存，方便判断溢出，返回时
: 候转换成int
avatar
L*Q
72 楼
你如果是计算两个整数除法，function的参数是int，返回值也是int，内部就用一个更
大，能确保不溢出的变量。leetcode上面atoi的题就是如此，返回值是int，那么就用
long long来计算，返回前判断long long的值是不是已经超过int的范围。

【在 y**********u 的大作中提到】
: 但是long long也会溢出啊
: 哦，你的意思是用大的变量类型来保存
avatar
l*o
73 楼
高精度乘法是原来搞竞赛时候热手用的。。。
avatar
l*b
74 楼

同意。 至少还得搞几个垫子。 不需要编译运行的话我甚至觉得有人15秒能写出来。看
看那些最好纪录，简直太恐怖。

【在 g**********y 的大作中提到】
: 你买降落伞吧。
: 在topcoder那儿做比赛的人，我可以肯定地说，至少1000人能在15分钟内写出无错可运
: 行代码。万一有一个逛到这个版。。。
avatar
N*N
75 楼
15秒，光敲键盘的速度都没那么快把。。。。

【在 l*********b 的大作中提到】
:
: 同意。 至少还得搞几个垫子。 不需要编译运行的话我甚至觉得有人15秒能写出来。看
: 看那些最好纪录，简直太恐怖。
avatar
y*g
76 楼
那些都是有template的

【在 l*********b 的大作中提到】
:
: 同意。 至少还得搞几个垫子。 不需要编译运行的话我甚至觉得有人15秒能写出来。看
: 看那些最好纪录，简直太恐怖。
avatar
i*7
77 楼
int divide(int a, int b)
{
bool flag = false;
if(((1 << 31) & a) != 0){
flag = !flag;
a = ~a + 1;
}
if(((1 << 31) & b) != 0){
flag = !flag;
b = ~b + 1;
}
int digitA = log2(a);
int digitB = log2(b);
cout<int q = 0;
int msb = (digitA - digitB + 1);
for(int i = msb; i >= 0; i--)
{
if((b << i) > a)
{
continue;
}
q |= (1 << i);
a -= (b << i);
}
if(flag){
q = ~q + 1;
}
return q;
}
我原本做的用Bit operation来做的除法，刚才改了一下能跑正负数了。
至于考虑溢出。。不知道是不是要考虑long long int的情况？不然我还能改改？
avatar
n*r
78 楼
用c++实现的，在leetcode上一跑就超时。
卡在
dividend = 2147483647
divisor = 1
Code 是：
int divide(int dividend, int divisor){
long a = dividend;
long b = divisor;
bool neg = false;
if(a < 0)
neg = !neg;
if(b < 0)
neg = !neg;
a = abs(a);
b = abs(b);
int d = 0;
while(b<d++;
int c = 0;
for(int i = d; i >=0; i--){
if(b<c |= 1 << i;
a -= b <}
}
if(neg)
c = -c;
return c;
}

【在 p*****2 的大作中提到】
:
: 对鸡牛来说就是3分钟的事情呀。
avatar
H*s
79 楼
divisor 是 1 你就单独判断吧，我还没想到更好的解法。

【在 n****r 的大作中提到】
: 用c++实现的，在leetcode上一跑就超时。
: 卡在
: dividend = 2147483647
: divisor = 1
: Code 是：
: int divide(int dividend, int divisor){
: long a = dividend;
: long b = divisor;
: bool neg = false;
: if(a < 0)
avatar
e*s
80 楼
这种情况怎么搞呢，如果返回值是int

【在 L***Q 的大作中提到】
: 这种情况会溢出：
: a / b
: a = INT_MIN
: b = -1
: 得到的结果是INT_MAX + 1
avatar
H*s
81 楼
内部用long long 处理，返回时再转换为int

【在 e***s 的大作中提到】
: 这种情况怎么搞呢，如果返回值是int
avatar
n*e
82 楼
但是longlong强制转换int的话不就成0了么？
edit:不好意思，强制转换后，是minint吧

【在 H****s 的大作中提到】
: 内部用long long 处理，返回时再转换为int
avatar
H*s
83 楼
要自己加判断， 大于INT_MAX则返回INT_MAX

【在 n***e 的大作中提到】
: 但是longlong强制转换int的话不就成0了么？
: edit:不好意思，强制转换后，是minint吧
avatar
s*y
84 楼
这题时间复杂度是多少
avatar
y*n
85 楼
如果不考虑正负和溢出，一行代码的事。
public static int Div(Int64 a, Int64 b, ref Int64 m)
{
return a >= b << 1 ? (Div(a, b << 1, ref m) << 1) + Div(m, b, ref m) : a
>= b ? (m = a - b) > 0 ? 1 : 1 : (m = a) > 0 ? 0 : 0;
}
public static Int64 Div(Int64 a, Int64 b)
{
if (b == 0)
throw new Exception("Div By 0");
else if ((a == Int64.MinValue) && (b == -1))
throw new Exception("Overflow");
bool neg = (Math.Sign(a) != Math.Sign(b));
Int64 mod = 0;
Int64 result = Div(a, b, ref mod);
return neg ? -result : result;
}
avatar
w*a
86 楼
我想知道这题这么写，面试会算你过么？？
我发誓我没用用"运算符"
int divide(int dividend, int divisor)
{
int result = 0;
__asm
{
mov eax,dividend
cdq
idiv divisor
mov result,eax
}

return result;
}
avatar
w*p
87 楼
如果是电面老老实实的写减法，没有overflow的担心，然后再告诉他可以用bit运算提
高应该也是可以过的吧。如果是bug free 的code
avatar
j*y
88 楼
bit ?
a / b 的 的除法可以做到 log(b / a) 的复杂度吧

【在 w********p 的大作中提到】
: 如果是电面老老实实的写减法，没有overflow的担心，然后再告诉他可以用bit运算提
: 高应该也是可以过的吧。如果是bug free 的code
avatar
w*p
89 楼
public static int Div(Int64 a, Int64 b, ref Int64 m)
这个方程的实现很有可能被认为coding style 不好，看起来，改起来都麻烦。不如多
写几行的好。
我认识的人中确实有题都做出来，但是因为coding style被dream company拒掉的。
code 要简洁加上易懂，易维护。

a

【在 y****n 的大作中提到】
: 如果不考虑正负和溢出，一行代码的事。
: public static int Div(Int64 a, Int64 b, ref Int64 m)
: {
: return a >= b << 1 ? (Div(a, b << 1, ref m) << 1) + Div(m, b, ref m) : a
: >= b ? (m = a - b) > 0 ? 1 : 1 : (m = a) > 0 ? 0 : 0;
: }
: public static Int64 Div(Int64 a, Int64 b)
: {
: if (b == 0)
: throw new Exception("Div By 0");
avatar
w*p
90 楼
我只是认同一个很牛朋友的看法。无bug的解决问题，比有bug的最好算法，更容易pass
interview.
用减法做，速度不是最快的，但是没有overflow的担心。10 分钟写出无bug的code是可
行的。
用bit operation做，更快些，但是对于多数人来说，很难做到10－15分钟内写出无bug
的code.
版上也有人说过面试的时候不要先功最好的算法，而是给出安全的code，再提高。
当然超牛，15秒落地的人随便咋写啦。

【在 j*****y 的大作中提到】
: bit ?
: a / b 的 的除法可以做到 log(b / a) 的复杂度吧
avatar
y*n
91 楼
完全同意你的观点，这个是自己写着玩儿，面试时当然不能这样写。
改良了一下style：
递归O(log(a/b))，没有位运算，忽略负数和除零和溢出情况。
public static int Div(UInt64 a, UInt64 b, ref UInt64 mod)
{
UInt64 b2 = b + b;
if (a >= b2)
{
int r1 = Div(a, b2, ref mod);
int r2 = Div(mod, b, ref mod);
return r1 + r1 + r2;
}
else if (a >= b)
{
mod = a - b;
return 1;
}
else
{
mod = a;
return 0;
}
}

【在 w********p 的大作中提到】
: public static int Div(Int64 a, Int64 b, ref Int64 m)
: 这个方程的实现很有可能被认为coding style 不好，看起来，改起来都麻烦。不如多
: 写几行的好。
: 我认识的人中确实有题都做出来，但是因为coding style被dream company拒掉的。
: code 要简洁加上易懂，易维护。
:
: a
avatar
w*p
92 楼
赞。学习。。。

【在 y****n 的大作中提到】
: 完全同意你的观点，这个是自己写着玩儿，面试时当然不能这样写。
: 改良了一下style：
: 递归O(log(a/b))，没有位运算，忽略负数和除零和溢出情况。
: public static int Div(UInt64 a, UInt64 b, ref UInt64 mod)
: {
: UInt64 b2 = b + b;
: if (a >= b2)
: {
: int r1 = Div(a, b2, ref mod);
: int r2 = Div(mod, b, ref mod);
avatar
y*n
93 楼
这个观点我不太同意。
至少这道题如果用纯减法做，几乎没有通过的可能。
首先，该overflow时自然会overflow，减法也会overflow。
其次，面试中我们必须要考虑算法的实用价值。
比如有人算(2^64)/1，纯减法会算上百年。
当然，我们也并不需要在15分钟之内找到神乎其技的超级算法。
至少应该展示“我在努力优化”。

pass
bug

【在 w********p 的大作中提到】
: 我只是认同一个很牛朋友的看法。无bug的解决问题，比有bug的最好算法，更容易pass
: interview.
: 用减法做，速度不是最快的，但是没有overflow的担心。10 分钟写出无bug的code是可
: 行的。
: 用bit operation做，更快些，但是对于多数人来说，很难做到10－15分钟内写出无bug
: 的code.
: 版上也有人说过面试的时候不要先功最好的算法，而是给出安全的code，再提高。
: 当然超牛，15秒落地的人随便咋写啦。
avatar
b*i
94 楼
减法难道不是一边移位一边减?

【在 y****n 的大作中提到】
: 这个观点我不太同意。
: 至少这道题如果用纯减法做，几乎没有通过的可能。
: 首先，该overflow时自然会overflow，减法也会overflow。
: 其次，面试中我们必须要考虑算法的实用价值。
: 比如有人算(2^64)/1，纯减法会算上百年。
: 当然，我们也并不需要在15分钟之内找到神乎其技的超级算法。
: 至少应该展示“我在努力优化”。
:
: pass
: bug
avatar
w*a
95 楼
减法不需要移位吧
avatar
b*i
96 楼
32位整数的除法当然最多减32次就行了，也就是移位32次。或者说自加32次，比较32次。
其实就是a/b是几位2进制，就最多移几次。

【在 w****a 的大作中提到】
: 减法不需要移位吧
avatar
b*i
97 楼
不用long 也行。直接用负数做，哪怕是正数也变负数。

【在 L***Q 的大作中提到】
: 受leetcode大牛的启发，function内部结果用long long保存，方便判断溢出，返回时
: 候转换成int
avatar
j*y
98 楼
nice.

【在 y****n 的大作中提到】
: 完全同意你的观点，这个是自己写着玩儿，面试时当然不能这样写。
: 改良了一下style：
: 递归O(log(a/b))，没有位运算，忽略负数和除零和溢出情况。
: public static int Div(UInt64 a, UInt64 b, ref UInt64 mod)
: {
: UInt64 b2 = b + b;
: if (a >= b2)
: {
: int r1 = Div(a, b2, ref mod);
: int r2 = Div(mod, b, ref mod);
avatar
j*y
99 楼
感觉这个复杂度是 (log(a/b))^2 阿？

【在 y****n 的大作中提到】
: 完全同意你的观点，这个是自己写着玩儿，面试时当然不能这样写。
: 改良了一下style：
: 递归O(log(a/b))，没有位运算，忽略负数和除零和溢出情况。
: public static int Div(UInt64 a, UInt64 b, ref UInt64 mod)
: {
: UInt64 b2 = b + b;
: if (a >= b2)
: {
: int r1 = Div(a, b2, ref mod);
: int r2 = Div(mod, b, ref mod);
avatar
y*n
100 楼
复杂度是O(log(a/b))。
你可以用Div((UInt64)1 << n, 1, mod)试验一下, n in [0..63]。
递归最深层次为n，递归次数为2n。
我前面贴的代码包含一个bug，当b >= 2^63时会溢出，导致堆栈溢出。
这是修复版。（bug free不容易呀）
public static UInt64 Div(UInt64 a, UInt64 b, ref UInt64 mod)
{
UInt64 b2 = b + b;
if ((b2 > b) && (a >= b2))
{
UInt64 r1 = Div(a, b2, ref mod);
UInt64 r2 = Div(mod, b, ref mod);
return r1 + r1 + r2;
}
else if (a >= b)
{
mod = a - b;
return 1;
}
else
{
mod = a;
return 0;
}
}

【在 j*****y 的大作中提到】
: 感觉这个复杂度是 (log(a/b))^2 阿？
avatar
j*y
101 楼
b 是 int 类型，不会出现 b >= 2^63的情况吧
你的那个递归里面call 了两个 子递归, 感觉说复杂度只是 O(log(a/b))有点不太像

【在 y****n 的大作中提到】
: 复杂度是O(log(a/b))。
: 你可以用Div((UInt64)1 << n, 1, mod)试验一下, n in [0..63]。
: 递归最深层次为n，递归次数为2n。
: 我前面贴的代码包含一个bug，当b >= 2^63时会溢出，导致堆栈溢出。
: 这是修复版。（bug free不容易呀）
: public static UInt64 Div(UInt64 a, UInt64 b, ref UInt64 mod)
: {
: UInt64 b2 = b + b;
: if ((b2 > b) && (a >= b2))
: {
avatar
y*n
102 楼
在我新贴的代码中，纠正了所有的整数类型为 UInt64。
你可以在代码中加个计数器，数一下就知道了。

【在 j*****y 的大作中提到】
: b 是 int 类型，不会出现 b >= 2^63的情况吧
: 你的那个递归里面call 了两个 子递归, 感觉说复杂度只是 O(log(a/b))有点不太像
avatar
n*r
103 楼
用c++实现的，在leetcode上一跑就超时。
卡在
dividend = 2147483647
divisor = 1
Code 是：
int divide(int dividend, int divisor){
long a = dividend;
long b = divisor;
bool neg = false;
if(a < 0)
neg = !neg;
if(b < 0)
neg = !neg;
a = abs(a);
b = abs(b);
int d = 0;
while(b<d++;
int c = 0;
for(int i = d; i >=0; i--){
if(b<c |= 1 << i;
a -= b <}
}
if(neg)
c = -c;
return c;
}

【在 p*****2 的大作中提到】
:
: 对鸡牛来说就是3分钟的事情呀。
avatar
H*s
104 楼
divisor 是 1 你就单独判断吧，我还没想到更好的解法。

【在 n****r 的大作中提到】
: 用c++实现的，在leetcode上一跑就超时。
: 卡在
: dividend = 2147483647
: divisor = 1
: Code 是：
: int divide(int dividend, int divisor){
: long a = dividend;
: long b = divisor;
: bool neg = false;
: if(a < 0)
avatar
e*s
105 楼
这种情况怎么搞呢，如果返回值是int

【在 L***Q 的大作中提到】
: 这种情况会溢出：
: a / b
: a = INT_MIN
: b = -1
: 得到的结果是INT_MAX + 1
avatar
H*s
106 楼
内部用long long 处理，返回时再转换为int

【在 e***s 的大作中提到】
: 这种情况怎么搞呢，如果返回值是int
avatar
n*e
107 楼
但是longlong强制转换int的话不就成0了么？
edit:不好意思，强制转换后，是minint吧

【在 H****s 的大作中提到】
: 内部用long long 处理，返回时再转换为int
avatar
H*s
108 楼
要自己加判断， 大于INT_MAX则返回INT_MAX

【在 n***e 的大作中提到】
: 但是longlong强制转换int的话不就成0了么？
: edit:不好意思，强制转换后，是minint吧
avatar
s*y
109 楼
这题时间复杂度是多少
avatar
y*n
110 楼
如果不考虑正负和溢出，一行代码的事。
public static int Div(Int64 a, Int64 b, ref Int64 m)
{
return a >= b << 1 ? (Div(a, b << 1, ref m) << 1) + Div(m, b, ref m) : a
>= b ? (m = a - b) > 0 ? 1 : 1 : (m = a) > 0 ? 0 : 0;
}
public static Int64 Div(Int64 a, Int64 b)
{
if (b == 0)
throw new Exception("Div By 0");
else if ((a == Int64.MinValue) && (b == -1))
throw new Exception("Overflow");
bool neg = (Math.Sign(a) != Math.Sign(b));
Int64 mod = 0;
Int64 result = Div(a, b, ref mod);
return neg ? -result : result;
}
avatar
w*a
111 楼
我想知道这题这么写，面试会算你过么？？
我发誓我没用用"运算符"
int divide(int dividend, int divisor)
{
int result = 0;
__asm
{
mov eax,dividend
cdq
idiv divisor
mov result,eax
}

return result;
}
avatar
w*p
112 楼
如果是电面老老实实的写减法，没有overflow的担心，然后再告诉他可以用bit运算提
高应该也是可以过的吧。如果是bug free 的code
avatar
j*y
113 楼
bit ?
a / b 的 的除法可以做到 log(b / a) 的复杂度吧

【在 w********p 的大作中提到】
: 如果是电面老老实实的写减法，没有overflow的担心，然后再告诉他可以用bit运算提
: 高应该也是可以过的吧。如果是bug free 的code
avatar
w*p
114 楼
public static int Div(Int64 a, Int64 b, ref Int64 m)
这个方程的实现很有可能被认为coding style 不好，看起来，改起来都麻烦。不如多
写几行的好。
我认识的人中确实有题都做出来，但是因为coding style被dream company拒掉的。
code 要简洁加上易懂，易维护。

a

【在 y****n 的大作中提到】
: 如果不考虑正负和溢出，一行代码的事。
: public static int Div(Int64 a, Int64 b, ref Int64 m)
: {
: return a >= b << 1 ? (Div(a, b << 1, ref m) << 1) + Div(m, b, ref m) : a
: >= b ? (m = a - b) > 0 ? 1 : 1 : (m = a) > 0 ? 0 : 0;
: }
: public static Int64 Div(Int64 a, Int64 b)
: {
: if (b == 0)
: throw new Exception("Div By 0");
avatar
w*p
115 楼
我只是认同一个很牛朋友的看法。无bug的解决问题，比有bug的最好算法，更容易pass
interview.
用减法做，速度不是最快的，但是没有overflow的担心。10 分钟写出无bug的code是可
行的。
用bit operation做，更快些，但是对于多数人来说，很难做到10－15分钟内写出无bug
的code.
版上也有人说过面试的时候不要先功最好的算法，而是给出安全的code，再提高。
当然超牛，15秒落地的人随便咋写啦。

【在 j*****y 的大作中提到】
: bit ?
: a / b 的 的除法可以做到 log(b / a) 的复杂度吧
avatar
y*n
116 楼
完全同意你的观点，这个是自己写着玩儿，面试时当然不能这样写。
改良了一下style：
递归O(log(a/b))，没有位运算，忽略负数和除零和溢出情况。
public static int Div(UInt64 a, UInt64 b, ref UInt64 mod)
{
UInt64 b2 = b + b;
if (a >= b2)
{
int r1 = Div(a, b2, ref mod);
int r2 = Div(mod, b, ref mod);
return r1 + r1 + r2;
}
else if (a >= b)
{
mod = a - b;
return 1;
}
else
{
mod = a;
return 0;
}
}

【在 w********p 的大作中提到】
: public static int Div(Int64 a, Int64 b, ref Int64 m)
: 这个方程的实现很有可能被认为coding style 不好，看起来，改起来都麻烦。不如多
: 写几行的好。
: 我认识的人中确实有题都做出来，但是因为coding style被dream company拒掉的。
: code 要简洁加上易懂，易维护。
:
: a
avatar
w*p
117 楼
赞。学习。。。

【在 y****n 的大作中提到】
: 完全同意你的观点，这个是自己写着玩儿，面试时当然不能这样写。
: 改良了一下style：
: 递归O(log(a/b))，没有位运算，忽略负数和除零和溢出情况。
: public static int Div(UInt64 a, UInt64 b, ref UInt64 mod)
: {
: UInt64 b2 = b + b;
: if (a >= b2)
: {
: int r1 = Div(a, b2, ref mod);
: int r2 = Div(mod, b, ref mod);
avatar
y*n
118 楼
这个观点我不太同意。
至少这道题如果用纯减法做，几乎没有通过的可能。
首先，该overflow时自然会overflow，减法也会overflow。
其次，面试中我们必须要考虑算法的实用价值。
比如有人算(2^64)/1，纯减法会算上百年。
当然，我们也并不需要在15分钟之内找到神乎其技的超级算法。
至少应该展示“我在努力优化”。

pass
bug

【在 w********p 的大作中提到】
: 我只是认同一个很牛朋友的看法。无bug的解决问题，比有bug的最好算法，更容易pass
: interview.
: 用减法做，速度不是最快的，但是没有overflow的担心。10 分钟写出无bug的code是可
: 行的。
: 用bit operation做，更快些，但是对于多数人来说，很难做到10－15分钟内写出无bug
: 的code.
: 版上也有人说过面试的时候不要先功最好的算法，而是给出安全的code，再提高。
: 当然超牛，15秒落地的人随便咋写啦。
avatar
b*i
119 楼
减法难道不是一边移位一边减?

【在 y****n 的大作中提到】
: 这个观点我不太同意。
: 至少这道题如果用纯减法做，几乎没有通过的可能。
: 首先，该overflow时自然会overflow，减法也会overflow。
: 其次，面试中我们必须要考虑算法的实用价值。
: 比如有人算(2^64)/1，纯减法会算上百年。
: 当然，我们也并不需要在15分钟之内找到神乎其技的超级算法。
: 至少应该展示“我在努力优化”。
:
: pass
: bug
avatar
w*a
120 楼
减法不需要移位吧
avatar
b*i
121 楼
32位整数的除法当然最多减32次就行了，也就是移位32次。或者说自加32次，比较32次。
其实就是a/b是几位2进制，就最多移几次。

【在 w****a 的大作中提到】
: 减法不需要移位吧
avatar
b*i
122 楼
不用long 也行。直接用负数做，哪怕是正数也变负数。

【在 L***Q 的大作中提到】
: 受leetcode大牛的启发，function内部结果用long long保存，方便判断溢出，返回时
: 候转换成int
avatar
j*y
123 楼
nice.

【在 y****n 的大作中提到】
: 完全同意你的观点，这个是自己写着玩儿，面试时当然不能这样写。
: 改良了一下style：
: 递归O(log(a/b))，没有位运算，忽略负数和除零和溢出情况。
: public static int Div(UInt64 a, UInt64 b, ref UInt64 mod)
: {
: UInt64 b2 = b + b;
: if (a >= b2)
: {
: int r1 = Div(a, b2, ref mod);
: int r2 = Div(mod, b, ref mod);
avatar
j*y
124 楼
感觉这个复杂度是 (log(a/b))^2 阿？

【在 y****n 的大作中提到】
: 完全同意你的观点，这个是自己写着玩儿，面试时当然不能这样写。
: 改良了一下style：
: 递归O(log(a/b))，没有位运算，忽略负数和除零和溢出情况。
: public static int Div(UInt64 a, UInt64 b, ref UInt64 mod)
: {
: UInt64 b2 = b + b;
: if (a >= b2)
: {
: int r1 = Div(a, b2, ref mod);
: int r2 = Div(mod, b, ref mod);
avatar
y*n
125 楼
复杂度是O(log(a/b))。
你可以用Div((UInt64)1 << n, 1, mod)试验一下, n in [0..63]。
递归最深层次为n，递归次数为2n。
我前面贴的代码包含一个bug，当b >= 2^63时会溢出，导致堆栈溢出。
这是修复版。（bug free不容易呀）
public static UInt64 Div(UInt64 a, UInt64 b, ref UInt64 mod)
{
UInt64 b2 = b + b;
if ((b2 > b) && (a >= b2))
{
UInt64 r1 = Div(a, b2, ref mod);
UInt64 r2 = Div(mod, b, ref mod);
return r1 + r1 + r2;
}
else if (a >= b)
{
mod = a - b;
return 1;
}
else
{
mod = a;
return 0;
}
}

【在 j*****y 的大作中提到】
: 感觉这个复杂度是 (log(a/b))^2 阿？
avatar
j*y
126 楼
b 是 int 类型，不会出现 b >= 2^63的情况吧
你的那个递归里面call 了两个 子递归, 感觉说复杂度只是 O(log(a/b))有点不太像

【在 y****n 的大作中提到】
: 复杂度是O(log(a/b))。
: 你可以用Div((UInt64)1 << n, 1, mod)试验一下, n in [0..63]。
: 递归最深层次为n，递归次数为2n。
: 我前面贴的代码包含一个bug，当b >= 2^63时会溢出，导致堆栈溢出。
: 这是修复版。（bug free不容易呀）
: public static UInt64 Div(UInt64 a, UInt64 b, ref UInt64 mod)
: {
: UInt64 b2 = b + b;
: if ((b2 > b) && (a >= b2))
: {
avatar
y*n
127 楼
在我新贴的代码中，纠正了所有的整数类型为 UInt64。
你可以在代码中加个计数器，数一下就知道了。

【在 j*****y 的大作中提到】
: b 是 int 类型，不会出现 b >= 2^63的情况吧
: 你的那个递归里面call 了两个 子递归, 感觉说复杂度只是 O(log(a/b))有点不太像
avatar
b*g
128 楼
复杂度确实是O(log(a/b))吧，虽然递归了，但是递归之前的和之后的是分开的又合并
了，所以还是lg那么多

【在 j*****y 的大作中提到】
: b 是 int 类型，不会出现 b >= 2^63的情况吧
: 你的那个递归里面call 了两个 子递归, 感觉说复杂度只是 O(log(a/b))有点不太像
avatar
h*e
129 楼
高精度乘除法。。15-20分钟肯定写得完。。除法就写个减法模块就行了。乘法也就是
个加法模块。。
fb没考算法题已经很优待了
相关阅读
[合集] NIH或者其他的经费来源有没有规定回扣的归属呢[合集] 关于在本版建立Journal Club系列的建议（草案）[合集] ptt好文 zz[公告] Biology 版的投票结果[合集] 学生物的对其他行业的看法 (纯属个人的super naive的意见)UCSF听觉生理学家Michael Merzenich 给年轻人的建议[合集] 请教如何测荧光的intensity?新年征文奖励名单[合集] 浓缩蛋白[合集] fellowship要交税吗?觉得做生物的人和其他学科的人真的不同推荐一部跟生物有点关系的爆笑日剧[合集] 顺便问一个问题，长片段PCR[合集] 中兴CELL造假案的全程回顾[合集] 悬浮培养的cell怎么观察phenotype?我是千老钱少工时长前途渺茫 美国生物学博士后面临严峻职业竞争attitudes about aging最后再说一点儿[合集] 我是女生. 我恨生物.
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。