当前在线人数13673
首页 - 分类讨论区 - 海外生活 - 待字闺中版 - 同主题阅读文章

此篇文章共收到打赏
0

  • 10
  • 20
  • 50
  • 100
您目前伪币余额:0
未名交友
[更多]
[更多]
问个Facebook的面经题
[版面:待字闺中][首篇作者:goldsky] , 2015年09月17日17:06:35 ,3925次阅读,19次回复
来APP回复,赚取更多伪币 关注本站公众号:
[分页:1 ]
goldsky
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 1 ]

发信人: goldsky (MC), 信区: JobHunting
标  题: 问个Facebook的面经题
发信站: BBS 未名空间站 (Thu Sep 17 17:06:35 2015, 美东)

3. 一种字母游戏这样的
给定四个位置 _,_,_,_
然后每个位置可以选5个candidates,然后问这些candidates最多可以组成多少个有效
的词,字典是给定的。

比如,
如果字典是 [cake, bike, fake]
我们可以这样选candidates
第一个位置可以选 b,c,f,e,d
第二个位置 i,a,o,p,e
第三个位置 k,m,w,q,a
第四个位置 e,g,h,k,l
那这些可以组成3个有效的词 cake, bike, fake.

但是如果,这样选每个位置的candidates
第一个位置可以选 z,c,v,b,y
第二个位置 i,a,o,p,e
第三个位置 k,m,w,q,a
第四个位置 e,g,h,k,l

只能组成一个有效的词就是bike.
这样就是第一种选candidates的方法比较好。

然后问你怎么选每个位置的candidates,最终可以让能组成的词最多。

没有什么特别好的思路,问是不是brutal search,还有更好的方法吗?答:你如果要
brutal search的话,你估算一下时间。
我就开始算时间,发现很长,然后面试官说,那你想办法优化。。。但是因为算brual
search的时间算了太长时间了,就没什么时间优化了。。。
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 24.]

 
workatca
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 2 ]

发信人: workatca (contepartiro), 信区: JobHunting
标  题: Re: 问个Facebook的面经题
发信站: BBS 未名空间站 (Thu Sep 17 17:31:13 2015, 美东)

是不是要先遍历字典里词的第一个字母,尽量多的往前放,然后依此类推。比如例子里
c,b,f应该要尽量放在第一个位置。
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 173.]

 
goldsky
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 3 ]

发信人: goldsky (MC), 信区: JobHunting
标  题: Re: 问个Facebook的面经题
发信站: BBS 未名空间站 (Thu Sep 17 17:37:25 2015, 美东)

我开始也是想到用这个greedy algorithm. 但是并不是以第一个字母为开头的单词多就
代表要选它,因为还得考虑后面位置的字母。


【 在 workatca (contepartiro) 的大作中提到: 】
: 是不是要先遍历字典里词的第一个字母,尽量多的往前放,然后依此类推。比如例子里
: c,b,f应该要尽量放在第一个位置。



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 24.]

 
autumnhu
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 4 ]

发信人: autumnhu (秋虎), 信区: JobHunting
标  题: Re: 问个Facebook的面经题
发信站: BBS 未名空间站 (Thu Sep 17 17:40:42 2015, 美东)

第二个例子为什么cake不行?

--
☆ 发自 iPhone 买买提 1.22.06
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 128.]

 
wzy0791
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 5 ]

发信人: wzy0791 (阿毛牛), 信区: JobHunting
标  题: Re: 问个Facebook的面经题
发信站: BBS 未名空间站 (Thu Sep 17 17:41:17 2015, 美东)

不知道题目的难度,正常思维应该都是这样想的,也可能有陷阱,特别是频率相同的字
母该选哪个?
面试的时候又不会告诉你这题难度是怎样,哎,真是越来越难了


【 在 workatca (contepartiro) 的大作中提到: 】
: 是不是要先遍历字典里词的第一个字母,尽量多的往前放,然后依此类推。比如例子里
: c,b,f应该要尽量放在第一个位置。



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 64.]

 
wzy0791
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 6 ]

发信人: wzy0791 (阿毛牛), 信区: JobHunting
标  题: Re: 问个Facebook的面经题
发信站: BBS 未名空间站 (Thu Sep 17 17:42:11 2015, 美东)

是啊,好奇怪

【 在 autumnhu (秋虎) 的大作中提到: 】
: 第二个例子为什么cake不行?



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 64.]

 
goldsky
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 7 ]

