一亩三分地论坛

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

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

LinkedIn电面第二轮,中奖了。。。

[复制链接] |试试Instant~ |关注本帖
qshen1989 发表于 2014-8-8 05:07:43 | 显示全部楼层 |阅读模式

2014(7-9月) 码农类 硕士 全职@Linkedin - 网上海投 - 技术电面 |Other

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

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

x
又被问了个面经外的题,目测是杯具了,实在是没梳理出逻辑boolean canIWin(int maxNum, int target),从1,2...maxNum的数组里两个玩家轮流选数,第一个达到sum>=target的玩家获胜,问如何判断先选的玩家能获胜。
能想到的就是先求总和sum, 如果sum < target 无解, false
                                           如果sum == target, 根据数组的长度判断,奇数个则true偶数个false
然后是sum>target, 双方的目标是要至少保证选完数x后target-x > 数组里留下的最大数,然后递归,根据回合数的奇偶判断是true还是false。然后就这个逻辑不知道该怎么实现了。。。

为啥就不能碰个面经里的题呢>.<

评分

2

查看全部评分

billupus 发表于 2014-10-2 00:55:24 | 显示全部楼层
上面代码helper错了。把删除的数加回去是一定要做的,否则不对。下面这段应该没问题:. Waral 鍗氬鏈夋洿澶氭枃绔,

private static boolean helper(ArrayList<Integer> numList, int target) {
                /* empty list, return false */-google 1point3acres
                if(numList.size() == 0) {
                        return false;
                }
                boolean opRes = true;            //results of opponent
                for(int i = 0; i < numList.size(); i++) {
                        int num = numList.get(i);
                        if(num >= target) {
                                /* pick this number, I will win */
                                return true;
                        }
                        numList.remove(i);       //I pick this one
                        if(!helper(numList, target - num)) {
                                /* my opponent cannot win */. From 1point 3acres bbs
                                opRes = false;
                        }
                        numList.add(i, num);    //I don't pick this one since my opponent will always win, add it back
                }
                return !opRes;             //if among these numbers picking one of them will let my opponent lose, then I will win
        }
回复 支持 3 反对 0

使用道具 举报

zhenggao1986 发表于 2014-8-9 19:08:30 | 显示全部楼层
这个直接按照逻辑写就可以了
先手胜的情况是
n 轮(先手): 当前的数组中存在一个数使得 Sum > target.
n-1轮(后手): 当前的数组中选任何一个数 X 都不能使得 Sum > target. 但是当后手选完之后存在一个数可使得 Sum > target

代码也不长
public class PickUpNumbers {
    public boolean canIWin(int[] numberPool, int target) {
        boolean isEmpty = true;
        for (int data : numberPool). 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
            if (data > 0) isEmpty = false;
        if (isEmpty) return false;
        else {
            if (target <= 0) return false;
            for (int data : numberPool).1point3acres缃
                if (data > 0 && data >= target) return true;
            boolean canIWinFlag = false;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
            for (int i = 0; i < numberPool.length && numberPool[i] > 0; ++i) {
                int data = numberPool[i];. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                numberPool[i] = -1;. more info on 1point3acres.com
                canIWinFlag = canIWinFlag || !canIWin(numberPool, target - data); // other's turn
                numberPool[i] = data;. Waral 鍗氬鏈夋洿澶氭枃绔,
            }. visit 1point3acres.com for more.
            return canIWinFlag;.鐣欏璁哄潧-涓浜-涓夊垎鍦
        }
    }

    public static void main(String[] args) {
        int[] numberPool = {1, 2, 3};
        System.out.println(new PickUpNumbers().canIWin(numberPool, 5));
        System.out.println(new PickUpNumbers().canIWin(numberPool, 4));. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
    }
}

运行结果
true
false
回复 支持 1 反对 0

使用道具 举报

yxyxyx 发表于 2014-8-8 05:28:04 | 显示全部楼层
我觉得这个问题里面有一个点你没注意到:
在你说的这个游戏里,不论先选还是后选,最优方案肯定是选剩下的数里面最大的。选小的没有意义啊
这样的话,选的方式肯定是先手选maxNum, 然后后手选maxNum-1, 先手选maxNum-2, 后手选maxNum-3...
这样的话,其实先手只能选maxNum,maxNum-2, maxNum-4, maxNum-6...maxNum-2k, k属于自然数。 又因为先手手中的sum肯定总是比后手手中的sum大,所以你只需要算一下先手能拿的所有数是否>=target即可,是则先手能赢,否则先手不会赢(但是在这个状态下其实没有人赢)。
回复 支持 反对

使用道具 举报

 楼主| qshen1989 发表于 2014-8-8 05:30:21 | 显示全部楼层
