h*********3
发帖数: 111 | 1 有没有人最近on site过，一般多久给消息啊？ | e******a
发帖数: 176 | 2 能不能说说面经？都问了些什么啊？
【在 h*********3 的大作中提到】
: 有没有人最近on site过，一般多久给消息啊？
| g*********s
发帖数: 1782 | 3
move on
了。
这个怎么做？不停用减法有点土吧？
题目就不详
细说了。3个人面食算法加coding, 基本没有新题，版上基本都讨论过。有一个人面试
系统设计,来回
讨论，沟通的不好。我估计是坏在这个人手上。
【在 h*********3 的大作中提到】
: 有没有人最近on site过，一般多久给消息啊？
| m******m
发帖数: 19 | 4 假设已知a,b，求a/b。不妨设a,b同为正数，其他情况保存符号信息。
1.找到一个范围(l,r)使得b*l
这里初始l=0,r=1;然后每次步长翻倍l=r,r=r*2.
2.再在(l,r)里用二分查找找到结果。
【在 g*********s 的大作中提到】
:
: move on
: 了。
: 这个怎么做？不停用减法有点土吧？
: 题目就不详
: 细说了。3个人面食算法加coding, 基本没有新题，版上基本都讨论过。有一个人面试
: 系统设计,来回
: 讨论，沟通的不好。我估计是坏在这个人手上。
| m***g
发帖数: 90 | 5 想知道，二进制与或？
move on
了。
这个怎么做？不停用减法有点土吧？
题目就不详
细说了。3个人面食算法加coding, 基本没有新题，版上基本都讨论过。有一个人面试
系统设计,来回
讨论，沟通的不好。我估计是坏在这个人手上。
【在 g*********s 的大作中提到】
:
: move on
: 了。
: 这个怎么做？不停用减法有点土吧？
: 题目就不详
: 细说了。3个人面食算法加coding, 基本没有新题，版上基本都讨论过。有一个人面试
: 系统设计,来回
: 讨论，沟通的不好。我估计是坏在这个人手上。
| h*********3
发帖数: 111 | 6
面试者想要logN的算法。
我用了额外的空间来存储中间结果。具体做法是：假设我们求a/b, a,b > 0
就把b, 2b, 4b,8b...都存下来，直道某个值xb > a, 然后把a - x/2 b,一直减，
直道最后为0 或者把所有的值都减了。
【在 m***g 的大作中提到】
: 想知道，二进制与或？
:
: move on
: 了。
: 这个怎么做？不停用减法有点土吧？
: 题目就不详
: 细说了。3个人面食算法加coding, 基本没有新题，版上基本都讨论过。有一个人面试
: 系统设计,来回
: 讨论，沟通的不好。我估计是坏在这个人手上。
| l*********y
发帖数: 142 | 7 系统设计怎么搞啊，每次都谈不到什么实质的点子上
move on 了。
题目就不详细说了。3个人面食算法加coding, 基本没有新题，版上基本都讨论过。有
一个人面试系统设计,来回讨论，沟通的不好。我估计是坏在这个人手上。
【在 h*********3 的大作中提到】
:
: 面试者想要logN的算法。
: 我用了额外的空间来存储中间结果。具体做法是：假设我们求a/b, a,b > 0
: 就把b, 2b, 4b,8b...都存下来，直道某个值xb > a, 然后把a - x/2 b,一直减，
: 直道最后为0 或者把所有的值都减了。
| j****a
发帖数: 1277 | 8 这个理由真扯淡 既然不fit 何必开始
move on 了。
题目就不详细说了。3个人面食算法加coding, 基本没有新题，版上基本都讨论过。有
一个人面试系统设计,来回讨论，沟通的不好。我估计是坏在这个人手上。
【在 h*********3 的大作中提到】
:
: 面试者想要logN的算法。
: 我用了额外的空间来存储中间结果。具体做法是：假设我们求a/b, a,b > 0
: 就把b, 2b, 4b,8b...都存下来，直道某个值xb > a, 然后把a - x/2 b,一直减，
: 直道最后为0 或者把所有的值都减了。
| g*********s
发帖数: 1782 | 9 第一步结束后，得到的是2^k*b <= a <=2^(k+1)*b.
然后怎么个二分法？找谁？
【在 m******m 的大作中提到】
: 假设已知a,b，求a/b。不妨设a,b同为正数，其他情况保存符号信息。
: 1.找到一个范围(l,r)使得b*l: 这里初始l=0,r=1;然后每次步长翻倍l=r,r=r*2.
: 2.再在(l,r)里用二分查找找到结果。
| g*********s
发帖数: 1782 | 10
第二步没看懂。假设我们已知2^k*b <= a <= 2^(k+1)*b，怎么个一直减？
比如a=16, b=3，第一步结束时知道12=2^2*3<=16<24=2^3*3，这里的x=8.
然后呢？16 - 8/2*3 = 16-12 = 4，然后呢？
【在 h*********3 的大作中提到】
:
: 面试者想要logN的算法。
: 我用了额外的空间来存储中间结果。具体做法是：假设我们求a/b, a,b > 0
: 就把b, 2b, 4b,8b...都存下来，直道某个值xb > a, 然后把a - x/2 b,一直减，
: 直道最后为0 或者把所有的值都减了。
| | | d****2
发帖数: 12 | 11 You don't have to store the values (b,2b,4b, etc). Use recursion, it
actually stores it for you already.
int DivideR(int a, int& res, int div, int inc)
{
if(inc + inc > a)
{
res = div;
return inc;
}
int t1 = DivideR(a, res, div+div, inc+inc);
int t2 = t1 + inc;
if( t2 <= a)
{
res += div;
return t2;
}
return t1;
}
//assume positive number. Otherwise, check it and adjust accordingly.
int Divide(int a, int b)
{
if(a < b)
return 0;
int res = 0;
DivideR(a, res, 1, b);
return res;
} | j*****u
发帖数: 1133 | 12 A non recursive version:
// Assume a > 0, b > 0.
int Div(int a, int b)
{
int result = 0;
for (int acc = 0; acc + b <= a;)
{
int factor = 1, inc = b;
for (; acc + inc + inc <= a; inc += inc, factor += factor);
acc += inc;
result += factor;
}
return result;
} | g*********s
发帖数: 1782 | 13 can u explain? i don't get it.
【在 j*****u 的大作中提到】
: A non recursive version:
: // Assume a > 0, b > 0.
: int Div(int a, int b)
: {
: int result = 0;
: for (int acc = 0; acc + b <= a;)
: {
: int factor = 1, inc = b;
: for (; acc + inc + inc <= a; inc += inc, factor += factor);
: acc += inc;
| j*****u
发帖数: 1133 | 14 acc是累加结果
内层loop每次尝试倍数1，2，4，8...直到超过a
外层loop从上次的acc开始继续内层loop
比如100/7：
第一次循环到factor=8结束，acc=56，因为7*16 > 100
第二次循环重新从factor=1开始，停止在factor=4，因为56+7*8 > 100
。。。
【在 g*********s 的大作中提到】
: can u explain? i don't get it.
| g*********s
发帖数: 1782 | 15 100/7=14怎么算出来的？
【在 j*****u 的大作中提到】
: acc是累加结果
: 内层loop每次尝试倍数1，2，4，8...直到超过a
: 外层loop从上次的acc开始继续内层loop
: 比如100/7：
: 第一次循环到factor=8结束，acc=56，因为7*16 > 100
: 第二次循环重新从factor=1开始，停止在factor=4，因为56+7*8 > 100
: 。。。
| r****l
发帖数: 28 | 16 //A recursive solution. Assume a>0 and b>0. Easy to change the code with a
sign flag if a or b can be negative.
//Calculate a / b
int divide (int a, int b) {
assert (b > 0);
assert (a > 0);
if (a < b) {
return 0;
}
int result = 1;
int cum = b;
while (cum < a) {
result <<= 1;
cum <<= 1;
}
if (cum == a) {
return result;
}
else {
result >>= 1;
cum >>= 1;
return result + divide(a-cum, b);
}
} | g*********s
发帖数: 1782 | 17 说说思路吧。看不懂啊。
a
【在 r****l 的大作中提到】
: //A recursive solution. Assume a>0 and b>0. Easy to change the code with a
: sign flag if a or b can be negative.
: //Calculate a / b
: int divide (int a, int b) {
: assert (b > 0);
: assert (a > 0);
:
: if (a < b) {
: return 0;
: }
| h*********3
发帖数: 111 | 18
用你的例子：
1) b=3 , 记下 (3,1)
2) b=6 , 记下 (6,2)
3) b=12 , 记下 (12,4)
4) b=24, stop
5) 16>12, tmp=16-12, result += 4 (这个4是第3步里面记下来的)
6) tmp=4, < 6, 跳过 6
7） tmp>3, tmp=tmp-3 result += 1
已经遍历完所以寸的值， 返回result, 5
【在 g*********s 的大作中提到】
: 说说思路吧。看不懂啊。
:
: a
| g*********s
发帖数: 1782 | 19 明白了。多谢。
【在 h*********3 的大作中提到】
:
: 用你的例子：
: 1) b=3 , 记下 (3,1)
: 2) b=6 , 记下 (6,2)
: 3) b=12 , 记下 (12,4)
: 4) b=24, stop
: 5) 16>12, tmp=16-12, result += 4 (这个4是第3步里面记下来的)
: 6) tmp=4, < 6, 跳过 6
: 7） tmp>3, tmp=tmp-3 result += 1
: 已经遍历完所以寸的值， 返回result, 5
|
|