发信人: goldsky (MC), 信区: JobHunting
标  题: Re: 问个Facebook的面经题
发信站: BBS 未名空间站 (Thu Sep 17 17:46:58 2015, 美东)

cake应该是可以的,我觉得应该是原作者疏忽了这个。


【 在 wzy0791 (阿毛牛) 的大作中提到: 】
: 是啊,好奇怪



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 24.]

 
ThinkU
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 8 ]

发信人: ThinkU (每天想你多一丝), 信区: JobHunting
标  题: Re: 问个Facebook的面经题
发信站: BBS 未名空间站 (Thu Sep 17 18:59:09 2015, 美东)

这题里面第一个位置的字母不能出现在之后位置上,trie不能保证把
【 在 component (component) 的大作中提到: 】
: 太简单了。
: 用tries,把字典的词全部添加到tries,
: 再对tries递归一遍,从最底层开始
: 在tries每一层那个指向下一层的指针矩阵里再存上之下所有单词的数量。
: 就好比二叉树在每一节点再存上之下所有节点数量一样,类似的。
: 每一层要选择的字母,就是该数量前5大。
: triesNode{
:  triesNode():var(-1){};
:  int var;
:  array<pair<triesNode*,int>,128> next;
: ...................



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 70.]

 
goldsky
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 9 ]

发信人: goldsky (MC), 信区: JobHunting
标  题: Re: 问个Facebook的面经题
发信站: BBS 未名空间站 (Thu Sep 17 19:20:54 2015, 美东)

开始也想到用Trie来着,但是后来想了想应该也不行或者很麻烦。比如对于其中某一层
,字母a, b, ..., z等可能会出现在这一层的多个Trie节点。因为这要取决于它的父亲
节点。

例子: ..ka.., ..da.., ..ea..,那么a字母在它的那一层其实出现到三个Trie节点,
然后又不能用个HashMap来统计次数,因为这又牵连到上一层的节点。

不知道分析得对不对,继续讨论吧。


【 在 component (component) 的大作中提到: 】
: 太简单了。
: 用tries,把字典的词全部添加到tries,
: 再对tries递归一遍,从最底层开始
: 在tries每一层那个指向下一层的指针矩阵里再存上之下所有单词的数量。
: 就好比二叉树在每一节点再存上之下所有节点数量一样,类似的。
: 每一层要选择的字母,就是该数量前5大。
: triesNode{
:  triesNode():var(-1){};
:  int var;
:  array<pair<triesNode*,int>,128> next;
: ...................



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 24.]

 
fattybelly
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 10 ]

发信人: fattybelly (pp), 信区: JobHunting
标  题: Re: 问个Facebook的面经题
发信站: BBS 未名空间站 (Thu Sep 17 20:14:04 2015, 美东)

感觉应该用图。 比如第一个例子,是个四层的图,在每层选5个,使得从第一层到第四
层的 unique path 数目最多。

这个用greedy 肯定有问题。

大牛说说,这是不是有现成算法啊?



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 50.]

 
backstab
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 11 ]

发信人: backstab (沧海月明), 信区: JobHunting
标  题: Re: 问个Facebook的面经题
发信站: BBS 未名空间站 (Thu Sep 17 21:50:41 2015, 美东)

throw my brick, :)

Think it the other way around, when you put a char in a specific position,
you are eliminate all the words have that char on other position, e.g. if
you put 'a' in position 0, then all the words have 'a' at position 1,2,3
cannot be constructed.

with this thought, we can construct the char/count for each position, e.g.
at position 0, we have [a:3, b:2, c:1, d:4...]
same for other positions.

now we just need to find the char which will eliminate the least number of
words, e.g. count each char for each position how many words it will
eliminate, and start from the one which will eliminate least, and do it
iteratively until all the positions are filled.








【 在 goldsky (MC) 的大作中提到: 】
: 3. 一种字母游戏这样的
: 给定四个位置 _,_,_,_
: 然后每个位置可以选5个candidates,然后问这些candidates最多可以组成多少个有效
: 的词,字典是给定的。
: 比如,
: 如果字典是 [cake, bike, fake]
: 我们可以这样选candidates
: 第一个位置可以选 b,c,f,e,d
: 第二个位置 i,a,o,p,e
: 第三个位置 k,m,w,q,a
: ...................



--
如果有来生,要做一棵树;
站成永恒,没有悲欢的姿势。
一半在土里安详,一半在风里飞扬,
一半洒落阴凉,一半沐浴阳光。
非常沉默,非常骄傲,    
从不依靠,从不寻找