yxyxyx 发表于 2014-8-8 05:28. From 1point 3acres bbs
我觉得这个问题里面有一个点你没注意到:
在你说的这个游戏里,不论先选还是后选,最优方案肯定是选剩下的 ...

. from: 1point3acres.com/bbs 给你个反例,{1,2,3}, target=5,你先手肯定选1
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
补充内容 (2014-8-8 05:31):
可能是没说清楚,是双方选的所有数的和大于等于target

补充内容 (2014-8-8 05:32):
记得像初中还是小学的奥数题。。。实在是忘记怎么做了
回复 支持 反对

使用道具 举报

yxyxyx 发表于 2014-8-8 05:49:59 | 显示全部楼层
qshen1989 发表于 2014-8-7 17:30
给你个反例,{1,2,3}, target=5,你先手肯定选1. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

补充内容 (2014-8-8 05:31):

哦我明白了。
不过这样的话,鉴于你说的:
“双方的目标是要至少保证选完数x后target-x > 数组里留下的最大数”
那其实最优策略是:
target-x > 数组里留下的最大数,则选数组里留下的最小数
否则,选数组里留下的最大数
所以,每一回合只有三种可能:
1. 先手选最小数,后手选次小数,谁都没赢;
2. 先手选最小数,后手选最大数,后手赢;
3. 先手选最大数,先手赢。
这样一来逻辑应该就清晰很多。
代码如下:
bool canIWinHelper(int curMax, int curMin, int target) {
   if(curMax >= target) return true;
   if(curMax + curMin >= target) return false;
   return canIWinHelper(curMax, curMin+2, target-curMin-(curMin+1));
}
回复 支持 反对

使用道具 举报

 楼主| qshen1989 发表于 2014-8-8 06:23:42 | 显示全部楼层
yxyxyx 发表于 2014-8-8 05:49
哦我明白了。
不过这样的话,鉴于你说的:
“双方的目标是要至少保证选完数x后target-x > 数组里留下的 ...

貌似是正解。。。好吧,真的是纯数学题啊~
回复 支持 反对

使用道具 举报

ototsuyume 发表于 2014-8-8 12:26:52 | 显示全部楼层
yxyxyx 发表于 2014-8-8 05:49
哦我明白了。
不过这样的话,鉴于你说的:. Waral 鍗氬鏈夋洿澶氭枃绔,
“双方的目标是要至少保证选完数x后target-x > 数组里留下的 ...

这解法有问题,比如max=6,target=17这种情况,你的解法得出的是后手胜,但是只要先手选了1,无论后手怎么选,先手都有方法必胜
回复 支持 反对

使用道具 举报

1guangnian 发表于 2014-8-8 16:25:34 | 显示全部楼层
感觉不管谁走,只要不能赢,就选最小的数
回复 支持 反对

使用道具 举报

yxyxyx 发表于 2014-8-8 19:15:17 | 显示全部楼层
ototsuyume 发表于 2014-8-8 00:26
这解法有问题,比如max=6,target=17这种情况,你的解法得出的是后手胜,但是只要先手选了1,无论后手怎 ...
. 1point3acres.com/bbs
嗯你说的对,先手只要前两轮选了1和6就可以保证必胜。看来我的思路还是有问题。
回复 支持 反对

使用道具 举报

 楼主| qshen1989 发表于 2014-8-8 23:30:10 | 显示全部楼层
Write a procedure, "Boolean canIWin(int maxChoosableInteger, int desiredTotal)",
which returns true if the first player to move can force a win with optimal play.. From 1point 3acres bbs
条件里有一句with optimal play,就是假定双方都是按照最佳的玩法来玩,先手能否必胜。这样的话6,17这种情况应该是false吧如果后手先选了6的话。。。但是这样那个算法的确没有cover到这种选法

补充内容 (2014-8-8 23:32):-google 1point3acres
额,貌似选了6还是先手赢= =
回复 支持 反对

使用道具 举报

1guangnian 发表于 2014-8-9 13:53:38 | 显示全部楼层
这个题,选过的数字还能再选么
回复 支持 反对

使用道具 举报

 楼主| qshen1989 发表于 2014-8-9 15:36:07 | 显示全部楼层
1guangnian 发表于 2014-8-9 13:53
这个题,选过的数字还能再选么
. 1point3acres.com/bbs
选过了就不能再选了
回复 支持 反对

使用道具 举报

zhenggao1986 发表于 2014-8-9 20:01:28 | 显示全部楼层
把平局考虑进去的话,代码如下
. more info on 1point3acres.com
enum Result {Win, Lose, Draw}

