G家，请问这样的面试表现拿到offer的几率如何？ - 未名空间MITBBS历史存档

G家，请问这样的面试表现拿到offer的几率如何？# JobHunting - 待字闺中

t*r2016-01-16 08:01

1 楼

楼主fresh ms
今天刚面的g
四轮，第一二轮每轮两题，都是直接给出最优解然后代码写完并且跑了两三个test
case
第三轮只做了一题，题本身不复杂，一个一米长的sidewalk，假设是0-1,设雨滴的宽度
固定为0.01米，每次下雨的位置随机，精度是double，问多少滴雨才能使整个sidewalk
变湿。模拟整个过程。只是面试官一直聊一直聊，一会又问我这个雨滴数的期望是多数
，一会又和我聊什么概率分布什么的，我一直想赶快写赶快写让他再出一题，。。最后
也只写了一题
第四轮，也是一题，也是一个面经题吧，给一个List l和一个number n，让
rearrange这些string，使得每一个string之后至少n个位置，才能出现重复的string。
如果这种结果不止一个，返回任意一个
例如，List = {"a","a","b","b","c","c“},n = 3
return {a,b,c,a,b,c}
这题我面经看到过类似的，应该说也是几分钟就可以写出来了。可能是因为有shadow，
要演示给shadow看？总之interviewer让我做了很多无用的工作，浪费了很多时间，一
直不让我写代码。例如把需要用的数据结构列出来，例如把每一个步骤的时间复杂度空
间复杂度写出来，并解释给他。。。最后也只完成了一题
感觉四轮都还行，没有明显的错误
现在心情有点儿小激动，毕竟G家。各位大大看看，这样的表现是否能拿到offer呀

w*t2016-01-16 08:01

2 楼

感觉后两个都是故意跟你墨迹浪费时间，就算做出来了但是hc看到只做了一道也不是啥
好事。所以如果recruiter跟你说挂了你就举报然后要求加面

m*n2016-01-16 08:01

3 楼

后两个人明显是拿一道题细问的。
你要是回答的还好，你的不耐烦又
没被看出来的话就没事儿。不然就
可能在communication和team work
上被低评。
不是每个人都问两题的。你有点喧宾夺主啊。

sidewalk

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

: 楼主fresh ms
: 今天刚面的g
: 四轮，第一二轮每轮两题，都是直接给出最优解然后代码写完并且跑了两三个test
: case
: 第三轮只做了一题，题本身不复杂，一个一米长的sidewalk，假设是0-1,设雨滴的宽度
: 固定为0.01米，每次下雨的位置随机，精度是double，问多少滴雨才能使整个sidewalk
: 变湿。模拟整个过程。只是面试官一直聊一直聊，一会又问我这个雨滴数的期望是多数
: ，一会又和我聊什么概率分布什么的，我一直想赶快写赶快写让他再出一题，。。最后
: 也只写了一题
: 第四轮，也是一题，也是一个面经题吧，给一个List l和一个number n，让

t*r2016-01-16 08:01

4 楼

是啊，我就是感觉有点儿磨叽时间，我这次准备的还算充分，面经都看的很多，题本身
也刷的认真些吧，基本都是他把题说完我就知道怎么写了，基本上三五分钟就能写完。
但是总是不让我开始，不停的聊，所以我有点儿担心。。。我担心的地方是，我不知道
他在考察什么，不知道他到底想要设呢

【在 w***t 的大作中提到】

: 感觉后两个都是故意跟你墨迹浪费时间，就算做出来了但是hc看到只做了一道也不是啥
: 好事。所以如果recruiter跟你说挂了你就举报然后要求加面

t*r2016-01-16 08:01

5 楼

我肯定没有不耐烦，我只是想尽快做完然后开始下一题
是不一定需要做两题是吗？
面试官考察的都有哪几方面呢？所以现在主要是三个方面打分吗，代码能力，
communication,team work ?

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

: 后两个人明显是拿一道题细问的。
: 你要是回答的还好，你的不耐烦又
: 没被看出来的话就没事儿。不然就
: 可能在communication和team work
: 上被低评。
: 不是每个人都问两题的。你有点喧宾夺主啊。
:
: sidewalk

l*82016-01-16 08:01

6 楼

能不能讨论下最后一题？我经验少没看过。是不是把所有都过一遍，然后首先看是不是
至少有n个不同元素，不是就返回null，然后把n个不同元素各自的数目统计出来。设所
有元素总的数目是N的话，每个元素的数目是m1, m2...mi。那么如果有一个mk，使得N/
(mk-1)这样的话，假设k是数量最多的元素之一，那么用k来划分整个区数组成(mk-1)格，也就
是第一和最后一个都是k，中间尽量都等分，这样分成z格，把其它的元素一个一个放在
这z格里面，比如有一个元素a，有重复ma次，因为ma一定小于等于z，所以把ma个a依次
放在z格里面的话，一定可以使得a符合要求。然后把b，c什么的接着a往下放，因为每
一个element的每一个instance都在不同的格上，所以它们都符合要求，放完了就好了
。是不是这样可以做？

sidewalk

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

: 楼主fresh ms
: 今天刚面的g
: 四轮，第一二轮每轮两题，都是直接给出最优解然后代码写完并且跑了两三个test
: case
: 第三轮只做了一题，题本身不复杂，一个一米长的sidewalk，假设是0-1,设雨滴的宽度
: 固定为0.01米，每次下雨的位置随机，精度是double，问多少滴雨才能使整个sidewalk
: 变湿。模拟整个过程。只是面试官一直聊一直聊，一会又问我这个雨滴数的期望是多数
: ，一会又和我聊什么概率分布什么的，我一直想赶快写赶快写让他再出一题，。。最后
: 也只写了一题
: 第四轮，也是一题，也是一个面经题吧，给一个List l和一个number n，让

t*r2016-01-16 08:01

7 楼

赞！我觉得你的做法是对的，我开始也想这么做，但是一时间没有缕清数学关系，就没
有往下走。但我没有仔细推敲那几个+1和-1的地方对不对，可能还需要小心一些corner
case
我先说一下我的做法
先统计每个string出现的次数
然后用
class Str{
String s;
int count;
}
把每个string建成一个Object并且全部放入最大堆里
同时维护一个queue
每次从堆里取出一个，放入返回的list，然后count - 1，然后把这个Object放进queue
。当queue的size >= n以后，也每一趟都从queue中取出一个Object，如果count > 0
，则放回heap里，否则放回queue中，直至堆空
最后比较返回的list的size和输入的size是否一致，小于输入的size的话，说明无法完
成排序，跑出异常。否则返回结果

N/

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

: 能不能讨论下最后一题？我经验少没看过。是不是把所有都过一遍，然后首先看是不是
: 至少有n个不同元素，不是就返回null，然后把n个不同元素各自的数目统计出来。设所
: 有元素总的数目是N的话，每个元素的数目是m1, m2...mi。那么如果有一个mk，使得N/
: (mk-1): 这样的话，假设k是数量最多的元素之一，那么用k来划分整个区数组成(mk-1)格，也就
: 是第一和最后一个都是k，中间尽量都等分，这样分成z格，把其它的元素一个一个放在
: 这z格里面，比如有一个元素a，有重复ma次，因为ma一定小于等于z，所以把ma个a依次
: 放在z格里面的话，一定可以使得a符合要求。然后把b，c什么的接着a往下放，因为每
: 一个element的每一个instance都在不同的格上，所以它们都符合要求，放完了就好了
: 。是不是这样可以做？

h*k2016-01-16 08:01

8 楼

你题目答得太快，面试官会怀疑你见过这题

t*r2016-01-16 08:01

9 楼

可是。。。。是没见过一模一样的，但是见过类似的，也很快就能做出的呀。。。

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

: 你题目答得太快，面试官会怀疑你见过这题

g*a2016-01-16 08:01

10 楼

lz绝逼大牛，offer毫无疑问。看了你最后一题的解法，想了一个小时，写了代码，是
对的，但还是没想太明白。楼主能给个简略的证明吗？为什么这种贪心策略是对的
? 多谢！

s*x2016-01-16 08:01

11 楼

这个数学关系怎么证明是充分必要条件？

N/

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

: 能不能讨论下最后一题？我经验少没看过。是不是把所有都过一遍，然后首先看是不是
: 至少有n个不同元素，不是就返回null，然后把n个不同元素各自的数目统计出来。设所
: 有元素总的数目是N的话，每个元素的数目是m1, m2...mi。那么如果有一个mk，使得N/
: (mk-1): 这样的话，假设k是数量最多的元素之一，那么用k来划分整个区数组成(mk-1)格，也就
: 是第一和最后一个都是k，中间尽量都等分，这样分成z格，把其它的元素一个一个放在
: 这z格里面，比如有一个元素a，有重复ma次，因为ma一定小于等于z，所以把ma个a依次
: 放在z格里面的话，一定可以使得a符合要求。然后把b，c什么的接着a往下放，因为每
: 一个element的每一个instance都在不同的格上，所以它们都符合要求，放完了就好了
: 。是不是这样可以做？

d*e2016-01-16 08:01

12 楼

不清楚狗狗想考什么，是不是没做够两题HC就一定拒你，但我觉得交流能力不也是一个
非常重要的考察方面吗？我以前有位同事说他面试别人，最讨厌就是什么也不说，上来
就写，写错就当然拒了，但写对也不一定给过，因为一个没有交流的面试他是不会给过
的，怎么也要解释你写的代码是在做什么，为什么这样做。

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

: 可是。。。。是没见过一模一样的，但是见过类似的，也很快就能做出的呀。。。

t*r2016-01-16 08:01

13 楼

谢谢鼓励！真不是什么大牛，只是刷题还算认真，又运气好碰到面经题而已
我准备的时候看到的面经题是，给一个string，重排，使每个字母之间间隔至少一个其
他字母，例如"aabbcc"，可以返回"abacbc"。我面到的题是一个string改成了一堆
string，间隔1个改成了间隔n个
对于原面经题，网上有不少讨论，在一亩三分地里，我觉得对的做法大概就是先统计次
数，如果一个字符出现超过1半，则无法重排
然后，也是用一个maxheap，但是现在不用queue，改成用一个temp变量，temp变量每隔
一轮才再放回heap中，其实也差不多就是size为1的queue
回到我面的那个题，如果要说证明的话，我也不会严格的证明。我的理解是这样：用
堆是可选的，其实你每一趟都是随便选一个当前还可用的string就可以，用堆是保证了
最少的循环次数。但是queue是必须的。这题唯一的要求，就是每个string中间间隔n个
其他string，用queue可以保证这一点，因为只有queue的size >= n，才开始向外Pop。
当然是有可能heap已经为空，但是queue还不为空的情况存在的，但是这就说明原本就
无法完成重排。例如输入是{"a","a","b","b"}, n = 5，显然循环结束的时候queue的
size是2，但是堆已空，而且还不满足条件从queue中拿出元素来

的

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

: lz绝逼大牛，offer毫无疑问。看了你最后一题的解法，想了一个小时，写了代码，是
: 对的，但还是没想太明白。楼主能给个简略的证明吗？为什么这种贪心策略是对的
: ? 多谢！

t*r2016-01-16 08:01

14 楼

充要条件的话。。还真不会证呢。。

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

: 这个数学关系怎么证明是充分必要条件？
:
: N/

t*r2016-01-16 08:01

15 楼

谢谢指点！我也觉得交流很重要。我面试的时候还是尽量的保持微笑，耐心的，而且写
之前也是先解释一下做法，然后举一个例子，才开始写。不过不确定中间会不会有一点
点儿defensive的时候。还有遇到情况是，我解释完了，面官说我也不确定你的做法是
不是对的，通常情况是你写出来你就知道对不对了，然后我就开始写。写完再用一两个
例子解释一下这样。

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

: 不清楚狗狗想考什么，是不是没做够两题HC就一定拒你，但我觉得交流能力不也是一个
: 非常重要的考察方面吗？我以前有位同事说他面试别人，最讨厌就是什么也不说，上来
: 就写，写错就当然拒了，但写对也不一定给过，因为一个没有交流的面试他是不会给过
: 的，怎么也要解释你写的代码是在做什么，为什么这样做。

s*x2016-01-16 08:01

16 楼

great, thx!

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

: 谢谢鼓励！真不是什么大牛，只是刷题还算认真，又运气好碰到面经题而已
: 我准备的时候看到的面经题是，给一个string，重排，使每个字母之间间隔至少一个其
: 他字母，例如"aabbcc"，可以返回"abacbc"。我面到的题是一个string改成了一堆
: string，间隔1个改成了间隔n个
: 对于原面经题，网上有不少讨论，在一亩三分地里，我觉得对的做法大概就是先统计次
: 数，如果一个字符出现超过1半，则无法重排
: 然后，也是用一个maxheap，但是现在不用queue，改成用一个temp变量，temp变量每隔
: 一轮才再放回heap中，其实也差不多就是size为1的queue
: 回到我面的那个题，如果要说证明的话，我也不会严格的证明。我的理解是这样：用
: 堆是可选的，其实你每一趟都是随便选一个当前还可用的string就可以，用堆是保证了

d*a2016-01-16 08:01

17 楼

楼主答得挺好的，下面有一点疑问。
当queue的size >= n以后，也每一趟都从queue中取出一个Object，如果count > 0
，则放回heap里，否则放回queue中，直至堆空
你说否则放回queue中，如果count = 0, 应该ignore吧？不应该放回queue中啊。

t*r2016-01-16 08:01

18 楼

我觉得应该放回queue中，举个例子
aaaabbbccc, n = 3
合法的解例如abcabcabca
中间会有一个过程解，此时得到的解是abcabc，并且heap中已空，但是queue中还有a（
count为2） b c，只要把queue中的拿出来，放到heap中，就可以继续往下循环。那么
如果不把queue中count为0的放回去的话，最后会出现的情况是queue中还剩下一个a，
heap已空，而queue的size又不够3，无法将这个a取出

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

: 楼主答得挺好的，下面有一点疑问。
: 当queue的size >= n以后，也每一趟都从queue中取出一个Object，如果count > 0
: ，则放回heap里，否则放回queue中，直至堆空
: 你说否则放回queue中，如果count = 0, 应该ignore吧？不应该放回queue中啊。

c*m2016-01-16 08:01

19 楼

楼主好牛逼，到这程序offer应该有了吧！祝福
之前也看过相似的面经题，当时没想出来解法。看了你的解法，才知道核心思想应该是
greedy吧？
greedy选择下一次排的word的条件是：
1.word余下出现次数最多
2.word满足的位置满足要求，即前面n位置没有相同的word。
因为有heap，你这个解法的复杂度是O(nlogn)。
我想到的和楼上有一位提到的相似，应该是O(n)的：
1. filter: 如果某个word出现大于ceil(N/n)次，那么就不能排，返回异常；否则就可
以排
2. 将N分成ceil(N/n)个sections,从出现次数最大的word开始，比如('a', 3次)，每个
section中放一个word，比如'a'放在１，２，３个section中；如果section满了，就放
到后面的section中去
3. 将所有的section连接起来，得到结果。
写了段python的，求拍
def rearrange(self, word_list, n):
#count
word_counter = collections.Counter(word_list)
#filter
#maximum appearing times of each word is ceil(len(word_list) / n)
num_sections = int(math.ceil(1.0 * len(word_list) / n))
print "max appearing times:", num_sections
for w in word_counter:
if word_counter[w] > num_sections:
return []
#can arrange
#divide len(word_list) into ceil(len(word_list) / n) sections
sections = [[] for _ in xrange(num_sections)]
#sort (word, appearing times) in decending order of appearing times
word_times_list = sorted(word_counter.items(), key=lambda a:a[1],
reverse=True)
#greedy: place words from max to min appearing times
first_valid_sec_idx = 0
for word, times in word_times_list:
#for sections starting at first_valid_sec_idx, add one word into
them
next_valid_sec_id = first_valid_sec_idx
for i in xrange(times):
sections[first_valid_sec_idx + i].append(word)
if len(sections[first_valid_sec_idx + i]) == n:
next_valid_sec_id = first_valid_sec_idx + i + 1
first_valid_sec_idx = next_valid_sec_id
#concantanate all sections
res_list = []
for section in sections:
res_list.extend(section)
#return result
return res_list

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

: 我觉得应该放回queue中，举个例子
: aaaabbbccc, n = 3
: 合法的解例如abcabcabca
: 中间会有一个过程解，此时得到的解是abcabc，并且heap中已空，但是queue中还有a（
: count为2） b c，只要把queue中的拿出来，放到heap中，就可以继续往下循环。那么
: 如果不把queue中count为0的放回去的话，最后会出现的情况是queue中还剩下一个a，
: heap已空，而queue的size又不够3，无法将这个a取出

d*a2016-01-16 08:01

20 楼

那要是aaaaabc, n = 3
你这样做没有问题吗？不是生成了abcaaaa了吗？这个size和原来size也一样啊

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

: 我觉得应该放回queue中，举个例子
: aaaabbbccc, n = 3
: 合法的解例如abcabcabca
: 中间会有一个过程解，此时得到的解是abcabc，并且heap中已空，但是queue中还有a（
: count为2） b c，只要把queue中的拿出来，放到heap中，就可以继续往下循环。那么
: 如果不把queue中count为0的放回去的话，最后会出现的情况是queue中还剩下一个a，
: heap已空，而queue的size又不够3，无法将这个a取出

B*42016-01-16 08:01

21 楼

雨滴那题，计算概率的话，要100%覆盖需要无穷多个雨点。
只有覆盖不足100%的长度，期望值才可能是有限的。
取线段上一个一厘米的长度，一个雨点不落在该区域的概率是0.99.
n个雨点都不落在该区域的概率是0.99^n.
所以落下n个雨点后该区域还是干的概率是0.99^n；
想让该区域变湿，需要0.99^n = 0， n是无穷大。
但推广到整个一米长就不知道怎么算了。所以要回答这个是什么概率分布，还真不知道。
模拟的话，可以用数组存放100个区域代表100厘米，用随机数模拟下落的位置。每个雨
点只可能落入一个或者两个区域，然后更改每个区域打湿的范围。当整个区域都打湿了
，计数器加一。当计数器到100的时候，停止模拟。

t*r2016-01-16 08:01

22 楼

不会的，假设当前结果是abc，现在queue里有a(4) b(0) c(0)，而此时heap已空。然后
从queue中取出a(4)，然后放入heap中，然后又从heap取出，count--，然后放回queue
里，现在是结果是abca，b(0) c(0) a(3)，那么新的循环开始时，取出b，发现count =
= 0，不放回heap中，heap空了，循环退出
最后的结果就是abca，与原长度不同，抛出异常

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

: 那要是aaaaabc, n = 3
: 你这样做没有问题吗？不是生成了abcaaaa了吗？这个size和原来size也一样啊

t*r2016-01-16 08:01

23 楼

这题坑很多。
面官问了我分布，我根本不知，随便说了一个正态分布，他说不对，其实是XXX分布，
我没听懂，所以没记住
然后问我我认为期望是多少？我说每个雨滴是0.01，最小需要100个雨滴，最大是无穷
个，期望我不会算，我估计应该1千到几千。他说估的还行，他做过很多次实验，平均
大概是700个雨滴左右。
然后我开始写，我用的方法是类似merge interval，然后一个interval list，然后用
Math.random()产生雨滴的start，start + 0.01作为雨滴的end。
每次新的雨滴进来，找到合适的插入位置，然后merge，当list中只有一个interval，
且这个interval的start <= 0且 end >= 1，就结束并返回结果
然后坑出现了，他说我这样做的话，可能是永远都不会结束，或者要运行很久很久很久
，即使我他已经告诉我平均是700。然后他指出，start不应该直接用Math.random()，
我突然发现对哦，如果start直接用Math.random()的话，真的只有随机到0，才可以湿
润左端点。其实start的范围应该是[-0.01,1]，是要一个把[0,1]的随机数映射到[-0.
01,1]，且几率相等。
改了以后，又说，你这样程序太慢了，让我改。然后我又把之前的从头遍历来找到插入
位置变成二分搜索来插入，然后利用插入的位置，只merge当前interval前后两个
interval
然后让我推导复杂度，我推导出O(N^2)，N在这里是最后返回的雨滴数，然后在他的引
导下，改正为O（N)，我也挺惊奇的，居然是O(N)
这题不是typical的算法题，代码总共也没写几分钟，主要还是讨论和推导，感觉考题
真的很活

