一亩三分地论坛

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

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

狗家八月纽约面经

[复制链接] |试试Instant~ |关注本帖
gogogogogogo 发表于 2016-10-28 16:40:06 | 显示全部楼层 |阅读模式

2016(7-9月) 工程类 硕士 全职@Google - 猎头 - Onsite |Pass在职跳槽

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

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

x
面试完一直要处理一些乱七八糟的事情。现在才发。我是8月面的。
. 鍥磋鎴戜滑@1point 3 acres
有两道题比较值得分享:
1. 算法。 一个游戏,两个人玩,交替给出一个字母,这个字母与前面所有的字母要是一个单词的前缀,最先拼出一个单词的那人输。
例如: 玩家1 先出一个字母 z, 玩家2 可以接着出字母 o, 但是不能出字母 b, 因为应该没有一个单词的前缀是zb, 然后玩家1 接着 zo 出字母,如果玩家1 出了字母 o,那么玩家1就输了。 因为zoo 是一个单词。但是玩家1可以出 n, 这时候玩家2 只能出字母 e, 那么玩家2就输了,因为zone 是个单词。
  写程序实现这个游戏。

2. 设计题: 狗家随时收到推特的数据流,设计一个系统从数据流中找出trending topics.

本帖被以下淘专辑推荐:

zzgzzm 发表于 2016-10-28 20:06:08 | 显示全部楼层
第二题:请问思路是按给了一个实时不断出现的string stream,然后要不停地找出top frequently 出现的几个单词吗?我假设top frequent words 就算是被提到最popular 的trending topics.
回复 支持 反对

使用道具 举报

nibuxing 发表于 2016-10-28 22:41:30 | 显示全部楼层
问一下楼主是直接投的nyc office吗
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-10-29 01:46:18 | 显示全部楼层
1. 算法。 两个人玩,交替给出一个字母。这个题很有意思。我的想法是用Trie来存字典中所有的单词,每个node用一个bool isWord来表示当前的node是否表示一个单词,若字典中一个单词已经是另一个单词的prefix,那么长单词就根本无需加入到Trie中了,因为这个游戏不可能进行到那一步。
请问这个题面试官有没有问先走的人有没有必胜的策略呢(这个是我认为比较non-trivial的问题)?我用recursion写了一个canWinNewGame的方法,就是先遍历当前所有的选择,然后看对手有没有必败的结果,若有那么第一人有必胜策略,否则没有必胜策略。当第一人有必胜策略时,因为第二人(自然没有必胜策略)的走法可以随机,所以我不好打印所谓的必胜策略路径。. from: 1point3acres.com/bbs
想请问一下面试官对这个游戏的设计有哪些要求和条件呢?.1point3acres缃
  1. struct TrieNode {
  2.   bool isWord;
  3.   vector<TrieNode*> next;
  4.   TrieNode(bool flag) :isWord(flag), next(vector<TrieNode*>(26, NULL)) {}
  5. };
    . Waral 鍗氬鏈夋洿澶氭枃绔,
  6. . 鍥磋鎴戜滑@1point 3 acres
  7. class TrieGame {
  8. private:
  9.   string _player1, _player2;
  10.   TrieNode* _root, *_cur;
  11.   bool _firstPlayerToMove;

  12.   TrieNode* createTrie(const unordered_set<string>& dict) {
  13.     auto r = new TrieNode(false);
  14.     auto cur = r;. more info on 1point3acres.com
  15.     for (const auto& w : dict) {
  16.       for (const auto& c : w) {
  17.         int idx = c - 'a';
  18.         if (!cur->next[idx]) cur->next[idx] = new TrieNode(false);
  19.         else if (cur->next[idx]->isWord) continue;
  20.         cur = cur->next[idx];
  21.       }
  22.       cur->isWord = true;
  23.     }
  24.     return r;
  25.   }

  26.   bool canWinAtNode(TrieNode* r) {
  27.     if (r->isWord) return true;
  28.     for (auto x : r->next) { if (!canWinAtNode(x)) return true; }
  29.     return false;
  30.   }

  31. public:
  32.   TrieGame(const unordered_set<string>& dict, string player1, string player2) :
  33.     _player1(player1), _player2(player2), _root(createTrie(dict)), _firstPlayerToMove(true)
  34.   {
  35.     _cur = _root;
  36.   } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

  37.   void resetGame() {
  38.     _cur = _root; _firstPlayerToMove = true;
  39.   }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

  40.   bool canWinNewGame() {
  41.     string name = _firstPlayerToMove ? _player1 : _player2;
  42.     bool canWin = canWinAtNode(_root);
  43.     cout << name << " will " << (canWin ? "win" : "lose") << " the new game.\n";
  44.     return canWin;
  45.   }

  46.   bool canWinCurrentGame() {
  47.     string name = _firstPlayerToMove ? _player1 : _player2;. more info on 1point3acres.com
  48.     bool canWin = canWinAtNode(_cur);
  49.     cout << name << " will " << (canWin ? "win" : "lose") << " the current game.\n";. from: 1point3acres.com/bbs
  50.     return canWin;
  51.   }

  52.   bool makeRandomMove() {
  53.     if (!_cur) { cout << "Game over!\n"; return false; }
  54.     vector<TrieNode*> options;
  55.     for (auto x : _cur->next) if (x) options.push_back(x);
  56.     _cur = options[rand() % options.size()];
  57.     if (_cur->isWord) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
  58.       cout << (_firstPlayerToMove ? _player1 : _player2) << "lost the game!\n"; _cur = NULL;
  59.     }
  60.     _firstPlayerToMove = !_firstPlayerToMove;
  61.     return true;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  62.   }
  63. };
