借人气问EB3排期 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>EB23 - 劳工卡

借人气问EB3排期

借人气问EB3排期# EB23 - 劳工卡

W*r2013-05-16 07:05

1 楼

好像有几个星期了，都记不起来了，和Google有了电面。几个月前在他家网上Post了一
下Resume，终于他们的Recruiter说想和我谈谈。
电面是用Google Docs进行的，考了几个题，印象不太深了：
(1) 有一个Character Array，存了0-9的字符，比如【1】【2】【3】，请写一个Java
Method，返回这个字符数组代表的数 + 1，也就是返回Character Array【1】【2】【4
】.
public char[] NumberPlusOne(char[] ca)
(2) Binary Tree的一个问题，好像是找和一个给定的浮点最接近的节点吧还是啥的，
反正要用到递归，呵呵。
(3) 描述一个Design的问题的解决，好象是数据流里找匹配啥的，反正最好要先给个优
化初值，再用Binary Search解决的。
电面G家比较满意，马上就安排Onsite了。
到了Onsite那天，我请了假，到他家楼下等着，TMD 连个像样的Lobby都没有，旁边是
厨房还是啥的，一堆人在吃饭，最里面还有人听讲座。我坐在一个没任何靠背的横椅上
，看着来来往往的G人。
面试题目能记起来的好像有：
(1) x^n = y, x/n/y都是整数，y叫做一个啥数来着，姑且叫做Super Cool数吧，忘了，
比如，1^1 = 1， 1^2 = 1×1=1， 1^3 = 1×1×1 = 1 ...
2^1 = 2， 2^2 = 2×2=4， 2^3 = 2×2×2 = 8 ...
现在给你一个整数y，请返回最近的那个Super Cool数，写Code。
(2) 写Code Validate Sudoku的解答是否正确。
(3) 只记得想用LinkedHashMap解决的一个问题，和找first non repeating character
类似的题目。
(4) ... 靠，想不起来其他的了。反正面了5个人吧，每个人有两三道题。
后来没有任何消息，就知道挂了，不Match，Move on了。

s*92013-05-16 07:05

2 楼

09年9月的，如果持续放水，乐观盼望，几月能交485，谢谢！！

d*d2013-05-16 07:05

3 楼

没明白super cool number那个题什么意思
y = y^1,那y自己不就是最近的么?
(1) x^n = y, x/n/y都是整数，y叫做一个啥数来着，姑且叫做Super Cool数吧，忘了，
比如，1^1 = 1， 1^2 = 1×1=1， 1^3 = 1×1×1 = 1 ...
2^1 = 2， 2^2 = 2×2=4， 2^3 = 2×2×2 = 8 ...
现在给你一个整数y，请返回最近的那个Super Cool数，写Code。

Java
【4

【在 W**********r 的大作中提到】

: 好像有几个星期了，都记不起来了，和Google有了电面。几个月前在他家网上Post了一
: 下Resume，终于他们的Recruiter说想和我谈谈。
: 电面是用Google Docs进行的，考了几个题，印象不太深了：
: (1) 有一个Character Array，存了0-9的字符，比如【1】【2】【3】，请写一个Java
: Method，返回这个字符数组代表的数 + 1，也就是返回Character Array【1】【2】【4
: 】.
: public char[] NumberPlusOne(char[] ca)
: (2) Binary Tree的一个问题，好像是找和一个给定的浮点最接近的节点吧还是啥的，
: 反正要用到递归，呵呵。
: (3) 描述一个Design的问题的解决，好象是数据流里找匹配啥的，反正最好要先给个优

s*y2013-05-16 07:05

4 楼

一年？
据说，EB3现在是放水建库存，所以算是“假排期”，不太可能持续放水
不过要是CIR过了，就另当别论

【在 s********9 的大作中提到】

: 09年9月的，如果持续放水，乐观盼望，几月能交485，谢谢！！

w*32013-05-16 07:05

5 楼

Thanks

q*c2013-05-16 07:05

6 楼

乐观的话，八月吧。

W*r2013-05-16 07:05

7 楼

应该是我原题没记清，漏掉条件了，n应该大于1，要不然每个数都是Super Cool了，明显不可能呀 :)
比如给你28，return 27 (=3^3=3*3*3); 给你32，return 36（6^2=6*6)。

了，

【在 d*******d 的大作中提到】