道。

【在 B********4 的大作中提到】

: 雨滴那题，计算概率的话，要100%覆盖需要无穷多个雨点。
: 只有覆盖不足100%的长度，期望值才可能是有限的。
: 取线段上一个一厘米的长度，一个雨点不落在该区域的概率是0.99.
: n个雨点都不落在该区域的概率是0.99^n.
: 所以落下n个雨点后该区域还是干的概率是0.99^n；
: 想让该区域变湿，需要0.99^n = 0， n是无穷大。
: 但推广到整个一米长就不知道怎么算了。所以要回答这个是什么概率分布，还真不知道。
: 模拟的话，可以用数组存放100个区域代表100厘米，用随机数模拟下落的位置。每个雨
: 点只可能落入一个或者两个区域，然后更改每个区域打湿的范围。当整个区域都打湿了
: ，计数器加一。当计数器到100的时候，停止模拟。

b*n2016-01-16 08:01

24 楼

感觉楼主面的挺好的，应该有offer吧。
最后一题我觉得应该没有那么复杂？就是greedy就好了。。
可以从最简单的情况讨论，如果K表示整个string的长度，并且K % N == 0，
那么可以把所有K个空位分成每N个一组，把所有字母按照出现的次数从大到小排，然后
按照从最右的组往最左的组的顺序填进去，填的方式是先填每组第1个位置，再填每组
第2个位置。。以此类推
举个例子：aaabbccdd，N=3
填的顺序就是：
[a][][] [a][][] [a][][]
然后
[a][c][] [a][b][] [a][b][]
最后
[a][c][d] [a][b][d] [a][b][c]
可以证明这样填是可以的，因为每个字母最多每个组出现一次，而填的方法可以保证不
会出现有两个相同的字母距离 < N
然后可以扩展到 K % N = M > 0 的情况，方法是取出所有字母中出现次数最多的M个，
先把最后一组M个每种字母取一个填上，就转化成上面的比较简单的情形了，后面需要
优先用这M个字母填，再填其它的。
举个例子，aaabbccd，N=3
先取一个a一个b填好最后一组
[][][] [][][] [a][b]
然后按照a，b，c，d的顺序
[a][][] [a][][] [a][b]
[a][c][d] [a][b][c] [a][b]

