google 电面 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

google 电面

google 电面# JobHunting - 待字闺中

o*g2013-10-09 07:10

1 楼

刚刚结束google电面，面了三题，发布一下攒rp.
第一道题找一个字符串里面频率最高的字符，问了好多小问题，如果是unicode 怎么
办。如果每个字符串5,6个字符怎么办。如果一个机器，四个核怎么处理。在一个
cluster里面，每个机器单核，所有机器互相连接怎么处理（数据量500g，网速 1g/每
秒）问了20分钟左右。
第二个题我刚刚发现是leetcode gas station 新题，还没来得及做。。这个题我想了
15分钟没想到o（n） solution。
第三道题，一个数，比如7可以拆成 1+3+3 或者3+4。求拆成的因子相乘积最大的那个
值。我先给了个 recursion的solution，每次从1开始拆。他说不够有效，然后我又
改成dp，用了10分钟，刚好到45分钟，面试结束。
学艺不精，基本上悲剧了。继续刷题。。

m*n2013-10-09 07:10

2 楼

最后一题永远是要接近e(2.718)的，所以都是3除了最后。

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

: 刚刚结束google电面，面了三题，发布一下攒rp.
: 第一道题找一个字符串里面频率最高的字符，问了好多小问题，如果是unicode 怎么
: 办。如果每个字符串5,6个字符怎么办。如果一个机器，四个核怎么处理。在一个
: cluster里面，每个机器单核，所有机器互相连接怎么处理（数据量500g，网速 1g/每
: 秒）问了20分钟左右。
: 第二个题我刚刚发现是leetcode gas station 新题，还没来得及做。。这个题我想了
: 15分钟没想到o（n） solution。
: 第三道题，一个数，比如7可以拆成 1+3+3 或者3+4。求拆成的因子相乘积最大的那个
: 值。我先给了个 recursion的solution，每次从1开始拆。他说不够有效，然后我又
: 改成dp，用了10分钟，刚好到45分钟，面试结束。

o*g2013-10-09 07:10

3 楼

果然如此，但是要如何证明呢。。。

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

: 最后一题永远是要接近e(2.718)的，所以都是3除了最后。

i*s2013-10-09 07:10

4 楼

第三题贪心就可以了吧

m*n2013-10-09 07:10

5 楼

首先，算数平均值大于几何平均值，可以证明如果把p分成n个数相乘，(p/n)^n是最大
的。
假设x=p/n，把这个数取log，就是p/x*log(x)，对x求导：
-log(x)/x^2+1/x^2=0，也就是说log(x)=1
更直接的办法是利用e=lim(n->inf, (1+1/n)^n)，以及凸函数的性质，不过具体怎么做
不记得了。

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

: 果然如此，但是要如何证明呢。。。

x*u2013-10-09 07:10

6 楼

大哥牛人啊

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

: 首先，算数平均值大于几何平均值，可以证明如果把p分成n个数相乘，(p/n)^n是最大
: 的。
: 假设x=p/n，把这个数取log，就是p/x*log(x)，对x求导：
: -log(x)/x^2+1/x^2=0，也就是说log(x)=1
: 更直接的办法是利用e=lim(n->inf, (1+1/n)^n)，以及凸函数的性质，不过具体怎么做
: 不记得了。

a*e2013-10-09 07:10

7 楼

那这道题的答案是不是
如果被3整除，都拆成3
如果被3除余1，拆出来一个4
如果被3除余2，拆出来一个2？

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

z*82013-10-09 07:10

8 楼

如果每个字符串5,6个字符怎么办。
这个有什么说法？

s*u2013-10-09 07:10

9 楼

lz这个是第一轮第二轮，是entry level么，感觉明显比我的难呵呵

i*e2013-10-09 07:10

10 楼

如果是unicode 怎么办?

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

b*72013-10-09 07:10

11 楼

hash或排序

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

: 如果是unicode 怎么办?

i*e2013-10-09 07:10

12 楼

不好意思, 没明白。为什么unicode make a difference?

【在 b******7 的大作中提到】

: hash或排序

o*g2013-10-09 07:10

13 楼

这个是当时讨论到如果unicode，用一个256*256的数组来存储字符出现频率，每次来一
个新的字
符串都是init数组，overhead比较大，问如何处理

【在 z*********8 的大作中提到】

: 如果每个字符串5,6个字符怎么办。
: 这个有什么说法？

s*u2013-10-09 07:10

14 楼

我也在想这一点，5-6个元素又有什么差别。。

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

: 不好意思, 没明白。为什么unicode make a difference?

u*o2013-10-09 07:10

15 楼

45分钟做这么难的三道题，g家还让不让人活了？？？

c*p2013-10-09 07:10

16 楼

Mark

f*x2013-10-09 07:10

17 楼

感觉leetcode啥的远远不够啊
但是至少保证类似第二题这种要秒杀
LZ45分钟3题已经很好了。

b*e2013-10-09 07:10

18 楼

tough..

z*52013-10-09 07:10

19 楼

如果是ascii码，那只要建一个128个element的数组，再把string遍历一遍，统计每个
字符出现的次数就行了。
如果是unicode，那么建一个几万个element的数组会导致空间吃紧。。。具体咋解决求
高人解惑啊。
如果只有5,6个元素的话就容易了，可以把string sort了找，省下了额外空间。

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

: 我也在想这一点，5-6个元素又有什么差别。。

l*n2013-10-09 07:10

20 楼

如果是unicode一般是文字比较集中的，不太可能出现又有中文又有阿拉伯文的时候。
这种稀疏的情况用hashmap应该是最好的吧。

【在 z*****5 的大作中提到】

:
: 如果是ascii码，那只要建一个128个element的数组，再把string遍历一遍，统计每个
: 字符出现的次数就行了。
: 如果是unicode，那么建一个几万个element的数组会导致空间吃紧。。。具体咋解决求
: 高人解惑啊。
: 如果只有5,6个元素的话就容易了，可以把string sort了找，省下了额外空间。

y*n2013-10-09 07:10

21 楼

试做第三题
public static long GetMaxResult(long n)
{
long[] dp = new long[n + 1];
for (long i = 1; i <= n; i++)
{
long max = i;
for (long j = 1; j <= (i >> 1); j++)
if (j * dp[i - j] > max)
max = j * dp[i - j];
dp[i] = max;
}
return dp[n];
}
1=>1
2=>2
3=>3
4=>4
5=>6
6=>9
7=>12
8=>18
9=>27
10=>36
11=>54
12=>81
13=>108
14=>162
15=>243
16=>324
17=>486
18=>729
19=>972
20=>1458
21=>2187
22=>2916
23=>4374
24=>6561
25=>8748
26=>13122
27=>19683
28=>26244
29=>39366
这道题还有更快解法，但证明正确有些难度

y*g2013-10-09 07:10

22 楼

3×3×。。。×3 if n mod 3 = 0
3×3×。。。×3×4 if n mod 3 = 1
3×3×。。。×3×2 if n mod 3 = 2

d*52013-10-09 07:10

23 楼

这道题首先证明没有大于等于5的数。
如果有，拆成3和n-3, 3×(n-3)显然大于n
然后证明不会多于2个2，否则 2+2+2 可以变成 3+3
当然不会有1.
然后就没有然后了。。。
如果面试时给出这样的证明，还要编程吗？难道就先判断下对3的模，然后输出答案？

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