: 没明白super cool number那个题什么意思
: y = y^1,那y自己不就是最近的么?
: (1) x^n = y, x/n/y都是整数，y叫做一个啥数来着，姑且叫做Super Cool数吧，忘了，
: 比如，1^1 = 1， 1^2 = 1×1=1， 1^3 = 1×1×1 = 1 ...
: 2^1 = 2， 2^2 = 2×2=4， 2^3 = 2×2×2 = 8 ...
: 现在给你一个整数y，请返回最近的那个Super Cool数，写Code。
:
: Java
: 【4

f*x2013-05-16 07:05

8 楼

准备好材料等着就是了。

s*n2013-05-16 07:05

9 楼

先算sqrt(x)取上下界。然后遍历判断每个数是不是super fool数。
那位高手有时间仔细做做？看看能否binary search一下？

明显不可能呀 :)

【在 W**********r 的大作中提到】

: 应该是我原题没记清，漏掉条件了，n应该大于1，要不然每个数都是Super Cool了，明显不可能呀 :)
: 比如给你28，return 27 (=3^3=3*3*3); 给你32，return 36（6^2=6*6)。
:
: 了，

N*r2013-05-16 07:05

10 楼

If lucky, in 1-2 months

i*e2013-05-16 07:05

11 楼

应该是 binary search 没错。
复杂度应该是 O( （log n）^2 ).
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

【在 s*****n 的大作中提到】

: 先算sqrt(x)取上下界。然后遍历判断每个数是不是super fool数。
: 那位高手有时间仔细做做？看看能否binary search一下？
:
: 明显不可能呀 :)

d*p2013-05-16 07:05

12 楼

这要看放水到什么时候结束，而且和row关系很大，毕竟eb3c数量不算太多，很可能以
后的决定因素是row的排期而不是eb3c的申请人数了

i*e2013-05-16 07:05

13 楼

LZ，32 的 super cool 应该是 32 才对吧？
因为 32 = 2^5.
刚写了一个程序，利用 binary search 的思路.
首先选定一个 upper bound，也就是 ceiling(log(n)).
然后再 i=2 到 upper bound 每一个做 binary search.
例如，n=32，upper bound = log(32) = 5.
i=2，从 low = 1 到　high = ceiling(n^(1/2))
i=3, 从 low = 1 到 high = ceiling(n^1/3))
..
以此类推...
binary search 的 invariant 就是比较 target 和 middle and middle's next，看哪
一个比较近。如果是离 middle 比较近，那就 middle's next 和它上边的值都可以抛
掉了。相反，那就 middle 和它下边的值就可以抛掉。
这里，我们确保 middle's next 不会大于 high。这个条件可以保证，因为取的是
lower middle = (L+H)/2.
int F(int n, int power) {
return pow((double)n, power);
}
int bSearchNearest(int low, int high, int power, int target) {
int L = low, H = high;
while (L < H) {
int M = L + (H-L)/2;
assert(M >= low && M+1 <= high);
int a = F(M, power);
int b = F(M+1, power);
int diffA = abs(a - target);
int diffB = abs(b - target);
if (diffA < diffB) {
H = M;
} else {
L = M+1;
}
}
assert(L == H);
return F(L, power);
}
const double LOG10_2 = 0.301029996;
int superCool(int n) {
int logN = ceil(log10((double)n) / LOG10_2);
int nearest = 1;
for (int i = 2; i <= logN; i++) {
int upper = ceil(pow((double)n, 1.0/i));
//cout << "i: " << i << " upper: " << upper << " ";
int candidate = bSearchNearest(1, upper, i, n);
//cout << "candidate: " << candidate << endl;
if (abs(candidate - n) < abs(nearest - n)) {
nearest = candidate;
}
}
return nearest;
}
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

R*d2013-05-16 07:05

14 楼

现在八月了，看样还要接着等

i*e2013-05-16 07:05

15 楼

另外一点，关于复杂度的分析：
log N^(1/2) + log N^(1/3) + ... + log N^(1/log N)
= log N (1/2 + 1/3 + ... + 1/log N)
一个很明显的 upper bound 肯定是 O( （log N）^2 ）.
1/2 + 1/3 + ... + 1/log N
这个其实跟著名的 harmonic series 很类似：
http://en.wikipedia.org/wiki/Harmonic_series_%28mathematics%29
根据以上的文章,
1/2 + 1/3 + ... + 1/log N
= ln( log N ) + γ - 1 ，当 N 很大的时候
那么，一个比较 tight 的 upper bound 应该是：
O( log N * ln(log N) )
不知道有没有分析错误，如有的话，请欢迎指正。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

W*r2013-05-16 07:05

16 楼

抱歉，我脑子乱了，You are right ... 所以G家的题很不适合我 :)