z*y2016-01-16 08:01

25 楼

second this
就是先把同样的按照repeat次数连起来，然后每隔N的重新去取，构造一个interleave
过的新string，就可以了吧。有反例可以推翻这个嘛

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

: 感觉楼主面的挺好的，应该有offer吧。
: 最后一题我觉得应该没有那么复杂？就是greedy就好了。。
: 可以从最简单的情况讨论，如果K表示整个string的长度，并且K % N == 0，
: 那么可以把所有K个空位分成每N个一组，把所有字母按照出现的次数从大到小排，然后
: 按照从最右的组往最左的组的顺序填进去，填的方式是先填每组第1个位置，再填每组
: 第2个位置。。以此类推
: 举个例子：aaabbccdd，N=3
: 填的顺序就是：
: [a][][] [a][][] [a][][]
: 然后

l*g2016-01-16 08:01

26 楼

真的不是必须两道or更多的给offer啊。。。
有的人喜欢多道题，每个都简单。
有的人喜欢一道题，但是很深入的讨论的，这样更好的看你的problem solving能力，
看你怎么自己improve和不断更多context下来继续深入的。这种最后结果如何，是看你
的讨论有多深，面试官自己有个bar的。

t*r2016-01-16 08:01

27 楼

谢谢！
我觉得应该对吧，没想出反例，这个是O(N)复杂度，比我的好

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