复制代码
回复 支持 反对

使用道具 举报

 楼主| gogogogogogo 发表于 2016-10-29 07:29:05 | 显示全部楼层
zzgzzm 发表于 2016-10-28 20:06
第二题:请问思路是按给了一个实时不断出现的string stream,然后要不停地找出top frequently 出现的几个单 ...
. from: 1point3acres.com/bbs
其实我也不知道要怎么答。就按照平时积累瞎抡了一下。先说说应该有几个模块,比如topic 提取模块,这个我没具体说,就说可能要用到natural language processing。然后假设已经有从twits 中提取topic 的技术,然后怎么count topic. 那么大的数据量需不需要上cache, 是程序内部cache, 还是需要用到external cache, 需不需要load balancer,  再分析存储需要占的空间,怎么存储,sql 型数据库存的话table 怎么设计,要不要index, query 怎么写,存储query 和access query. 要是得用no sql 存的话,key-value pair 是啥。不过你理解的trending topic 跟我一样错了。trending != hot. 在我都快抡完的时候面试官说给我举了个例子说比如奥巴马在twits 中出现一只很多,但是傅园慧在奥运期间被twit的数据量急剧上升,虽然奥黑出现次数比傅园慧更多,但是奥黑不是,傅园慧是。
但是我觉得这个不影响面试官想考察的能力。反正你能自圆其说应该就行了
回复 支持 反对

使用道具 举报

 楼主| gogogogogogo 发表于 2016-10-29 07:32:34 | 显示全部楼层
nibuxing 发表于 2016-10-28 22:41
问一下楼主是直接投的nyc office吗

他家猎头找的
回复 支持 反对

使用道具 举报

 楼主| gogogogogogo 发表于 2016-10-29 07:53:31 | 显示全部楼层
zzgzzm 发表于 2016-10-29 01:46
1. 算法。 两个人玩,交替给出一个字母。这个题很有意思。我的想法是用Trie来存字典中所有的单词,每个node ...

如果两个玩家都足够聪明,那么给定一个dictionary, 先手胜负就确定了。
用recursion 的思路是对的。但是你确定当前node 胜负的时候有些问题。
思路是,如果当前node 是单词,那么不管这个node还有没有child, canwin  at 当前node 是 false.
如果不是单词,若当前node 的所有children 所携带的canwin 都是false,那么当前node 的canwin = true.
如果任何一个child 的canwin 是true.那么当前node 是false.

面试官没有任何提示和进一步的要求,一直催我写代码。
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-10-29 08:46:39 | 显示全部楼层
gogogogogogo 发表于 2016-10-29 07:29
其实我也不知道要怎么答。就按照平时积累瞎抡了一下。先说说应该有几个模块,比如topic 提取模块,这个我 ...

很有道理,看来是否trending是和frequency的变化率有关的,不一定和绝对的frequency直接挂钩。
看了LZ的分析获益匪浅。不知LZ的背景是否和distributed system直接相关?我也是在职,但专业和背景都不是这方面的,而在职的又比较可能问到这些,所以自己脑补啊。。。
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-10-29 10:20:00 | 显示全部楼层
gogogogogogo 发表于 2016-10-29 07:53
如果两个玩家都足够聪明,那么给定一个dictionary, 先手胜负就确定了。
用recursion 的思路是对的。但是 ...

这个我还是改成这样的。因为当一个人make move从当前是单词的node开始走的时候,这个node其实是上个人走到这里的,所以这个人就赢了。我自己还run了几个简单的例子。

补充内容 (2016-10-29 10:40):
例如字典都是单字母单词dict = { "a", "b", "c" },那么很明显先走的人就输定了。但Trie的root node是一个isWord=false的假节点,它的所有子节点都是isWord=true, 所以在for loop里的每个canWinAtNode都返回true。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 20:39

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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