Google Phone Interview 求米!

求米求米!!~

Timeline:
9月底内推
11月中做的OA 传送门 -> https://www.1point3acres.com/bbs/thread-571801-1-1.html
12月中phone interview

题目背景:

有一个游戏 叫Ghost 给一个"dictionary" 两个人轮流说字母 说出字母组成给的字典里的单词 或者不可能组成字典里的单词的那个人 就输了
Ex:
dict = {"bread", "apple"}
从第一个人开始
b r e a d -> player 1 lose
b c -> player 2 lose

我们要写一个class 来支持这个游戏


每一个player 是一个这个class的instance


然后要写一个method, input 是一个字母 (上一个人说的字母)  output 也是一个字母 (我这轮说的字母) 并且在选择字母的时候 选一个不会让我立刻输的字母


这个class 需要保留之前说过的东西

ex:
dict = {"bread", "ape"}
p1.class()
p2.class()
p1.method("") -> a
p2.method("a") -> p
p1.method("p") -> e -> lose
以下内容需要积分高于 100 您已经可以浏览

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

补充内容 (2020-3-30 23:04):
咦? 才发现 不小心把follow up的题目放在hide里面了 在这里补充一下
follow up:
这个method 如果要求output 保证能赢的字母 要怎么做

补充内容 (2020-4-2 23:12):
还有onsite的面经哦~ 传送门 -> https://www.1point3acres.com/bbs/thread-617689-1-1.html

guan99_tr 发表于 2020-3-30 12:36
这个method只用选出trie里路径长度为偶数的就可以是吗？这题是在考察什么啊

我感觉没那么简单，你选出偶数长度的也不一定赢，因为路径可以有很多条，很多相同前缀的词在当前节点后面，你选了偶数别人后面也可以选之前你认为是奇数的路径；如果要稳赢的话要枚举可能是动归或者记忆化搜索出一条稳赢的路径才行，目测hard难度

这个method只用选出trie里路径长度为偶数的就可以是吗？这题是在考察什么啊

guan99_tr 发表于 2020-3-30 12:36
这个method只用选出trie里路径长度为偶数的就可以是吗？这题是在考察什么啊

第一问没那么复杂 只要我选的字母 不会让我这一轮马上输掉 就可以
我感觉考的应该就是trie

guan99_tr 发表于 2020-3-30 12:36
这个method只用选出trie里路径长度为偶数的就可以是吗？这题是在考察什么啊

不过follow up就比较难了 建议参考蠡口肆陆肆

我觉得这个就是根据dictionary建立Trie，游戏就转化为两个players A, B轮流沿trie edge走，若Player A从root node开始，A有没有必胜策略走到某个leaf （i.e., B无路可走）.
这个就是博弈论, A有必胜策略就等价于A当前存在一个option，使得B没有必胜策略 （DFS解决）。

1. Node {
   
2.   vector<Node*> next(26);
   
3.   bool isWord; // not relevant for this problem
   
4. };
   
5. 
   
6. // assume Trie is built with root at r
   
7. bool canWin(Node* r) {
   
8.   for (Node* x : r->next) {
   
9.     if (x && !canWin(x)) return true;
   
10.   }
    
11.   return false;
    
12. }
    

复制代码

AB 足够聪明的情况下    给定 dict下    先手的胜/负似乎是必然结果