: 感觉楼主面的挺好的，应该有offer吧。
: 最后一题我觉得应该没有那么复杂？就是greedy就好了。。
: 可以从最简单的情况讨论，如果K表示整个string的长度，并且K % N == 0，
: 那么可以把所有K个空位分成每N个一组，把所有字母按照出现的次数从大到小排，然后
: 按照从最右的组往最左的组的顺序填进去，填的方式是先填每组第1个位置，再填每组
: 第2个位置。。以此类推
: 举个例子：aaabbccdd，N=3
: 填的顺序就是：
: [a][][] [a][][] [a][][]
: 然后

t*r2016-01-16 08:01

28 楼

好吧，谢谢你。。但愿有offer！

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

: 真的不是必须两道or更多的给offer啊。。。
: 有的人喜欢多道题，每个都简单。
: 有的人喜欢一道题，但是很深入的讨论的，这样更好的看你的problem solving能力，
: 看你怎么自己improve和不断更多context下来继续深入的。这种最后结果如何，是看你
: 的讨论有多深，面试官自己有个bar的。

B*42016-01-16 08:01

29 楼

雨点起始位置当然是[-0.01,1]的，因为你雨点落在-0.01，刚好能把线段左端点打湿。
落在1，刚好能把线段右端点打湿。你说的mapping是不是就是让雨点在[-0.01,1]均匀
分布？
randomStart = 1.01 * Math.random() - 0.01;

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

