o*******g
发帖数: 4 | 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******n
发帖数: 187 | 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*******g
发帖数: 4 | 3 果然如此，但是要如何证明呢。。。
【在 m******n 的大作中提到】
: 最后一题永远是要接近e(2.718)的，所以都是3除了最后。
|
i********s
发帖数: 22 | |
m******n
发帖数: 187 | 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********u
发帖数: 1150 | 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******e
发帖数: 710 | 7 那这道题的答案是不是
如果被3整除，都拆成3
如果被3除余1， 拆出来一个4
如果被3除余2， 拆出来一个2？
【在 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)，以及凸函数的性质，不过具体怎么做
: 不记得了。
|
z*********8
发帖数: 2070 | 8 如果每个字符串5,6个字符怎么办。
这个有什么说法？ |
s********u
发帖数: 1109 | 9 lz这个是第一轮第二轮，是entry level么，感觉明显比我的难呵呵 |
i*******e
发帖数: 69 | 10 如果是unicode 怎么办?
【在 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分钟，面试结束。
|
|
|
b******7
发帖数: 92 | 11 hash或排序
【在 i*******e 的大作中提到】
: 如果是unicode 怎么办?
|
i*******e
发帖数: 69 | 12 不好意思, 没明白。为什么unicode make a difference?
【在 b******7 的大作中提到】
: hash或排序
|
o*******g
发帖数: 4 | 13
这个是当时讨论到如果unicode，用一个256*256的数组来存储字符出现频率，每次来一
个新的字
符串都是init数组，overhead比较大，问如何处理
【在 z*********8 的大作中提到】
: 如果每个字符串5,6个字符怎么办。
: 这个有什么说法？
|
s********u
发帖数: 1109 | 14 我也在想这一点，5-6个元素又有什么差别。。
【在 i*******e 的大作中提到】
: 不好意思, 没明白。为什么unicode make a difference?
|
u*****o
发帖数: 1224 | 15 45分钟做这么难的三道题，g家还让不让人活了？？？ |
c********p
发帖数: 1969 | |
f********x
发帖数: 2086 | 17 感觉leetcode啥的远远不够啊
但是至少保证类似第二题这种要秒杀
LZ45分钟3题已经很好了。 |
b*******e
发帖数: 123 | |
z*****5
发帖数: 38 | 19
如果是ascii码，那只要建一个128个element的数组，再把string遍历一遍，统计每个
字符出现的次数就行了。
如果是unicode，那么建一个几万个element的数组会导致空间吃紧。。。具体咋解决求
高人解惑啊。
如果只有5,6个元素的话就容易了，可以把string sort了找，省下了额外空间。
【在 s********u 的大作中提到】
: 我也在想这一点，5-6个元素又有什么差别。。
|
l*n
发帖数: 529 | 20 如果是unicode一般是文字比较集中的，不太可能出现又有中文又有阿拉伯文的时候。
这种稀疏的情况用hashmap应该是最好的吧。
【在 z*****5 的大作中提到】
:
: 如果是ascii码，那只要建一个128个element的数组，再把string遍历一遍，统计每个
: 字符出现的次数就行了。
: 如果是unicode，那么建一个几万个element的数组会导致空间吃紧。。。具体咋解决求
: 高人解惑啊。
: 如果只有5,6个元素的话就容易了，可以把string sort了找，省下了额外空间。
|
|
|
y****n
发帖数: 743 | 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***g
发帖数: 1492 | 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****5
发帖数: 202 | 23 这道题首先证明没有大于等于5的数。
如果有，拆成3和n-3, 3×(n-3)显然大于n
然后证明不会多于2个2，否则 2+2+2 可以 变成 3+3
当然不会有1.
然后就没有然后了。。。
如果面试时给出这样的证明，还要编程吗？难道就先判断下对3的模，然后输出答案？
【在 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)，以及凸函数的性质，不过具体怎么做
: 不记得了。
|
