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

此篇文章共收到打赏
0

  • 10
  • 20
  • 50
  • 100
您目前伪币余额:0
未名交友
[更多]
[更多]
贡献一道AAA游戏公司的onsite的面试题
[版面:待字闺中][首篇作者:InzaghiFly] , 2015年08月29日23:23:31 ,4802次阅读,9次回复
来APP回复,赚取更多伪币 关注本站公众号:
[分页:1 ]
InzaghiFly
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 1 ]

发信人: InzaghiFly (Inzaghi), 信区: JobHunting
标  题: 贡献一道AAA游戏公司的onsite的面试题
发信站: BBS 未名空间站 (Sat Aug 29 23:23:31 2015, 美东)

给一个int的数组parties,每一个element也就是每一个party代表一组玩家,比如
parties[0]是3,代表这个party有3个玩家。然后给一个一场多人游戏最多可以容纳的
玩家数量的值maxHopperSize,要求从这个数组中选任意多party加和组成一个Hopper,
加和的玩家总数要满足小于等于maxHopperSize。然后同时给一个hopper的数目
hopperCount,问是否可以fill所有的玩家到给定数目的Hoppers。

所以方法的签名是:

bool(int[] parties, int maxHopperSize, int hopperCount)

比如parties是[2,3,2,4,3], maxHopperSize是8,hopperCount是2.那么返回的就是
true。
而如果parties是[3,3,3,1,2], maxHopperSize是4,hopperCount是3,那么返回就是
false。


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

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

发信人: NewmanGG (小胖), 信区: JobHunting
标  题: Re: 贡献一道AAA游戏公司的onsite的面试题
发信站: BBS 未名空间站 (Sun Aug 30 03:57:09 2015, 美东)

只能搜,如果hoppercount不大(比如2、3)可以动态规划,但是复杂度是
maxHoppersize^hopperCount
本身这题是NP完全的,因为假设存在多项式算法,那么下面这个问题可解:
给定N个数,是否可以分两组,使得和一样
maxHopperSize=SUM/2
hopperCount=2
而这个partition problem是NP完全的
https://en.wikipedia.org/wiki/Partition_problem
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 128.]

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

发信人: hplp (hplp), 信区: JobHunting
标  题: Re: 贡献一道AAA游戏公司的onsite的面试题
发信站: BBS 未名空间站 (Sun Aug 30 04:05:10 2015, 美东)

combination sum的变种?加了额外条件是
#1 sum可以是 <= maxsum
#2 和数字的个数?

记得见过fb的面试,有一题类似
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 50.]

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

发信人: InzaghiFly (Inzaghi), 信区: JobHunting
标  题: Re: 贡献一道AAA游戏公司的onsite的面试题
发信站: BBS 未名空间站 (Sun Aug 30 04:26:45 2015, 美东)

hopperCount可以很大,
谁能给写个code看看。

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

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

发信人: tigerwinter (Frostmourne hungers.), 信区: JobHunting
标  题: Re: 贡献一道AAA游戏公司的onsite的面试题
发信站: BBS 未名空间站 (Sun Aug 30 11:38:46 2015, 美东)

可以先排序,然后对排在最前(或者最后的)count个element求和?
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 73.]

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

发信人: cowboy747 (vow), 信区: JobHunting
标  题: Re: 贡献一道AAA游戏公司的onsite的面试题
发信站: BBS 未名空间站 (Sun Aug 30 12:32:55 2015, 美东)

感觉类似内存chunk的分配,每个64 bit 的word占8个byte,等于说每个坑的大小是8,
然后总共有N个坑,问给你一堆东西能否塞进这N个坑,前提是同一个东西不能跨两个坑。

不知道这样能不能行,party从大到小排序。hopper按剩余空间做index(hash table)
和 max heap。

对于每下一个party,如果能找到正好可以完全占满的hopper,放进去,不然就放入当
前最大的hopper里。update hopper的hash table和heap。直至结束。

比如parties是[2,3,2,4,3], maxHopperSize是8,hopperCount是2.那么返回的就是
true。

party: 4 3 3 2 2
hopper: 8 8

hopper依序变成 4 8 # 4 5 # 4 2 # 4 0 # 2 0#



而如果parties是[3,3,3,1,2], maxHopperSize是4,hopperCount是3,那么返回就是
false。

party: 3 3 3 2 1
hopper: 4 4 4

hopper依序变成 1 4 4 # 1 1 4 # 1 1 1 # 遇到2 fail。

--
※ 修改:·cowboy747 於 Aug 30 12:37:03 2015 修改本文·[FROM: 205.]
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 205.]

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

发信人: vincexu (元始天尊级别的老帐户), 信区: JobHunting
标  题: Re: 贡献一道AAA游戏公司的onsite的面试题
发信站: BBS 未名空间站 (Sun Aug 30 15:53:00 2015, 美东)

反例:  5 5 3 3 3
maxHopperSize  10
hopperCount    2


【 在 cowboy747 (vow) 的大作中提到: 】
: 感觉类似内存chunk的分配,每个64 bit 的word占8个byte,等于说每个坑的大小是8,
: 然后总共有N个坑,问给你一堆东西能否塞进这N个坑,前提是同一个东西不能跨两个
坑。
: 不知道这样能不能行,party从大到小排序。hopper按剩余空间做index(hash table)
: 和 max heap。
: 对于每下一个party,如果能找到正好可以完全占满的hopper,放进去,不然就放入当
: 前最大的hopper里。update hopper的hash table和heap。直至结束。
: 比如parties是[2,3,2,4,3], maxHopperSize是8,hopperCount是2.那么返回的就是
: true。
: party: 4 3 3 2 2
: hopper: 8 8
: ...................



--

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

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

发信人: InzaghiFly (Inzaghi), 信区: JobHunting
标  题: Re: 贡献一道AAA游戏公司的onsite的面试题
发信站: BBS 未名空间站 (Sun Aug 30 22:34:12 2015, 美东)

这题在leetcode里,够格算hard的不?

[在  NewmanGG (小胖) 的大作中提到:]
:只能搜,如果hoppercount不大(比如2、3)可以动态规划,但是复杂度是
:maxHoppersize^hopperCount
:...........

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

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

发信人: miyahengheng (哼哼), 信区: JobHunting
标  题: Re: 贡献一道AAA游戏公司的onsite的面试题
发信站: BBS 未名空间站 (Mon Aug 31 10:58:57 2015, 美东)


  都NPC了, 放哪儿也是最难的问题了啊.

【 在 InzaghiFly (Inzaghi) 的大作中提到: 】
: 这题在leetcode里,够格算hard的不?
: [在  NewmanGG (小胖) 的大作中提到:]
: :只能搜,如果hoppercount不大(比如2、3)可以动态规划,但是复杂度是
: :maxHoppersize^hopperCount
: :...........



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

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

发信人: jobhunter123 (jobhunting), 信区: JobHunting
标  题: Re: 贡献一道AAA游戏公司的onsite的面试题
发信站: BBS 未名空间站 (Mon Aug 31 11:17:59 2015, 美东)

AAA是公司名吗?
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 73.]

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

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

友情链接


 

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

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