: 这题坑很多。
: 面官问了我分布，我根本不知，随便说了一个正态分布，他说不对，其实是XXX分布，
: 我没听懂，所以没记住
: 然后问我我认为期望是多少？我说每个雨滴是0.01，最小需要100个雨滴，最大是无穷
: 个，期望我不会算，我估计应该1千到几千。他说估的还行，他做过很多次实验，平均
: 大概是700个雨滴左右。
: 然后我开始写，我用的方法是类似merge interval，然后一个interval list，然后用
: Math.random()产生雨滴的start，start + 0.01作为雨滴的end。
: 每次新的雨滴进来，找到合适的插入位置，然后merge，当list中只有一个interval，
: 且这个interval的start <= 0且 end >= 1，就结束并返回结果

t*r2016-01-16 08:01

30 楼

完全正确！

【在 B********4 的大作中提到】

: 雨点起始位置当然是[-0.01,1]的，因为你雨点落在-0.01，刚好能把线段左端点打湿。
: 落在1，刚好能把线段右端点打湿。你说的mapping是不是就是让雨点在[-0.01,1]均匀
: 分布？
: randomStart = 1.01 * Math.random() - 0.01;

N*i2016-01-16 08:01

31 楼

LZ很牛啊！赞一个...
不过单从面试的角度来看，你如果做的太快或者没有思考过程就直接给出最优解，面试
官可能会以为你已经做过但没告诉他们。最后两轮拖得久了一点并不一定是坏事，做出
来了就行

