送给你一份 五年西雅图生活 总结出的经验

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

锦晖律师事务所
12月16日
H1B讲座通知
E轮2.5亿美元融资
K12教育独角兽一起作业诚聘
机器学习/数据统计/教育等职位
码农求职神器Triplebyte:
不用海投
内推多家公司面试
高效直聘+内推,70%面试率
AI帮你免费完善简历
直击全美十万个科技职位
坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 2370|回复: 8
收起左侧

狗家八月纽约面经

[复制链接] |试试Instant~
我的人缘0
gogogogogogo 发表于 2016-10-28 16:40:06 | 显示全部楼层 |阅读模式
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (3)
 
 
0% (0)  踩

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

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

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

x
面试完一直要处理一些乱七八糟的事情。现在才发。我是8月面的。

有两道题比较值得分享:
1. 算法。 一个游戏,两个人玩,交替给出一个字母,这个字母与前面所有的字母要是一个单词的前缀,最先拼出一个单词的那人输。
例如: 玩
游客,本帖隐藏的内容需要积分高于 188 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.

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

上一篇:ibm dev-ops oa
下一篇:Two sigma 电面附solution

本帖被以下淘专辑推荐:

我的人缘0
zzgzzm 发表于 2016-10-28 20:06:08 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  98% (68)
 
 
1% (1)  踩
第二题:请问思路是按给了一个实时不断出现的string stream,然后要不停地找出top fre
游客,本帖隐藏的内容需要积分高于 10 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.
的trending topics.
回复

使用道具 举报

我的人缘0
nibuxing 发表于 2016-10-28 22:41:30 | 显示全部楼层
问一下楼主是直接投的
游客,本帖隐藏的内容需要积分高于 10 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.
ice吗
回复

使用道具 举报

我的人缘0
zzgzzm 发表于 2016-10-29 01:46:18 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  98% (68)
 
 
1% (1)  踩
1. 算法。 两个人玩,交替给出一个字母。这个题很有意思。我的想法是用Trie来存字典中所有的单词,每个node用一个bool isWord来表示当前的node是否表示一个单词,若字典中一个单词已经是另一个单词的prefix,那么长单词就根本无需加入到Trie中了,因为这个游戏不可能进行到那一步。
请问这个题面试官有没有问先走的人有
游客,本帖隐藏的内容需要积分高于 10 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.
印所谓的必胜策略路径。
想请问一下面试官对这个游戏的设计有哪些要求和条件呢?
  1. struct TrieNode {
  2.   bool isWord;
  3.   vector<TrieNode*> next;
  4.   TrieNode(bool flag) :isWord(flag), next(vector<TrieNode*>(26, NULL)) {}
  5. };. 1point3acres

  6. class TrieGame {
  7. private:
  8.   string _player1, _player2;
  9.   TrieNode* _root, *_cur;
  10.   bool _firstPlayerToMove;

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

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

  30. public:. check 1point3acres for more.
  31.   TrieGame(const unordered_set<string>& dict, string player1, string player2) :
  32.     _player1(player1), _player2(player2), _root(createTrie(dict)), _firstPlayerToMove(true)
  33.   {
  34.     _cur = _root;
  35.   }

  36.   void resetGame() {
  37.     _cur = _root; _firstPlayerToMove = true;
  38.   }

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

  45.   bool canWinCurrentGame() {
  46.     string name = _firstPlayerToMove ? _player1 : _player2;
  47.     bool canWin = canWinAtNode(_cur);
  48.     cout << name << " will " << (canWin ? "win" : "lose") << " the current game.\n";
  49.     return canWin;
  50.   }. From 1point 3acres bbs

  51.   bool makeRandomMove() {
  52.     if (!_cur) { cout << "Game over!\n"; return false; }
  53.     vector<TrieNode*> options;
  54.     for (auto x : _cur->next) if (x) options.push_back(x);
  55.     _cur = options[rand() % options.size()];
  56.     if (_cur->isWord) {
  57.       cout << (_firstPlayerToMove ? _player1 : _player2) << "lost the game!\n"; _cur = NULL;
  58.     }
  59.     _firstPlayerToMove = !_firstPlayerToMove;
  60.     return true;
  61.   }
  62. };
复制代码
回复

使用道具 举报

我的人缘0
 楼主| gogogogogogo 发表于 2016-10-29 07:29:05 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (3)
 
 
0% (0)  踩
zzgzzm 发表于 2016-10-28 20:06
第二题:请问思路是按给了一个实时不断出现的string stream,然后要不停地找出top frequently 出现的几个单 ...

其实我也不知道要怎么答。就按照平时积累瞎抡了一下。先说说应该有几个模块,比如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的数据量急剧上升,虽然奥黑出现次数比傅园慧更多,但是奥黑不是,傅园慧是。
但是我觉得这个不影响面试官想考察的能力。反正你能自圆其说应该就行了
回复

使用道具 举报

我的人缘0
 楼主| gogogogogogo 发表于 2016-10-29 07:32:34 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (3)
 
 
0% (0)  踩
nibuxing 发表于 2016-10-28 22:41
问一下楼主是直接投的nyc office吗

他家猎头找的
回复

使用道具 举报

我的人缘0
 楼主| gogogogogogo 发表于 2016-10-29 07:53:31 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (3)
 
 
0% (0)  踩
zzgzzm 发表于 2016-10-29 01:46
1. 算法。 两个人玩,交替给出一个字母。这个题很有意思。我的想法是用Trie来存字典中所有的单词,每个node ...
. 1point3acres
如果两个玩家都足够聪明,那么给定一个dictionary, 先手胜负就确定了。
用recursion 的思路是对的。但是你确定当前node 胜负的时候有些问题。
思路是,如果当前node 是单词,那么不管这个node还有没有child, canwin  at 当前node 是 false.
如果不是单词,若当前node 的所有children 所携带的canwin 都是false,那么当前node 的canwin = true.
如果任何一个child 的canwin 是true.那么当前node 是false.

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

使用道具 举报

我的人缘0
zzgzzm 发表于 2016-10-29 08:46:39 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  98% (68)
 
 
1% (1)  踩
gogogogogogo 发表于 2016-10-29 07:29
其实我也不知道要怎么答。就按照平时积累瞎抡了一下。先说说应该有几个模块,比如topic 提取模块,这个我 ...
. From 1point 3acres bbs
很有道理,看来是否trending是和frequency的变化率有关的,不一定和绝对的frequency直接挂钩。
看了LZ的分析获益匪浅。不知LZ的背景是否和distributed system直接相关?我也是在职,但专业和背景都不是这方面的,而在职的又比较可能问到这些,所以自己脑补啊。。。
回复

使用道具 举报

我的人缘0
zzgzzm 发表于 2016-10-29 10:20:00 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  98% (68)
 
 
1% (1)  踩
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。
回复

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法 - 不要多加空格: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|小黑屋|一亩三分地留学网

GMT+8, 2018-12-10 03:15

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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