【在 i**********e 的大作中提到】

: LZ，32 的 super cool 应该是 32 才对吧？
: 因为 32 = 2^5.
: 刚写了一个程序，利用 binary search 的思路.
: 首先选定一个 upper bound，也就是 ceiling(log(n)).
: 然后再 i=2 到 upper bound 每一个做 binary search.
: 例如，n=32，upper bound = log(32) = 5.
: i=2，从 low = 1 到　high = ceiling(n^(1/2))
: i=3, 从 low = 1 到 high = ceiling(n^1/3))
: ..
: 以此类推...

h*32013-05-16 07:05

17 楼

你得到每个upperbound后，为什么还要binary search呢，难道不是只可能在
upperbound 和 upperbound-1 之间取一个吗？
比如 target is 31,
ceiling(pow(31,1/2)) = 5, 就只需要考虑 2^4 和2^5,
ceiling(pow(31,1/3)) = 4, 就只需要考虑 3^3 和3^4
一直到 ceiling(sqrt(31)) = 6,
ceiling(pow(31,1/6)) = 2, 只考虑 6^2

【在 i**********e 的大作中提到】

i*e2013-05-16 07:05

18 楼

你说的有道理，这样的话复杂度只要 O(logN) :)
貌似像你这样说的是对的（要注意一些边际条件，例如 N = 1,2,3）。
不知道 LZ 能不能说下这题是不是有限制不能调用 sqrt, pow 等函数？
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

【在 h*********3 的大作中提到】

: 你得到每个upperbound后，为什么还要binary search呢，难道不是只可能在
: upperbound 和 upperbound-1 之间取一个吗？
: 比如 target is 31,
: ceiling(pow(31,1/2)) = 5, 就只需要考虑 2^4 和2^5,
: ceiling(pow(31,1/3)) = 4, 就只需要考虑 3^3 和3^4
: 一直到 ceiling(sqrt(31)) = 6,
: ceiling(pow(31,1/6)) = 2, 只考虑 6^2

W*r2013-05-16 07:05

19 楼

不让用，我提到了用Java Math里的类似pow function的，人家让我所有要现写，复杂
度计算都计入其中。
记忆中最后讨论的时候，人家说Upper Bound用y/2就够了，不用很精确，关键是写Code
，就10几20分钟时间吧。

【在 i**********e 的大作中提到】

: 你说的有道理，这样的话复杂度只要 O(logN) :)
: 貌似像你这样说的是对的（要注意一些边际条件，例如 N = 1,2,3）。
: 不知道 LZ 能不能说下这题是不是有限制不能调用 sqrt, pow 等函数？
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com

i*e2013-05-16 07:05

20 楼

恩，那看来还是需要 binary search 的。
这样的话，把所有upper bound 都订在 y/2 就行了。
pow(x, y)，x 和 y 都是整数的情况之下可以用简单的递归实现，复杂度为 O(log(y)).
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

Code

【在 W**********r 的大作中提到】

: 不让用，我提到了用Java Math里的类似pow function的，人家让我所有要现写，复杂
: 度计算都计入其中。
: 记忆中最后讨论的时候，人家说Upper Bound用y/2就够了，不用很精确，关键是写Code
: ，就10几20分钟时间吧。

g*y2013-05-16 07:05

21 楼

写了个算术版的，当作业 :) 假定输入很友善，>=0, 复杂度(N^0.5 * lnN)
public int findSuperCool(int y) {
if (y <= 1) return y;
int superCool = 1;
for (int i=2; ;i++) {
int test = i*i;
if (test-y > Math.abs(y-superCool) || test < 0) break;
int t = findSuperCool(i, y);
if (y-t < Math.abs(superCool - y)) superCool = t;
if (t*i-y < Math.abs(superCool - y)) superCool = t*i;
}
return superCool;
}
private int findSuperCool(int i, int y) {
int t = 1;
while (y > 0) {
y = y / i;
if (y > 0) t *= i;
}
return t;
}

s*y2013-05-16 07:05

22 楼

if (test > y || test < 0) break;
supercool可以比输入大的，是不是阿？