c*m2016-01-16 08:01

32 楼

K%N!=0也是可以的，比如aaabbcc, N=3，结果是abcabca，这个例子楼主已经给过了

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

: 感觉楼主面的挺好的，应该有offer吧。
: 最后一题我觉得应该没有那么复杂？就是greedy就好了。。
: 可以从最简单的情况讨论，如果K表示整个string的长度，并且K % N == 0，
: 那么可以把所有K个空位分成每N个一组，把所有字母按照出现的次数从大到小排，然后
: 按照从最右的组往最左的组的顺序填进去，填的方式是先填每组第1个位置，再填每组
: 第2个位置。。以此类推
: 举个例子：aaabbccdd，N=3
: 填的顺序就是：
: [a][][] [a][][] [a][][]
: 然后

r*x2016-01-16 08:01

33 楼

我也感觉楼主面的不错啊。。题目难度也挺难的。。
有offer了嘛？

b*n2016-01-16 08:01

34 楼

这种情况最后讨论过了呀，你可能没有看全吧。
按照我的理解，前面大家主要在讨论的是证明正确性，我的方法主要也是想解决这个问
题，按照这种方法应该可以严格证明solution是一定存在并且正确的，只要出现次数最
多的字母的出现次数 <= (K-1)/N + 1。

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

: K%N!=0也是可以的，比如aaabbcc, N=3，结果是abcabca，这个例子楼主已经给过了

b*w2016-01-16 08:01

35 楼

实在是想不懂，无论如何也不可能是O(N)Time啊

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

