t*********r 发帖数: 79 | 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***t 发帖数: 1474 | 2 感觉后两个都是故意跟你墨迹浪费时间,就算做出来了但是hc看到只做了一道也不是啥
好事。所以如果recruiter跟你说挂了你就举报然后要求加面 |
m*****n 发帖数: 204 | 3 后两个人明显是拿一道题细问的。
你要是回答的还好,你的不耐烦又
没被看出来的话就没事儿。不然就
可能在communication和team work
上被低评。
不是每个人都问两题的。你有点喧宾夺主啊。
sidewalk
【在 t*********r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 楼主fresh ms : 今天刚面的g : 四轮,第一二轮每轮两题,都是直接给出最优解然后代码写完并且跑了两三个test : case : 第三轮只做了一题,题本身不复杂,一个一米长的sidewalk,假设是0-1,设雨滴的宽度 : 固定为0.01米,每次下雨的位置随机,精度是double,问多少滴雨才能使整个sidewalk : 变湿。模拟整个过程。只是面试官一直聊一直聊,一会又问我这个雨滴数的期望是多数 : ,一会又和我聊什么概率分布什么的,我一直想赶快写赶快写让他再出一题,。。最后 : 也只写了一题 : 第四轮,也是一题,也是一个面经题吧,给一个List l和一个number n,让
|
t*********r 发帖数: 79 | 4 是啊,我就是感觉有点儿磨叽时间,我这次准备的还算充分,面经都看的很多,题本身
也刷的认真些吧,基本都是他把题说完我就知道怎么写了,基本上三五分钟就能写完。
但是总是不让我开始,不停的聊,所以我有点儿担心。。。我担心的地方是,我不知道
他在考察什么,不知道他到底想要设呢
【在 w***t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 感觉后两个都是故意跟你墨迹浪费时间,就算做出来了但是hc看到只做了一道也不是啥 : 好事。所以如果recruiter跟你说挂了你就举报然后要求加面
|
t*********r 发帖数: 79 | 5 我肯定没有不耐烦,我只是想尽快做完然后开始下一题
是不一定需要做两题是吗?
面试官考察的都有哪几方面呢? 所以现在主要是三个方面打分吗,代码能力,
communication,team work ?
【在 m*****n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 后两个人明显是拿一道题细问的。 : 你要是回答的还好,你的不耐烦又 : 没被看出来的话就没事儿。不然就 : 可能在communication和team work : 上被低评。 : 不是每个人都问两题的。你有点喧宾夺主啊。 : : sidewalk
|
l******8 发帖数: 1691 | 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 楼主fresh ms : 今天刚面的g : 四轮,第一二轮每轮两题,都是直接给出最优解然后代码写完并且跑了两三个test : case : 第三轮只做了一题,题本身不复杂,一个一米长的sidewalk,假设是0-1,设雨滴的宽度 : 固定为0.01米,每次下雨的位置随机,精度是double,问多少滴雨才能使整个sidewalk : 变湿。模拟整个过程。只是面试官一直聊一直聊,一会又问我这个雨滴数的期望是多数 : ,一会又和我聊什么概率分布什么的,我一直想赶快写赶快写让他再出一题,。。最后 : 也只写了一题 : 第四轮,也是一题,也是一个面经题吧,给一个List l和一个number n,让
|
t*********r 发帖数: 79 | 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 能不能讨论下最后一题?我经验少没看过。是不是把所有都过一遍,然后首先看是不是 : 至少有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**k 发帖数: 3368 | |
t*********r 发帖数: 79 | 9 可是。。。。是没见过一模一样的,但是见过类似的,也很快就能做出的呀。。。
【在 h**k 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你题目答得太快,面试官会怀疑你见过这题
|
g*****a 发帖数: 8 | 10 lz绝逼大牛,offer毫无疑问。 看了你最后一题的解法,想了一个小时,写了代码,是
对的,但还是没想太明白。 楼主能给个简略的证明吗 ? 为什么这种贪心策略是对的
? 多谢 ! |
|
|
s**x 发帖数: 7506 | 11 这个数学关系怎么证明是充分必要条件?
N/
【在 l******8 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 能不能讨论下最后一题?我经验少没看过。是不是把所有都过一遍,然后首先看是不是 : 至少有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**e 发帖数: 6098 | 12 不清楚狗狗想考什么,是不是没做够两题HC就一定拒你,但我觉得交流能力不也是一个
非常重要的考察方面吗?我以前有位同事说他面试别人,最讨厌就是什么也不说,上来
就写,写错就当然拒了,但写对也不一定给过,因为一个没有交流的面试他是不会给过
的,怎么也要解释你写的代码是在做什么,为什么这样做。
【在 t*********r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 可是。。。。是没见过一模一样的,但是见过类似的,也很快就能做出的呀。。。
|
t*********r 发帖数: 79 | 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : lz绝逼大牛,offer毫无疑问。 看了你最后一题的解法,想了一个小时,写了代码,是 : 对的,但还是没想太明白。 楼主能给个简略的证明吗 ? 为什么这种贪心策略是对的 : ? 多谢 !
|
t*********r 发帖数: 79 | 14 充要条件的话。。还真不会证呢。。
【在 s**x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个数学关系怎么证明是充分必要条件? : : N/
|
t*********r 发帖数: 79 | 15 谢谢指点!我也觉得交流很重要。我面试的时候还是尽量的保持微笑,耐心的,而且写
之前也是先解释一下做法,然后举一个例子,才开始写。不过不确定中间会不会有一点
点儿defensive的时候。还有遇到情况是,我解释完了,面官说我也不确定你的做法是
不是对的,通常情况是你写出来你就知道对不对了,然后我就开始写。写完再用一两个
例子解释一下这样。
【在 d**e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 不清楚狗狗想考什么,是不是没做够两题HC就一定拒你,但我觉得交流能力不也是一个 : 非常重要的考察方面吗?我以前有位同事说他面试别人,最讨厌就是什么也不说,上来 : 就写,写错就当然拒了,但写对也不一定给过,因为一个没有交流的面试他是不会给过 : 的,怎么也要解释你写的代码是在做什么,为什么这样做。
|
s**x 发帖数: 7506 | 16 great, thx!
【在 t*********r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 谢谢鼓励! 真不是什么大牛,只是刷题还算认真,又运气好碰到面经题而已 : 我准备的时候看到的面经题是,给一个string,重排,使每个字母之间间隔至少一个其 : 他字母,例如"aabbcc",可以返回"abacbc"。我面到的题是一个string改成了一堆 : string,间隔1个改成了间隔n个 : 对于原面经题,网上有不少讨论,在一亩三分地里,我觉得对的做法大概就是先统计次 : 数,如果一个字符出现超过1半,则无法重排 : 然后,也是用一个maxheap,但是现在不用queue,改成用一个temp变量,temp变量每隔 : 一轮才再放回heap中,其实也差不多就是size为1的queue : 回到我面的那个题,如果要说证明的话,我也不会严格的证明。我的理解是这样: 用 : 堆是可选的,其实你每一趟都是随便选一个当前还可用的string就可以,用堆是保证了
|
d******a 发帖数: 238 | 17 楼主答得挺好的,下面有一点疑问。
当queue的size >= n以后,也每一趟都从queue中取出一个Object,如果count > 0
,则放回heap里,否则放回queue中,直至堆空
你说否则放回queue中, 如果count = 0, 应该ignore吧?不应该放回queue中啊。 |
t*********r 发帖数: 79 | 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 楼主答得挺好的,下面有一点疑问。 : 当queue的size >= n以后,也每一趟都从queue中取出一个Object,如果count > 0 : ,则放回heap里,否则放回queue中,直至堆空 : 你说否则放回queue中, 如果count = 0, 应该ignore吧?不应该放回queue中啊。
|
c*****m 发帖数: 271 | 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'放在1,2,3个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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我觉得应该放回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 发帖数: 238 | 20 那要是aaaaabc, n = 3
你这样做没有问题吗? 不是生成了abcaaaa了吗?这个size和原来size也一样啊
【在 t*********r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我觉得应该放回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********4 发帖数: 7156 | 21 雨滴那题,计算概率的话,要100%覆盖需要无穷多个雨点。
只有覆盖不足100%的长度,期望值才可能是有限的。
取线段上一个一厘米的长度,一个雨点不落在该区域的概率是0.99.
n个雨点都不落在该区域的概率是0.99^n.
所以落下n个雨点后该区域还是干的概率是0.99^n;
想让该区域变湿,需要0.99^n = 0, n是无穷大。
但推广到整个一米长就不知道怎么算了。所以要回答这个是什么概率分布,还真不知道。
模拟的话,可以用数组存放100个区域代表100厘米,用随机数模拟下落的位置。每个雨
点只可能落入一个或者两个区域,然后更改每个区域打湿的范围。当整个区域都打湿了
,计数器加一。当计数器到100的时候,停止模拟。 |
t*********r 发帖数: 79 | 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 那要是aaaaabc, n = 3 : 你这样做没有问题吗? 不是生成了abcaaaa了吗?这个size和原来size也一样啊
|
t*********r 发帖数: 79 | 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 雨滴那题,计算概率的话,要100%覆盖需要无穷多个雨点。 : 只有覆盖不足100%的长度,期望值才可能是有限的。 : 取线段上一个一厘米的长度,一个雨点不落在该区域的概率是0.99. : n个雨点都不落在该区域的概率是0.99^n. : 所以落下n个雨点后该区域还是干的概率是0.99^n; : 想让该区域变湿,需要0.99^n = 0, n是无穷大。 : 但推广到整个一米长就不知道怎么算了。所以要回答这个是什么概率分布,还真不知道。 : 模拟的话,可以用数组存放100个区域代表100厘米,用随机数模拟下落的位置。每个雨 : 点只可能落入一个或者两个区域,然后更改每个区域打湿的范围。当整个区域都打湿了 : ,计数器加一。当计数器到100的时候,停止模拟。
|
b*****n 发帖数: 618 | 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****y 发帖数: 345 | 25 second this
就是先把同样的按照repeat次数连起来,然后每隔N的重新去取,构造一个interleave
过的新string,就可以了吧。有反例可以推翻这个嘛
【在 b*****n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 感觉楼主面的挺好的,应该有offer吧。 : 最后一题我觉得应该没有那么复杂?就是greedy就好了。。 : 可以从最简单的情况讨论,如果K表示整个string的长度,并且K % N == 0, : 那么可以把所有K个空位分成每N个一组,把所有字母按照出现的次数从大到小排,然后 : 按照从最右的组往最左的组的顺序填进去,填的方式是先填每组第1个位置,再填每组 : 第2个位置。。以此类推 : 举个例子:aaabbccdd,N=3 : 填的顺序就是: : [a][][] [a][][] [a][][] : 然后
|
l********g 发帖数: 372 | 26 真的不是必须两道or更多的给offer啊。。。
有的人喜欢多道题,每个都简单。
有的人喜欢一道题,但是很深入的讨论的,这样更好的看你的problem solving能力,
看你怎么自己improve和不断更多context下来继续深入的。这种最后结果如何,是看你
的讨论有多深,面试官自己有个bar的。 |
t*********r 发帖数: 79 | 27 谢谢!
我觉得应该对吧,没想出反例,这个是O(N)复杂度,比我的好
【在 b*****n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 感觉楼主面的挺好的,应该有offer吧。 : 最后一题我觉得应该没有那么复杂?就是greedy就好了。。 : 可以从最简单的情况讨论,如果K表示整个string的长度,并且K % N == 0, : 那么可以把所有K个空位分成每N个一组,把所有字母按照出现的次数从大到小排,然后 : 按照从最右的组往最左的组的顺序填进去,填的方式是先填每组第1个位置,再填每组 : 第2个位置。。以此类推 : 举个例子:aaabbccdd,N=3 : 填的顺序就是: : [a][][] [a][][] [a][][] : 然后
|
t*********r 发帖数: 79 | 28 好吧,谢谢你。。但愿有offer!
【在 l********g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 真的不是必须两道or更多的给offer啊。。。 : 有的人喜欢多道题,每个都简单。 : 有的人喜欢一道题,但是很深入的讨论的,这样更好的看你的problem solving能力, : 看你怎么自己improve和不断更多context下来继续深入的。这种最后结果如何,是看你 : 的讨论有多深,面试官自己有个bar的。
|
B********4 发帖数: 7156 | 29 雨点起始位置当然是[-0.01,1]的,因为你雨点落在-0.01,刚好能把线段左端点打湿。
落在1,刚好能把线段右端点打湿。你说的mapping是不是就是让雨点在[-0.01,1]均匀
分布?
randomStart = 1.01 * Math.random() - 0.01;
【在 t*********r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这题坑很多。 : 面官问了我分布,我根本不知,随便说了一个正态分布,他说不对,其实是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*********r 发帖数: 79 | 30 完全正确!
【在 B********4 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 雨点起始位置当然是[-0.01,1]的,因为你雨点落在-0.01,刚好能把线段左端点打湿。 : 落在1,刚好能把线段右端点打湿。你说的mapping是不是就是让雨点在[-0.01,1]均匀 : 分布? : randomStart = 1.01 * Math.random() - 0.01;
|
|
|
N**********i 发帖数: 34 | 31 LZ很牛啊!赞一个...
不过单从面试的角度来看,你如果做的太快或者没有思考过程就直接给出最优解,面试
官可能会以为你已经做过但没告诉他们。最后两轮拖得久了一点并不一定是坏事,做出
来了就行 |
c*****m 发帖数: 271 | 32 K%N!=0也是可以的,比如aaabbcc, N=3,结果是abcabca,这个例子楼主已经给过了
【在 b*****n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 感觉楼主面的挺好的,应该有offer吧。 : 最后一题我觉得应该没有那么复杂?就是greedy就好了。。 : 可以从最简单的情况讨论,如果K表示整个string的长度,并且K % N == 0, : 那么可以把所有K个空位分成每N个一组,把所有字母按照出现的次数从大到小排,然后 : 按照从最右的组往最左的组的顺序填进去,填的方式是先填每组第1个位置,再填每组 : 第2个位置。。以此类推 : 举个例子:aaabbccdd,N=3 : 填的顺序就是: : [a][][] [a][][] [a][][] : 然后
|
r***x 发帖数: 65 | 33 我也感觉楼主面的不错啊。。题目难度也挺难的。。
有offer了嘛? |
b*****n 发帖数: 618 | 34 这种情况最后讨论过了呀,你可能没有看全吧。
按照我的理解,前面大家主要在讨论的是证明正确性,我的方法主要也是想解决这个问
题,按照这种方法应该可以严格证明solution是一定存在并且正确的,只要出现次数最
多的字母的出现次数 <= (K-1)/N + 1。
【在 c*****m 的大作中提到】![](/moin_static193/solenoid/img/up.png) : K%N!=0也是可以的,比如aaabbcc, N=3,结果是abcabca,这个例子楼主已经给过了
|
b*****w 发帖数: 56 | 35 实在是想不懂,无论如何也不可能是O(N)Time啊
【在 t*********r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这题坑很多。 : 面官问了我分布,我根本不知,随便说了一个正态分布,他说不对,其实是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*********r 发帖数: 79 | 36 还没呢,hr说连feedback都没收集好呢
【在 r***x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我也感觉楼主面的不错啊。。题目难度也挺难的。。 : 有offer了嘛?
|
t*********r 发帖数: 79 | 37 我现在也忘记如何推的了,但是面试的时候我确实是在面官引导下得出了O(N)的结论,
而且他很肯定这个结论是对的。。。。
【在 b*****w 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 实在是想不懂,无论如何也不可能是O(N)Time啊
|
w*******d 发帖数: 59 | 38 O(N)是对的。因为在这个(0, 1)区间里,独立interval的个数不会超过100个,否则肯
定有两个被merge了,所以每次的binary search都是constant time, 因为只需要在小
于100个元素里查找
【在 t*********r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我现在也忘记如何推的了,但是面试的时候我确实是在面官引导下得出了O(N)的结论, : 而且他很肯定这个结论是对的。。。。
|
c*****m 发帖数: 271 | 39 谢谢,看到了
【在 b*****n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这种情况最后讨论过了呀,你可能没有看全吧。 : 按照我的理解,前面大家主要在讨论的是证明正确性,我的方法主要也是想解决这个问 : 题,按照这种方法应该可以严格证明solution是一定存在并且正确的,只要出现次数最 : 多的字母的出现次数 <= (K-1)/N + 1。
|
c*****m 发帖数: 271 | 40 谢谢,看到了
【在 b*****n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这种情况最后讨论过了呀,你可能没有看全吧。 : 按照我的理解,前面大家主要在讨论的是证明正确性,我的方法主要也是想解决这个问 : 题,按照这种方法应该可以严格证明solution是一定存在并且正确的,只要出现次数最 : 多的字母的出现次数 <= (K-1)/N + 1。
|
|
|
c*****m 发帖数: 271 | 41 谢谢,看到了
【在 b*****n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这种情况最后讨论过了呀,你可能没有看全吧。 : 按照我的理解,前面大家主要在讨论的是证明正确性,我的方法主要也是想解决这个问 : 题,按照这种方法应该可以严格证明solution是一定存在并且正确的,只要出现次数最 : 多的字母的出现次数 <= (K-1)/N + 1。
|
w*******d 发帖数: 59 | 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*********r 发帖数: 79 | 43 受教了!虽然大部分都还是似懂非懂的,但是看得出来层主已经尽力在用朴实的语言。
。。。
geometric
0
【在 w*******d 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这似乎不是一个什么很准确的概率分布,简单的话可以近似成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*******d 发帖数: 59 | 44 客气啦。只是觉得面试的时候不可能要求这种细致的解答。这反而更像是fund里招
Quant问的题。我觉得LZ题都答得挺好嗒,那个O(N)本来也不是一下子能反应过来的。
答出来很不错呐。应该问题不大~Good luck
【在 t*********r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 受教了!虽然大部分都还是似懂非懂的,但是看得出来层主已经尽力在用朴实的语言。 : 。。。 : : geometric : 0
|
b**q 发帖数: 247 | 45 有点疑问,雨滴那题,如果是double precision那么wetarea里不止100个区间啊
我写了个模拟,几万个也没法完全覆盖。。。 |
t*********r 发帖数: 79 | 46 我没有自己模拟过,所以也不是很清楚呢。。你检查一下,你的雨点start的区间是 [-
0.01,1]吗 ?
【在 b**q 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 有点疑问,雨滴那题,如果是double precision那么wetarea里不止100个区间啊 : 我写了个模拟,几万个也没法完全覆盖。。。
|
t*********r 发帖数: 79 | 47 我也没有模拟过,不太清楚呢。。你检查一下,你的start是[-0.01,1]的区间吗? 如
果是的话,我就真不清楚了。。。
[-
【在 t*********r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我没有自己模拟过,所以也不是很清楚呢。。你检查一下,你的雨点start的区间是 [- : 0.01,1]吗 ?
|
b**q 发帖数: 247 | 48 区间没错,中间merge的时候有个bug
现在ok了,run了一次结果是829,接近E(X)
【在 t*********r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我也没有模拟过,不太清楚呢。。你检查一下,你的start是[-0.01,1]的区间吗? 如 : 果是的话,我就真不清楚了。。。 : : [-
|
b**q 发帖数: 247 | 49 区间没错,中间merge的时候有个bug
现在ok了,run了一次结果是829,接近E(X)
【在 t*********r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我也没有模拟过,不太清楚呢。。你检查一下,你的start是[-0.01,1]的区间吗? 如 : 果是的话,我就真不清楚了。。。 : : [-
|
d********9 发帖数: 38 | 50 没错哈,其实这个题就是经典的coupon collection问题的变形啊。
【在 w*******d 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 客气啦。只是觉得面试的时候不可能要求这种细致的解答。这反而更像是fund里招 : Quant问的题。我觉得LZ题都答得挺好嗒,那个O(N)本来也不是一下子能反应过来的。 : 答出来很不错呐。应该问题不大~Good luck
|
|
|
j******i 发帖数: 244 | 51 雨滴题就是coupon collector‘s problem
答案是100*H(100),H(n)是第n个调和级数(1 + 1/2 + 1/3 + ... + 1/n)
狗家怎么考概率题去了
sidewalk
【在 t*********r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 楼主fresh ms : 今天刚面的g : 四轮,第一二轮每轮两题,都是直接给出最优解然后代码写完并且跑了两三个test : case : 第三轮只做了一题,题本身不复杂,一个一米长的sidewalk,假设是0-1,设雨滴的宽度 : 固定为0.01米,每次下雨的位置随机,精度是double,问多少滴雨才能使整个sidewalk : 变湿。模拟整个过程。只是面试官一直聊一直聊,一会又问我这个雨滴数的期望是多数 : ,一会又和我聊什么概率分布什么的,我一直想赶快写赶快写让他再出一题,。。最后 : 也只写了一题 : 第四轮,也是一题,也是一个面经题吧,给一个List l和一个number n,让
|
j**********m 发帖数: 51 | 52 不太熟悉python,但是你sort了words based on count,为什么复杂度还是O(N)呢?
【在 c*****m 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 楼主好牛逼,到这程序offer应该有了吧!祝福 : 之前也看过相似的面经题,当时没想出来解法。看了你的解法,才知道核心思想应该是 : greedy吧? : greedy选择下一次排的word的条件是: : 1.word余下出现次数最多 : 2.word满足的位置满足要求,即前面n位置没有相同的word。 : 因为有heap,你这个解法的复杂度是O(nlogn)。 : 我想到的和楼上有一位提到的相似,应该是O(n)的: : 1. filter: 如果某个word出现大于ceil(N/n)次,那么就不能排,返回异常;否则就可 : 以排
|