GoDaddy 2016 ）OA

1. 从LinkedList里面删除值大于给定val的element，这个很简单，跟leetocde remove li

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

1,2,1};
第三题有三个test case超时。。。 攒人品吧

droidgps 发表于 2016-9-21 04:07
这个要超时的

那可不可以用二分呢？首先1..n的和是(1+n)*n/2
left=1, right=n，然后target是abs(target-n)<n；
int left=1, right=n;
while(left<=right){
    int mid = left+(right-left)/2;
    int sum = (1+mid)*mid/2;//sum to the current mid lement
    int prevsum = (1+mid-1)*(mid-1)/2;//sum to the previous element
    if(sum>n && prevsum<=n) return mid-1;
    else if(sum>n && prevsum>n) mid = left+1;
    else mid =right-1;
}
return left;

补充内容 (2016-9-21 04:29):
请无视这句话：”然后target是abs(target-n)<n；“

function main(){
int tmp = 0;
while(tmp<n){
    tmp+=i;
    i++;
}
return i-1;
}
第三题我的理解是这样的：第一个台阶方一块，第二个台阶两块，第三个台阶三块，不是直接求和，直到和大于N就可以了。
话说吐槽一句，找别人内退的，过了一星期了还没OA，是不是简历拒了。。。

补充内容 (2016-9-21 03:47):
抱歉，int i = 0;。。忘记声明了。。

droidgps 发表于 2016-9-21 03:38
你那个是什么原理，我没太看懂，我觉得关键点肯定是用数学原理解出来，但是那点时间，我一下子也没想出好 ...

就是等差数列求和，前n阶的和是 n*(n + 1) / 2，只要这个和大于x就好了，解一个一元二次方程……（-b + sqrt(b ^ 2 - 4ac)） / 2

楼主海投还是内推的呢

Roger_yyzz 发表于 2016-9-20 10:02
楼主海投还是内推的呢

是海投的

youWednesday 发表于 2016-9-20 10:04
是海投的

多长时间收到的回复？

Roger_yyzz 发表于 2016-9-20 10:11
多长时间收到的回复？

第二天一早就收到了

youWednesday 发表于 2016-9-20 10:12
第二天一早就收到了

好的，感谢！

第三题我也遇到了，也是超时，想用hashmap来记住以前算过的值，跑一下也没用，不知道该怎么破。

droidgps 发表于 2016-9-20 10:51
第三题我也遇到了，也是超时，想用hashmap来记住以前算过的值，跑一下也没用，不知道该怎么破。

他有n的constrain，如果提前跑一个程序把每个楼梯需要的个数都存在一个数组里，直接遍历这个数组可不可行

youWednesday 发表于 2016-9-20 10:54
他有n的constrain，如果提前跑一个程序把每个楼梯需要的个数都存在一个数组里，直接遍历这个数组可不可行

我用hashmap就是这个意思，用了之后还是不行。

droidgps 发表于 2016-9-20 13:45
我用hashmap就是这个意思，用了之后还是不行。

不是可以O(1)时间得到吗？x =( -1 + sqrt(1 + 8 * n)) / 2 吗？

不知道是不是我理解错了