: 这题坑很多。
: 面官问了我分布，我根本不知，随便说了一个正态分布，他说不对，其实是XXX分布，
: 我没听懂，所以没记住
: 然后问我我认为期望是多少？我说每个雨滴是0.01，最小需要100个雨滴，最大是无穷
: 个，期望我不会算，我估计应该1千到几千。他说估的还行，他做过很多次实验，平均
: 大概是700个雨滴左右。
: 然后我开始写，我用的方法是类似merge interval，然后一个interval list，然后用
: Math.random()产生雨滴的start，start + 0.01作为雨滴的end。
: 每次新的雨滴进来，找到合适的插入位置，然后merge，当list中只有一个interval，
: 且这个interval的start <= 0且 end >= 1，就结束并返回结果

t*r2016-01-16 08:01

36 楼

还没呢，hr说连feedback都没收集好呢

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

: 我也感觉楼主面的不错啊。。题目难度也挺难的。。
: 有offer了嘛？

t*r2016-01-16 08:01

37 楼

我现在也忘记如何推的了，但是面试的时候我确实是在面官引导下得出了O(N)的结论，
而且他很肯定这个结论是对的。。。。

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

: 实在是想不懂，无论如何也不可能是O(N)Time啊

w*d2016-01-16 08:01

38 楼

O(N)是对的。因为在这个(0, 1)区间里，独立interval的个数不会超过100个，否则肯
定有两个被merge了，所以每次的binary search都是constant time, 因为只需要在小
于100个元素里查找

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

: 我现在也忘记如何推的了，但是面试的时候我确实是在面官引导下得出了O(N)的结论，
: 而且他很肯定这个结论是对的。。。。

c*m2016-01-16 08:01

39 楼

谢谢，看到了

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

: 这种情况最后讨论过了呀，你可能没有看全吧。
: 按照我的理解，前面大家主要在讨论的是证明正确性，我的方法主要也是想解决这个问
: 题，按照这种方法应该可以严格证明solution是一定存在并且正确的，只要出现次数最
: 多的字母的出现次数 <= (K-1)/N + 1。

c*m2016-01-16 08:01

40 楼

谢谢，看到了

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

: 这种情况最后讨论过了呀，你可能没有看全吧。
: 按照我的理解，前面大家主要在讨论的是证明正确性，我的方法主要也是想解决这个问
: 题，按照这种方法应该可以严格证明solution是一定存在并且正确的，只要出现次数最
: 多的字母的出现次数 <= (K-1)/N + 1。

c*m2016-01-16 08:01

41 楼

谢谢，看到了

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

: 这种情况最后讨论过了呀，你可能没有看全吧。
: 按照我的理解，前面大家主要在讨论的是证明正确性，我的方法主要也是想解决这个问
: 题，按照这种方法应该可以严格证明solution是一定存在并且正确的，只要出现次数最
: 多的字母的出现次数 <= (K-1)/N + 1。

w*d2016-01-16 08:01

42 楼

这似乎不是一个什么很准确的概率分布，简单的话可以近似成negative binomial
distribution，准确一些其实是markov chain的hitting time，相当于一些geometric
distribution的和。
假如我们把[0,1]区间等分成100个小区间，然后假设雨点一定是准确落到某个小区间里
【来近似均匀分布】，那么每个小区间是否被雨点落到就是一个bernoulli分布，概率
是0.01，问题就是在雨点砸到全部100个小区间之前我们需要砸多少次。假如每个小区
间是否被砸到是独立的，那么这就是一个negative binomial，不过这个假设是错的，
而且近似的结果非常的loose，期望在几千左右。
换一个角度，我们考虑被覆盖区域长度的变化。按照近似这个长度只能取值0, 0.01, 0
.02, ..., 1，而且每次都只能从前一个值往后一个值跳跃。那么我们的问题是需要多
少次，这个markov chain可以移动到1。假设我们当前在x，也就是说有x的长度已经被
覆盖了，那么下一次雨点落下来不增加覆盖长度的概率就是x，而增加0.01的概率是1 -
x。所以我们关心的是需要多少次雨点才能增加0.01，这是一个geometric
distribution，且成功的概率是1 - x。而geomtric distribution成功所需要次数的期
望就是1/(1 - x)。这也就是说每次从一个值x跳到x + 0.01所需要的期望步数是1/(1 -
x)。最终我们移动到1所需的次数的期望就是把这些geometric distribution的期望
加起来，
sum_{x = 0}^0.99 1/(1 - x)
这个计算出来的理论值大概是 518.74，和700还是有点差距，因为有近似。比如在即将
铺满的时候，我们的近似和实际差别较大。拿最后一步来说，一个雨滴落下来把0.99变
成1的概率是很小的，一般需要两个雨滴分别在中心点的两侧，所以，我们可以把最后
一步需要的100点换成200点，这样的结果就是618.74，和实验结果比较接近。

t*r2016-01-16 08:01

43 楼

受教了！虽然大部分都还是似懂非懂的，但是看得出来层主已经尽力在用朴实的语言。
。。。

geometric
0

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

