周末读物之聊聊三观

一亩三分地论坛

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

最近看过此主题的会员

坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
前Google华人高管创立
面试offer一键直通
Leap.ai助你进入热门独角兽
查看: 2292|回复: 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月面的。. more info on 1point3acres

有两道题比较值得分享:
1. 算法。 一个游戏,两个人玩,交替给出一个字母,这个字母与前面所有的字母要是一个单词的前缀,最先拼出一个单词的那人输。
例如: 玩家1 先出一个字母 z, 玩家2 可以接着出字母 o, 但是不能出字母 b, 因为应该没有一个单词的前缀是zb, 然后玩家1 接着 zo 出字母,如果玩家1 出了字母 o,那么玩家1就输了。 因为zoo 是一个单词。但是玩家1可以出 n, 这时候玩家2 只能出字母 e, 那么玩家2就输了,因为zone 是个单词。
  写程序实现这个游戏。

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

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

本帖被以下淘专辑推荐:

我的人缘0
zzgzzm 发表于 2016-10-28 20:06:08 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  98% (63)
 
 
1% (1)  踩
第二题:请问思路是按给了一个实时不断出现的string stream,然后要不停地找出top frequently 出现的几个单词吗?我假设top frequent words 就算是被提到最popular 的trending topics.
回复

使用道具 举报

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

使用道具 举报

我的人缘0
zzgzzm 发表于 2016-10-29 01:46:18 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  98% (63)
 
 
1% (1)  踩
1. 算法。 两个人玩,交替给出一个字母。这个题很有意思。我的想法是用Trie来存字典中所有的单词,每个node用一个bool isWord来表示当前的node是否表示一个单词,若字典中一个单词已经是另一个单词的prefix,那么长单词就根本无需加入到Trie中了,因为这个游戏不可能进行到那一步。
请问这个题面试官有没有问先走的人有没有必胜的策略呢(这个是我认为比较non-trivial的问题)?我用recursion写了一个canWinNewGame的方法,就是先遍历当前所有的选择,然后看对手有没有必败的结果,若有那么第一人有必胜策略,否则没有必胜策略。当第一人有必胜策略时,因为第二人(自然没有必胜策略)的走法可以随机,所以我不好打印所谓的必胜策略路径。
想请问一下面试官对这个游戏的设计有哪些要求和条件呢?. 1point 3acres 论坛
  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];
    . 1point 3acres 论坛
  20.       }.本文原创自1point3acres论坛
  21.       cur->isWord = true;
  22.     }. Waral 博客有更多文章,
  23.     return r;
  24.   }

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

  30. public:
  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. . 1point 3acres 论坛
  40.   bool canWinNewGame() {
  41.     string name = _firstPlayerToMove ? _player1 : _player2;. 1point 3acres 论坛
  42.     bool canWin = canWinAtNode(_root); . more info on 1point3acres
  43.     cout << name << " will " << (canWin ? "win" : "lose") << " the new game.\n";
  44.     return canWin;
  45.   }

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

  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);. Waral 博客有更多文章,
  56.     _cur = options[rand() % options.size()];. Waral 博客有更多文章,
  57.     if (_cur->isWord) {
  58.       cout << (_firstPlayerToMove ? _player1 : _player2) << "lost the game!\n"; _cur = NULL;
  59.     }.留学论坛-一亩-三分地
  60.     _firstPlayerToMove = !_firstPlayerToMove;
  61.     return true;
  62.   }
  63. };
复制代码
回复

使用道具 举报

我的人缘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的数据量急剧上升,虽然奥黑出现次数比傅园慧更多,但是奥黑不是,傅园慧是。
但是我觉得这个不影响面试官想考察的能力。反正你能自圆其说应该就行了

21.000+ students read the Road to learn React. The course weaves all the opinionated roadmaps into one roadmap to master React. It gives you all the fundamentals in React. You will build a Hacker News App along the way.

回复

使用道具 举报

我的人缘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 ...

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

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

使用道具 举报

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

With React+D3v4 you'll learn the basics of building fast data visualization components in about an hour.

回复

使用道具 举报

我的人缘0
zzgzzm 发表于 2016-10-29 10:20:00 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  98% (63)
 
 
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-9-22 14:55

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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