【在 g**********y 的大作中提到】

: 写了个算术版的，当作业 :) 假定输入很友善，>=0, 复杂度(N^0.5 * lnN)
: public int findSuperCool(int y) {
: if (y <= 1) return y;
: int superCool = 1;
: for (int i=2; ;i++) {
: int test = i*i;
: if (test-y > Math.abs(y-superCool) || test < 0) break;
: int t = findSuperCool(i, y);
: if (y-t < Math.abs(superCool - y)) superCool = t;
: if (t*i-y < Math.abs(superCool - y)) superCool = t*i;

g*y2013-05-16 07:05

23 楼

对，边界理解有误，code需要改。

【在 s*****y 的大作中提到】

: if (test > y || test < 0) break;
: supercool可以比输入大的，是不是阿？

s*y2013-05-16 07:05

24 楼

private int findSuperCool(int i, int y) {
int t = 1;
while (y > 0) {
y = y / i;
if (y > 0) t *= i;
}
这个代入 i=2,y = 7， supercool 是8
但是返回了4。

【在 g**********y 的大作中提到】

g*y2013-05-16 07:05

25 楼

改在原贴，应该用findSuperCool(y), 后面这个是helper function。

【在 s*****y 的大作中提到】

: private int findSuperCool(int i, int y) {
: int t = 1;
: while (y > 0) {
: y = y / i;
: if (y > 0) t *= i;
: }
: 这个代入 i=2,y = 7， supercool 是8
: 但是返回了4。

s*y2013-05-16 07:05

26 楼

2个问题:
1.if (test > y || test < 0) break; 这里还是没有改阿,假如y是80,supercool是81,
i是9的时候,test=i*i=81都没有得到81就直接退出了.
2. int t = findSuperCool(i, y);应该是找以i为base的最接近y的cool数吧？
但是代入i=2，y=7，t得出4，而不是8。
难道我理解错了？

【在 g**********y 的大作中提到】

g*y2013-05-16 07:05

27 楼

1. 贴code时贴错了，重新贴过了。
2. t = findSuperCool(i, y)是找比y小的最接近的cool数。supercool数必然是t，或t
*i

81,

【在 s*****y 的大作中提到】

: 2个问题:
: 1.if (test > y || test < 0) break; 这里还是没有改阿,假如y是80,supercool是81,
: i是9的时候,test=i*i=81都没有得到81就直接退出了.
: 2. int t = findSuperCool(i, y);应该是找以i为base的最接近y的cool数吧？
: 但是代入i=2，y=7，t得出4，而不是8。
: 难道我理解错了？

s*y2013-05-16 07:05

28 楼

其实你把判断直接做在这个函数里面，return最接近的cool数，外面再判断哪个cool数
最大
这样子code是不是更加简洁，容易理解阿。

或t

【在 g**********y 的大作中提到】

: 1. 贴code时贴错了，重新贴过了。
: 2. t = findSuperCool(i, y)是找比y小的最接近的cool数。supercool数必然是t，或t
: *i
:
: 81,

g*y2013-05-16 07:05

29 楼

是，更容易理解。

【在 s*****y 的大作中提到】

: 其实你把判断直接做在这个函数里面，return最接近的cool数，外面再判断哪个cool数
: 最大
: 这样子code是不是更加简洁，容易理解阿。
:
: 或t

s*n2013-05-16 07:05

30 楼

写个简单好理解的brute force版得。
int superCool(int y){

int lower = 2;
while ( lower < y)
lower *=2;
int upper = lower;
lower = uppder/2;
for (int i = 3; i < y/3; i++){
int guess = i;
while ( i < y)
guess *= i;
if (guess < upper)
upper = guess;
guess /= i;
if ( guess > lower)
lower = guess;
}
return math.Abs(lower - y) > math.Abs(upper - y) ? upper : lower;
}

【在 g**********y 的大作中提到】

: 是，更容易理解。

g*y2013-05-16 07:05

31 楼

不错，记住上下界是更易读。
Code有点小错，while (i另外用y/3做边界，复杂度就变成N*log(N)；整数越界的时候，程序会死循环。

【在 s*****n 的大作中提到】

: 写个简单好理解的brute force版得。
: int superCool(int y){
:
: int lower = 2;
: while ( lower < y)
: lower *=2;
: int upper = lower;
: lower = uppder/2;
: for (int i = 3; i < y/3; i++){
: int guess = i;