※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 108.]

 
fattybelly
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 12 ]

发信人: fattybelly (pp), 信区: JobHunting
标  题: RE: 问个Facebook的面经题
发信站: BBS 未名空间站 (Thu Sep 17 21:57:19 2015, 美东)

字母可以重用吧?比如a is used at 2nd and 3rd positions.

“比如,如果字典是 [cake, bike, fake]我们可以这样选candidates第一个位置可以
选 b,c,f,e,d第二个位置 i,a,o,p,e第三个位置 k,m,w,q,a第四个位置 e,g,h,k,l那这
些可以组成3个有效的词 cake, bike, fake.”



【 在 backstab (沧海月明) 的大作中提到: 】
throw my brick, :)Think it the other way around, when you put a char in a
specific posit........
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 50.]

 
backstab
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 13 ]

发信人: backstab (沧海月明), 信区: JobHunting
标  题: Re: RE: 问个Facebook的面经题
发信站: BBS 未名空间站 (Thu Sep 17 22:10:01 2015, 美东)

if you can reuse the char, then the trie solution above is the best. sorry
didn't read it carefully.

【 在 fattybelly (pp) 的大作中提到: 】
: 字母可以重用吧?比如a is used at 2nd and 3rd positions.
: “比如,如果字典是 [cake, bike, fake]我们可以这样选candidates第一个位置可以
: 选 b,c,f,e,d第二个位置 i,a,o,p,e第三个位置 k,m,w,q,a第四个位置 e,g,h,k,l那这
: 些可以组成3个有效的词 cake, bike, fake.”
: throw my brick, :)Think it the other way around, when you put a char in a
: specific posit........



--
如果有来生,要做一棵树;
站成永恒,没有悲欢的姿势。
一半在土里安详,一半在风里飞扬,
一半洒落阴凉,一半沐浴阳光。
非常沉默,非常骄傲,    
从不依靠,从不寻找

※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 108.]

 
yzser
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 14 ]

发信人: yzser (yz), 信区: JobHunting
标  题: Re: 问个Facebook的面经题
发信站: BBS 未名空间站 (Fri Sep 18 00:33:48 2015, 美东)

Trie的方法不一定对吧,每一层的选择都会相互影响,感觉有点像max flow那一类题
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 107.]

 
goldsky
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 15 ]

发信人: goldsky (MC), 信区: JobHunting
标  题: Re: 问个Facebook的面经题
发信站: BBS 未名空间站 (Fri Sep 18 01:23:39 2015, 美东)

max flow方法该怎么弄?


【 在 yzser (yz) 的大作中提到: 】
: Trie的方法不一定对吧,每一层的选择都会相互影响,感觉有点像max flow那一类题



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 24.]

 
Erica3740
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 16 ]

发信人: Erica3740 (秋泥针), 信区: JobHunting
标  题: Re: 问个Facebook的面经题
发信站: BBS 未名空间站 (Fri Sep 18 15:44:09 2015, 美东)

mark.
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 173.]

 
firework2
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 17 ]

发信人: firework2 (firework), 信区: JobHunting
标  题: Re: 问个Facebook的面经题
发信站: BBS 未名空间站 (Fri Sep 18 17:25:33 2015, 美东)

先go through 整个字典,4个位置上面,每一个位置26个字母出现的频率排个序。
取每一个位置出现率最高的字母,再让四个位置出现率最高PK,比如例子中第3位置K的
出现率最高。

第3位就选K, 然后在其他3个位置用上面的算法,直到第一轮4个位置都填满。
然后去掉被cover的字,剩下的字里面,以此类推。


【 在 goldsky (MC) 的大作中提到: 】
: 3. 一种字母游戏这样的
: 给定四个位置 _,_,_,_
: 然后每个位置可以选5个candidates,然后问这些candidates最多可以组成多少个有效
: 的词,字典是给定的。
: 比如,
: 如果字典是 [cake, bike, fake]
: 我们可以这样选candidates
: 第一个位置可以选 b,c,f,e,d
: 第二个位置 i,a,o,p,e
: 第三个位置 k,m,w,q,a
: ...................



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 98.]

[分页:1 ]
[快速返回] [ 进入待字闺中讨论区] [返回顶部]
回复文章
标题:
内 容:

未名交友
将您的链接放在这儿

友情链接


 

Site Map - Contact Us - Terms and Conditions - Privacy Policy

版权所有,未名空间(mitbbs.com),since 1996