一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 810|回复: 13
收起左侧

Amazon一道Onsite 题

[复制链接] |试试Instant~ |关注本帖
cgdong2012 发表于 2014-12-13 06:34:50 | 显示全部楼层 |阅读模式

2014(7-9月) 码农类 硕士 全职@Amazon - Other - Onsite |Fail

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
一个朋友取A家面试遇到的一个题, 我到现在也没太懂咋解。
问题是这样的, 两个人玩游戏,给一个数组,俩人轮流选里面的数字, 看到最后谁的数字之和最大。
这题貌似也看到过其他人发出来, 请问有谁知道具体解法吗?
拜谢了
Adeath 发表于 2014-12-13 07:05:06 | 显示全部楼层
我记得以前好像有一道类似的  只能取首尾的  问最后取得的数的和  
这题是用递归做 每次取数前计算取哪个数可以获得更大的和  因为两人都会采用相同的策略  实际上数组确定后两人的取数就确定了
优化用DP
回复 支持 反对

使用道具 举报

MCwong 发表于 2014-12-13 08:34:52 | 显示全部楼层
数组可见么, 两人都是同一种策略吗?感觉可以用Minimax tree再加上alpha-beta pruning优化.
回复 支持 反对

使用道具 举报

 楼主| cgdong2012 发表于 2014-12-13 09:18:06 | 显示全部楼层
Adeath 发表于 2014-12-13 07:05
我记得以前好像有一道类似的  只能取首尾的  问最后取得的数的和  
这题是用递归做 每次取数前计算取哪个 ...

对,是只能取首尾的, 不能用贪婪算法, 因为对面的可能取到更大的数。 第一想法用递归没错,但是我还是不太理解这个题啥意思, 是给个数组,最后返回个 boolean 值来判断先手玩家输赢么? 能不能把你的想法写个伪代码表达一下
回复 支持 反对

使用道具 举报

 楼主| cgdong2012 发表于 2014-12-13 09:18:40 | 显示全部楼层
MCwong 发表于 2014-12-13 08:34
数组可见么, 两人都是同一种策略吗?感觉可以用Minimax tree再加上alpha-beta pruning优化.
. more info on 1point3acres.com
数组可见的, 经过楼上提醒, 是每次只能取首尾的数字。
回复 支持 反对

使用道具 举报

Adeath 发表于 2014-12-13 09:41:32 | 显示全部楼层
cgdong2012 发表于 2014-12-13 09:18
对,是只能取首尾的, 不能用贪婪算法, 因为对面的可能取到更大的数。 第一想法用递归没错,但是我还是 ...

http://www.1point3acres.com/bbs/ ... kbox%26sortid%3D311
找到这个帖子了  第二轮的题   鏉ユ簮涓浜.涓夊垎鍦拌鍧.
我的想法跟这个lz的是一样的
回复 支持 反对

使用道具 举报

 楼主| cgdong2012 发表于 2014-12-13 09:43:54 | 显示全部楼层
Adeath 发表于 2014-12-13 09:41. From 1point 3acres bbs
http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=95879&extra=page%3D1%26filter%3Dsorti ...

非常感谢, 这个题不知道解法今晚估计我睡不着了~
回复 支持 反对

使用道具 举报

jlin705 发表于 2014-12-13 10:05:20 | 显示全部楼层
我面google onsite考得这道题。。。。
回复 支持 反对

使用道具 举报

 楼主| cgdong2012 发表于 2014-12-13 10:36:45 | 显示全部楼层
jlin705 发表于 2014-12-13 10:05
我面google onsite考得这道题。。。。

我了个去, 这个题这么高频, 你最后解法是哪个? 面试官满意否?
回复 支持 反对

使用道具 举报

pyemma 发表于 2014-12-13 10:45:55 | 显示全部楼层
只能取首位的话是不是就是coin in a line那道题啊?是这个么?http://leetcode.com/2011/02/coins-in-line.html
回复 支持 反对

使用道具 举报

jacgraphy 发表于 2014-12-13 10:55:29 | 显示全部楼层
cgdong2012 发表于 2014-12-12 21:36. 1point3acres.com/bbs
我了个去, 这个题这么高频, 你最后解法是哪个? 面试官满意否?

我以前面试也碰到过这题,最后还是靠面试官提示才懂的。好像记得这题还有个条件是数组里一共有偶数个数。先手必胜。做法是事先算一下所有在奇数位置的数的总和,偶数位置的数的总和,哪个总和大决定从哪一头开始取。比如先手从头开始取,就等于选了奇数位置的组,取完留给后手的数,头尾都是偶数位置的,所以可以保证先手的总能取奇数位置,反之亦然。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
表述能力略差 = =,不知道这是不是lz想要的答案。
回复 支持 反对

使用道具 举报

 楼主| cgdong2012 发表于 2014-12-13 11:10:10 | 显示全部楼层
jacgraphy 发表于 2014-12-13 10:55
我以前面试也碰到过这题,最后还是靠面试官提示才懂的。好像记得这题还有个条件是数组里一共有偶数个数。 ...

http://www.1point3acres.com/bbs/ ... kbox%26sortid%3D311 这个帖子的第二问 和我遇到的问题一模一样。 你所说的解法要多加个你所说的限制条件就是必须是偶数个, 先手的玩家可以控制自己要奇数位置或者偶数位置的总和, 从而取得胜利对吧。 你的这个方法很巧妙
回复 支持 反对

使用道具 举报

 楼主| cgdong2012 发表于 2014-12-13 11:14:40 | 显示全部楼层
pyemma 发表于 2014-12-13 10:45
只能取首位的话是不是就是coin in a line那道题啊?是这个么?http://leetcode.com/2011/02/coins-in-line. ...

灰常感谢你的回复, coin in a line can take coins from one of the ends of the line, and there are even number coins. 这个和楼下那个应该是同一个问题, 和我那个不太一样。http://www.1point3acres.com/bbs/ ... kbox%26sortid%3D311 这个第二题。
回复 支持 反对

使用道具 举报

jacgraphy 发表于 2014-12-13 11:17:40 | 显示全部楼层
cgdong2012 发表于 2014-12-12 22:10
http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=95879&extra=page%3D1%26filter%3Dsorti ...

哦,条件确实不一样。不过我碰到这题的时候只是为了考思路,不用些代码,所以才会有偶数个这个简化条件吧。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-4 01:46

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表