一亩三分地论坛

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

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

Google电面新鲜面经

[复制链接] |试试Instant~ |关注本帖
dm37537 发表于 2015-7-12 12:50:40 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 本科 全职@Google - 猎头 - 技术电面 |Pass其他

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

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

x
周四Google电面完,周五收到onsite,周六来发下面经。

可能是因为我做得慢,总共就做了一道题,就是一个游戏。 . Waral 鍗氬鏈夋洿澶氭枃绔,
input string:“+++--++-+”.鐣欏璁哄潧-涓浜-涓夊垎鍦
游戏规则:每人每次可以 flip "++" to "--"(必须是相邻的)


第一问:generate all possible moves
第二问:determine if this player can will
Extra:这两个问题的implementation的Big-O


补充内容 (2015-7-12 13:13):
下个人没法flip了这个人就赢;all possible moves for next flip

评分

7

查看全部评分

 楼主| dm37537 发表于 2015-7-12 22:02:10 | 显示全部楼层
第一问:遍历string,每次flip,创建新string,加入list
第二问:recursive嵌套for loop,使用第一问method,直到没有possible moves
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
同志们给米啊。

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

YY大帝 发表于 2015-7-12 13:01:13 | 显示全部楼层
请问怎么才算赢
回复 支持 反对

使用道具 举报

stellari 发表于 2015-7-12 13:05:00 | 显示全部楼层
感谢分享!之前看地里有人提过这题。想问一下,all possible moves指的是“从目前的input string开始,仅进行一次flip操作的所有可能”,还是“从目前的input string开始,进行K次交替flip操作(直至有一位玩家胜利),然后返回所有的flip sequence”?
回复 支持 反对

使用道具 举报

say543 发表于 2015-7-12 13:50:09 | 显示全部楼层
之前有看過這個問題  但是一職沒有完整的solution LZ可以分享一下思路嗎
回复 支持 反对

使用道具 举报

头像被屏蔽
zxy4159526 发表于 2015-7-12 15:15:02 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

blueseen 发表于 2015-7-12 15:19:23 | 显示全部楼层
我觉得可能是,第一问递归输出所有的可能的操作序列。第二问是问两人都采用最优策略的情况下哪个人赢。最直接的就是求SG值,NIM什么的,博弈论相关的。
回复 支持 反对

使用道具 举报

stellari 发表于 2015-7-12 18:05:07 | 显示全部楼层
blueseen 发表于 2015-7-12 15:19-google 1point3acres
我觉得可能是,第一问递归输出所有的可能的操作序列。第二问是问两人都采用最优策略的情况下哪个人赢。最直 ...

这题肯定能用博弈论的方法分析,但是如果那样的话,作为电面的题我觉得难度有点大了。应该是有比较简单的,不需要懂博弈论也能想到的做法
回复 支持 反对

使用道具 举报

stellari 发表于 2015-7-13 01:47:34 | 显示全部楼层
blueseen 发表于 2015-7-12 15:19
我觉得可能是,第一问递归输出所有的可能的操作序列。第二问是问两人都采用最优策略的情况下哪个人赢。最直 ...

刚刚去恶补了一下博弈论,最后终于靠着SG定理找到一个O(N^2)解法。等我组织下语言,明天贴完整算法分析。
回复 支持 反对

使用道具 举报

handsomecool 发表于 2015-7-13 05:35:12 | 显示全部楼层
直接暴力法面试官满意么,用backtracking, 一旦发现对手输了,立即return true?
  1. bool backTracking(string &s, bool myTurn){
  2.         bool foundMove = false;
  3.         for (int i = 0; i<s.length() - 1; i++){
  4.                 if (s[i] == '+' && s[i + 1] == '+'){. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  5.                         foundMove = true;. from: 1point3acres.com/bbs
  6.                         s[i] = '-';
  7.                         s[i + 1] = '-';
  8.                         //一旦找到对手会输的情况,说明玩家是有可能赢的,立即中止
  9.                         if (backTracking(s, !myTurn)) return true;
  10.                         s[i] = '+';
  11.                         s[i + 1] = '+';
  12.                 }
  13.         }
  14.         if (!foundMove && !myTurn) return true;. more info on 1point3acres.com
  15.         return false;
  16. }. visit 1point3acres.com for more.


  17. int main()
  18. {
  19.         string input = "++++--++-+";. 鍥磋鎴戜滑@1point 3 acres
  20.         //玩家先走, myTurn = true
  21.         if (backTracking(input, true)) cout << "can win" << endl;.1point3acres缃
  22.         else cout << "can't win" << endl;;
  23. }
复制代码
复杂度 O(2^n)
.1point3acres缃
我想这题有更简单的数学做法吧,比如说input = "++--++-++",这里只有三个"++", 只能flip三次那玩家如果后走就必输。更普遍的结论就是有奇数次的flip的话,后走的必输。 这是flip次数绝对的情况,而如果input里面含有连续三个"+"以上的情况,比如"++++---------++",那一共可以flip的次数可能是3次,也可能是2次,不是绝对的。 (因为"++++"可以flip一次变成"+--+",或者flip两次变成"----") 这样的话,玩家总是有赢的可能性的。
总结一下, 扫一遍input, 如果连续出现了k个"+", 且k>2&&k%2==0 那玩家一定有赢的可能; 如果没有发现这样的k在Input里面(总flip次数是确定的)那就回到了原来的结论:有奇数次的flip的话,后走的必输。

这样做的话,过一遍input就行了  O(n)
回复 支持 反对

使用道具 举报

handsomecool 发表于 2015-7-13 05:41:35 | 显示全部楼层
呃。。这个题目面试官说要考虑最优策略么,楼主?  那我的做法显然不行了。。
回复 支持 反对