: 这似乎不是一个什么很准确的概率分布，简单的话可以近似成negative binomial
: distribution，准确一些其实是markov chain的hitting time，相当于一些geometric
: distribution的和。
: 假如我们把[0,1]区间等分成100个小区间，然后假设雨点一定是准确落到某个小区间里
: 【来近似均匀分布】，那么每个小区间是否被雨点落到就是一个bernoulli分布，概率
: 是0.01，问题就是在雨点砸到全部100个小区间之前我们需要砸多少次。假如每个小区
: 间是否被砸到是独立的，那么这就是一个negative binomial，不过这个假设是错的，
: 而且近似的结果非常的loose，期望在几千左右。
: 换一个角度，我们考虑被覆盖区域长度的变化。按照近似这个长度只能取值0, 0.01, 0
: .02, ..., 1，而且每次都只能从前一个值往后一个值跳跃。那么我们的问题是需要多

w*d2016-01-16 08:01

44 楼

客气啦。只是觉得面试的时候不可能要求这种细致的解答。这反而更像是fund里招
Quant问的题。我觉得LZ题都答得挺好嗒，那个O(N)本来也不是一下子能反应过来的。
答出来很不错呐。应该问题不大～Good luck

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

: 受教了！虽然大部分都还是似懂非懂的，但是看得出来层主已经尽力在用朴实的语言。
: 。。。
:
: geometric
: 0

b*q2016-01-16 08:01

45 楼

有点疑问，雨滴那题，如果是double precision那么wetarea里不止100个区间啊
我写了个模拟，几万个也没法完全覆盖。。。

t*r2016-01-16 08:01

46 楼

我没有自己模拟过，所以也不是很清楚呢。。你检查一下，你的雨点start的区间是 [-
0.01,1]吗？

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

: 有点疑问，雨滴那题，如果是double precision那么wetarea里不止100个区间啊
: 我写了个模拟，几万个也没法完全覆盖。。。

t*r2016-01-16 08:01

47 楼

我也没有模拟过，不太清楚呢。。你检查一下，你的start是[-0.01,1]的区间吗？如
果是的话，我就真不清楚了。。。

[-

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

: 我没有自己模拟过，所以也不是很清楚呢。。你检查一下，你的雨点start的区间是 [-
: 0.01,1]吗？

b*q2016-01-16 08:01

48 楼

区间没错，中间merge的时候有个bug
现在ok了，run了一次结果是829，接近E(X)

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

: 我也没有模拟过，不太清楚呢。。你检查一下，你的start是[-0.01,1]的区间吗？如
: 果是的话，我就真不清楚了。。。
:
: [-

b*q2016-01-16 08:01

49 楼

区间没错，中间merge的时候有个bug
现在ok了，run了一次结果是829，接近E(X)

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

: 我也没有模拟过，不太清楚呢。。你检查一下，你的start是[-0.01,1]的区间吗？如
: 果是的话，我就真不清楚了。。。
:
: [-

d*92016-01-16 08:01

50 楼

没错哈，其实这个题就是经典的coupon collection问题的变形啊。

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

: 客气啦。只是觉得面试的时候不可能要求这种细致的解答。这反而更像是fund里招
: Quant问的题。我觉得LZ题都答得挺好嗒，那个O(N)本来也不是一下子能反应过来的。
: 答出来很不错呐。应该问题不大～Good luck

j*i2016-01-16 08:01

51 楼

雨滴题就是coupon collector‘s problem
答案是100*H(100)，H(n)是第n个调和级数(1 + 1/2 + 1/3 + ... + 1/n)
狗家怎么考概率题去了

sidewalk

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

: 楼主fresh ms
: 今天刚面的g
: 四轮，第一二轮每轮两题，都是直接给出最优解然后代码写完并且跑了两三个test
: case
: 第三轮只做了一题，题本身不复杂，一个一米长的sidewalk，假设是0-1,设雨滴的宽度
: 固定为0.01米，每次下雨的位置随机，精度是double，问多少滴雨才能使整个sidewalk
: 变湿。模拟整个过程。只是面试官一直聊一直聊，一会又问我这个雨滴数的期望是多数
: ，一会又和我聊什么概率分布什么的，我一直想赶快写赶快写让他再出一题，。。最后
: 也只写了一题
: 第四轮，也是一题，也是一个面经题吧，给一个List l和一个number n，让

j*m2016-01-16 08:01

52 楼

不太熟悉python，但是你sort了words based on count，为什么复杂度还是O(N)呢？

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

: 楼主好牛逼，到这程序offer应该有了吧！祝福
: 之前也看过相似的面经题，当时没想出来解法。看了你的解法，才知道核心思想应该是
: greedy吧？
: greedy选择下一次排的word的条件是：
: 1.word余下出现次数最多
: 2.word满足的位置满足要求，即前面n位置没有相同的word。
: 因为有heap，你这个解法的复杂度是O(nlogn)。
: 我想到的和楼上有一位提到的相似，应该是O(n)的：
: 1. filter: 如果某个word出现大于ceil(N/n)次，那么就不能排，返回异常；否则就可
: 以排