public class PickUpNumbers {-google 1point3acres
    public static Result canIWin(int[] numberPool, int target) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
        if (target <= 0) return Result.Lose;
        boolean isEmpty = true;.鐣欏璁哄潧-涓浜-涓夊垎鍦
        for (int data : numberPool)
            if (data > 0) isEmpty = false;
        if (isEmpty) return Result.Draw;
        else {. 1point 3acres 璁哄潧
            for (int data : numberPool) 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                if (data >= target) return Result.Win;
            Result drawFlag = Result.Draw;
            for (int i = 0; i < numberPool.length; ++i) {
. Waral 鍗氬鏈夋洿澶氭枃绔,                if (numberPool[i] > 0) {
                    int data = numberPool[i];
                    numberPool[i] = -1;
                    Result rivalResult = canIWin(numberPool, target - data); // rival's turn. 鍥磋鎴戜滑@1point 3 acres
                    if (rivalResult == Result.Win) drawFlag = rivalResult;
                    if (rivalResult == Result.Lose) return Result.Win;. 1point3acres.com/bbs
                    numberPool[i] = data;. 鍥磋鎴戜滑@1point 3 acres
                }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
            }
            if (drawFlag == Result.Draw) return Result.Draw;. more info on 1point3acres.com
            return Result.Lose; // whatever number i choose, rival wins
        }
    }

    public static void main(String[] args) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
        int[] numberPool = {1, 2, 3};
        System.out.println(PickUpNumbers.canIWin(numberPool, 5));
        System.out.println(PickUpNumbers.canIWin(numberPool, 4));
        System.out.println(PickUpNumbers.canIWin(numberPool, 8));
    }.鏈枃鍘熷垱鑷1point3acres璁哄潧
}
. 1point3acres.com/bbs
运行结果. more info on 1point3acres.com
Win
Lose
Draw
回复 支持 反对

使用道具 举报

北美农民 发表于 2014-8-9 20:50:22 | 显示全部楼层
不用考虑奇偶。

canIWin(set{1..maxNum}, int target)先手必胜的条件是, 所有的 canIWin(set {1..MaxNum}中选出一个元素x, target - x) 状态中有1个状态先手会输(只要有一个就行了).
. from: 1point3acres.com/bbs
回复 支持 反对

使用道具 举报

北美农民 发表于 2014-8-9 20:51:01 | 显示全部楼层
en, 12楼正解。
回复 支持 反对

使用道具 举报

 楼主| qshen1989 发表于 2014-8-10 06:13:33 | 显示全部楼层
zhenggao1986 发表于 2014-8-9 19:08
这个直接按照逻辑写就可以了
先手胜的情况是
n 轮(先手): 当前的数组中存在一个数使得 Sum > target.
. visit 1point3acres.com for more.
学习了。。。!!
回复 支持 反对

使用道具 举报

 楼主| qshen1989 发表于 2014-8-10 06:14:35 | 显示全部楼层
zhenggao1986 发表于 2014-8-9 19:08
这个直接按照逻辑写就可以了
先手胜的情况是
n 轮(先手): 当前的数组中存在一个数使得 Sum > target.

弱弱的问一句你这题考虑了多久?
回复 支持 反对

使用道具 举报

zhenggao1986 发表于 2014-8-10 10:25:43 | 显示全部楼层
看完就想到了啊,连写代码加调试一共用了半小时,
主要是调试费时间80%都是在调试,一开始写出来的代码不是这样的,哈哈哈。
不过唬住面试官应该够了。
这个题,题目本身有个Bug,不该给一个boolean的输出,应该是按照我后来那样的代码,给三种状态输出才对。. 鍥磋鎴戜滑@1point 3 acres
不然的话如果Target大于所有数值和的时候也会判定先手胜,调试花的时间主要就是解决那个bug的。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
估计是面试官把您带沟里去了,他就不该给你限定死函数的输入和输出。
回复 支持 反对

使用道具 举报

zhenggao1986 发表于 2014-8-10 10:28:33 | 显示全部楼层
12楼的那个有bug, 13楼我给的那个答案是我认为最正确的
回复 支持 反对

使用道具 举报

忽而今夏 发表于 2014-8-10 11:49:20 | 显示全部楼层
zhenggao1986 发表于 2014-8-10 10:28
12楼的那个有bug, 13楼我给的那个答案是我认为最正确的

按照ls之前讨论的{1,2,3,4,5,6}和17的例子,只要先手拿1或6就肯定赢,就意味着{1,2,3,4,5}和11的话先手肯定赢不了
你的程序{1,2,3,4,5,6}和17的结果是Win,但{1,2,3,4,5}和11的结果也是Win,可是按照这个理论第二个结果应该是Lose啊...
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 23:23

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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