使用道具 举报

storm_hair 发表于 2015-7-13 06:58:12 | 显示全部楼层
依旧是搜索
回复 支持 反对

使用道具 举报

stellari 发表于 2015-7-13 07:50:10 | 显示全部楼层
handsomecool 发表于 2015-7-13 05:35. visit 1point3acres.com for more.
直接暴力法面试官满意么,用backtracking, 一旦发现对手输了,立即return true?复杂度 O(2^n). from: 1point3acres.com/bbs

我想这题 ...

这段代码的复杂度我认为是O(N!)。理由是:. 1point3acres.com/bbs

假设有一个这样的输入["-------------------------++++++++++++++"],即N个减号后面跟N个加号。
那么,每一次函数调用都会先用O(N)时间跳过之前的减号,而在后面的+号序列中,if条件对于每一个 i 都满足,于是在+号有N-2的情况下进行下一次递归调用,因此递推公式为:
f(N) = kN + N*f(N-2)
这是O(N!)级别的运行时间。

从另一个角度来想,连续的N个+号中,最多能够取N/2次,最少能取N/3次。如果两人交替地取,那么即使是按照最少的N/3次来取,也会有A(N/3, N/3) = (N/3)!种不同的组合 (即N/3的全排列)。. From 1point 3acres bbs

所以无论怎么看,这样的做法都是O(N!)级别的。之所以不是2^N, 是因为有大量的重复情况,比如:[A取12,B取34,A取56]与[A取56,B取34,A取12]这两个操作序列会得到相同的局面,但是因为没有memoization,所以程序仍然会浪费大量时间来进行重复计算。递归的时间复杂度确实是可以控制在2^N内,但是前提是要能去重。
---------------------------------------------------------------------

如果双方都是用最优策略来做,那么“如果连续出现k(k为>2的偶数)个+,则先手玩家一定能赢”就不成立了。比如++++--++++,其中有两个连续为4的序列,但是先手玩家必输。因为无论先手玩家在其中一个序列中做什么操作,后手玩家只要在另一个序列中重复其操作即可保证赢。更复杂一点的,比如++++--++++++--++等也是先手必输。-google 1point3acres
回复 支持 反对

使用道具 举报

stellari 发表于 2015-7-13 08:23:18 | 显示全部楼层
刚刚总结了一个O(N^2)的解法,因为涉及到相当多的博弈论知识,请各位慎重观看:
.1point3acres缃
猛戳这里
回复 支持 反对

使用道具 举报

yawnzh 发表于 2015-7-13 08:37:34 | 显示全部楼层
感觉用dp做,只用考虑连续长度的++能不能赢,赢了奇数次就赢了。比如++--++++--++,对于++,++++,++都是赢的,一共三次,就用了,如果++-+++++对于++是赢的,+++++是输的,但是最后还是赢的。

补充内容 (2015-7-12 16:38):
然后连续长度的+谁赢用dp做就好了. more info on 1point3acres.com

补充内容 (2015-7-12 16:46):.鏈枃鍘熷垱鑷1point3acres璁哄潧
dp表示在长度为i+1的连续+上能不能赢,dp=dp[i-2] or dp[i-3]
回复 支持 反对

使用道具 举报

handsomecool 发表于 2015-7-13 09:27:05 | 显示全部楼层
stellari 发表于 2015-7-13 07:50
这段代码的复杂度我认为是O(N!)。理由是:.鏈枃鍘熷垱鑷1point3acres璁哄潧

假设有一个这样的输入["-------------------------++++++++ ...
. 1point3acres.com/bbs
英雄所见略同!

补充内容 (2015-7-13 10:10):. Waral 鍗氬鏈夋洿澶氭枃绔,
我的第一种解法确实是O(n!), 同时我理解的“能赢”是指有赢的可能(对手不采用最优策略),我的两种解法都是在这个前提下写的。。
回复 支持 反对

使用道具 举报

stellari 发表于 2015-7-13 10:02:32 | 显示全部楼层
yawnzh 发表于 2015-7-13 08:37
感觉用dp做,只用考虑连续长度的++能不能赢,赢了奇数次就赢了。比如++--++++--++,对于++,++++,++都是赢 ...

这也是我最初的思路,但是如果双方都是用最优策略的话,这种DP方案是不行的。主要是dp[ i ] = dp [ i - 2] OR dp [ i -3 ]这个状态转移方程不对,比如序列长为9时,dp[8] = dp[6] OR dp[5] = 1 OR 1 = 1,而事实上长为9的序列先手必输,此值应该为0。
回复 支持 反对

使用道具 举报

durandalk 发表于 2015-7-13 10:19:10 | 显示全部楼层
弱弱地问下楼主的专业背景是啥~?
回复 支持 反对

使用道具 举报

yawnzh 发表于 2015-7-13 11:47:26 | 显示全部楼层
stellari 发表于 2015-7-12 18:02
这也是我最初的思路,但是如果双方都是用最优策略的话,这种DP方案是不行的。主要是dp[ i ] = dp [ i - 2 ...

说错了,应该是dp[ i ]=(not dp[ i-2 ]) or (not dp[i -3])。dp[0]=dp[1]=True dp[2]=dp[3]=False。 这样可以吗?

补充内容 (2015-7-12 19:49):
又打错了dp[0]=dp[1]=False, dp[2]=dp[3]=True
回复 支持 反对

使用道具 举报

 楼主| dm37537 发表于 2015-7-13 11:53:11 | 显示全部楼层
durandalk 发表于 2015-7-13 10:19
弱弱地问下楼主的专业背景是啥~?
.鏈枃鍘熷垱鑷1point3acres璁哄潧
CS小本大四
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 07:42

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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