推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 6971|回复: 43
收起左侧

谷歌10月onsite

[复制链接] |试试Instant~ |关注本帖
evasuka 发表于 2016-11-19 03:21:18 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 全职@Google - 内推 - Onsite |Pass在职跳槽

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

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

x
分享一个10月的google onsite:
第一轮: lc 247, 248.
第二轮 : 给一串电话号码, 一个number 和 字母的mapping,Map<Integer, List<Character>> map, 和一个dictionary, Set<String> dict. 输出所有可能的在dict里的英文单词。
第三轮: 1. word search.  2. open ended question, mosaic pictures, 怎么用一些小图片拼成一个mosaic pictures。
第四轮: sliding maze。 一个迷宫,一个球, 球一直走直到遇到障碍物才能停下。 问这个迷宫是不是solvable, followup 找最短path。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
第五轮: 给一个数据结构. from: 1point3acres.com/bbs
class Purchase{
int id;
int val;
Purchase previous;
}. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
每个节点指向自己的parent
输入是List<Purchase>, 打印每个节点的及其子节点的value。
Example:
              Node1, 1
               /           \      
      Node2, 2      Node3, 4
          /. 1point 3acres 璁哄潧
Node4, 1           . more info on 1point3acres.com
输出
node1, 8  Node 2, 3  Node 3,4 Node4,1
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

本帖被以下淘专辑推荐:

sadfcbasy 发表于 2016-11-19 12:57:30 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
话说楼主跳槽的时候google的hr还要过你当初毕业时候的成绩单么?或者reference?
回复 支持 反对

使用道具 举报

 楼主| evasuka 发表于 2016-11-19 13:00:42 | 显示全部楼层
关注一亩三分地微博:
Warald
sadfcbasy 发表于 2016-11-19 12:57
话说楼主跳槽的时候google的hr还要过你当初毕业时候的成绩单么?或者reference?

没有啊。就问我要了google内部认识的人
回复 支持 反对

使用道具 举报

zyoppy008 发表于 2016-11-21 17:16:26 | 显示全部楼层
最后一问咋样o(n)? 从下往上是nlogn吧 难度用hash表把父亲节点转换成children 节点 这样可以o(n) 肯定有别的o(n)方法 求教
回复 支持 反对

使用道具 举报

 楼主| evasuka 发表于 2016-11-22 02:13:54 | 显示全部楼层
zyoppy008 发表于 2016-11-21 17:16
最后一问咋样o(n)? 从下往上是nlogn吧 难度用hash表把父亲节点转换成children 节点 这样可以o(n) 肯定有别 ...

可以先生成一个purchase 和 in-degree 的map, 然后把leave 节点放入一个queue里,然后更新这个map, 找到新的leave
回复 支持 反对

使用道具 举报

zhan1612 发表于 2016-11-22 05:06:36 | 显示全部楼层
麻烦问一下楼主, 那迷宫可不可以详细说一下
回复 支持 反对

使用道具 举报

 楼主| evasuka 发表于 2016-11-22 05:19:45 | 显示全部楼层
zhan1612 发表于 2016-11-22 05:06. 鍥磋鎴戜滑@1point 3 acres
麻烦问一下楼主, 那迷宫可不可以详细说一下

迷宫那题是面经题, 就是给一个球,一个起点,一个终点, 有四种操作,up/down/left/right, 但球会一直走知道碰到一个wall。 然后找从起点到终点的最短路径。要自己先定义maze,我是用一个三维数组来表示迷宫
回复 支持 反对

使用道具 举报

zyoppy008 发表于 2016-11-22 05:50:52 | 显示全部楼层
evasuka 发表于 2016-11-22 02:13.鐣欏璁哄潧-涓浜-涓夊垎鍦
可以先生成一个purchase 和 in-degree 的map, 然后把leave 节点放入一个queue里,然后更新这个map, 找 ...

Good 从下往上bfs 确实好 只想到dfs了
回复 支持 反对

使用道具 举报

harry0302 发表于 2016-11-22 08:17:26 | 显示全部楼层
请问楼主,迷宫那道题为什么要用三维数组来表示迷宫?二维不够么?
回复 支持 反对

使用道具 举报

 楼主| evasuka 发表于 2016-11-22 08:49:10 | 显示全部楼层
harry0302 发表于 2016-11-22 08:17
请问楼主,迷宫那道题为什么要用三维数组来表示迷宫?二维不够么?

因为一个cell有四个边, 需要用三维数组来表示哪一条边有墙。。。
回复 支持 反对

使用道具 举报

harry0302 发表于 2016-11-22 12:01:35 | 显示全部楼层
哦哦,我原先想的是整个cell要么是墙要么是路
回复 支持 反对

使用道具 举报

zyoppy008 发表于 2016-11-22 15:32:44 | 显示全部楼层
evasuka 发表于 2016-11-22 08:49
因为一个cell有四个边, 需要用三维数组来表示哪一条边有墙。。。

不会吧 难度不是一块cell一个block?
回复 支持 反对

使用道具 举报

chengbaokun 发表于 2016-11-23 23:51:17 | 显示全部楼层
LZ 请问下迷宫这个题 假如已经表示了墙的限制条件 (我想可以用一个四位的二进制数表示嘛?每个位置都有一个数,表示四个方向能不能走),球走迷宫,跟正常的BFS走迷宫有啥区别吗?还是就是一样的……
回复 支持 反对

使用道具 举报

 楼主| evasuka 发表于 2016-11-24 04:10:22 | 显示全部楼层
chengbaokun 发表于 2016-11-23 23:51
LZ 请问下迷宫这个题 假如已经表示了墙的限制条件 (我想可以用一个四位的二进制数表示嘛?每个位置都有一 ...
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
不一样的地方就是球要走到墙才会停, 其他都一样
回复 支持 反对

使用道具 举报

chengbaokun 发表于 2016-11-24 04:38:12 | 显示全部楼层
evasuka 发表于 2016-11-24 04:10
不一样的地方就是球要走到墙才会停, 其他都一样

哦哦 碰到墙然后会退回来是吗
回复 支持 反对

使用道具 举报

zhan1612 发表于 2016-11-25 06:52:42 | 显示全部楼层
麻烦问一下楼主, 迷宫是不是用DFS做的。 最短路径的话, 是不是哟普好多条可以出去的路径然后, 然后遍历所有的路径?
回复 支持 反对

使用道具 举报

新宿车站 发表于 2016-11-25 09:07:58 | 显示全部楼层
LZ能详细说下第二轮的题目么?什么叫“可能在字典里的单词”?
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-11-25 12:10:15 | 显示全部楼层
第二轮 : 这里的“一串电话号码”是指多个电话号码吗?我是按最一般的假设:假设给定了一堆电话号码,而且电话号码的长度可以不同。我觉得这个题得对一堆电话号码以及字典都建立Trie来避免重复计算(对于相同的号码前缀或单词前缀),否则的话对于每个电话号码"d1d2...dk"就有n1*n2*...*nk种可能的单词,然后逐个判断是否在字典中会有很多重复prefix计算。
  1. // global variables. 鍥磋鎴戜滑@1point 3 acres
  2. vector<string> res; // result to store all phone words
  3. map<int, set<char>> i2chars; // given map from digit to chars

  4. void dfs(PN* x, unordered_map<DN*, string>& toStr) {
  5.   // add only dictionary words to result represented by current phone number   
  6.   for (auto d2s : toStr)
  7.     if (x->isPhoneNumber && d2s.first->isWord) res.push_back(d2s.second);  
    . from: 1point3acres.com/bbs
  8.   // get next phone numbers and represented strings. 1point3acres.com/bbs
  9.   for (int i = 0; i <= 9; ++i) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  10.     if (!i2chars.count(i) || !x->next[i]) continue;
  11.     unordered_map<DN*, string> tmp;    . 1point 3acres 璁哄潧
  12.     for (auto d2s : toStr) . more info on 1point3acres.com
  13.       for (char c : i2chars[i]). visit 1point3acres.com for more.
  14.         if (auto dn = d2s.first->next[c-'a']) tmp[dn] = d2s.second + c;
  15.     dfs(x->next[i], tmp);
  16.   }. visit 1point3acres.com for more.
  17.   toStr.clear();
  18. }. 鍥磋鎴戜滑@1point 3 acres

  19. vector<string> getAllWords(vector<string>& phoneNumbers, set<string>& dict) {
  20.   PN* proot;// = createPhoneTrie(phoneNumbers); // assume Trie is built
  21.   DN* nroot;// = createDictTrie(dict);
  22.   unordered_map<DN*, string> toStr = {{nroot, ""}}; dfs(proot, toStr);
  23.   return res;
  24. }
复制代码
. visit 1point3acres.com for more.
Trie node定义:
  1. struct PN { // trie node for phone number
  2.   bool isPhoneNumber; vector<PN*> next;
  3.   PN():isPhoneNumber(false),next(vector<PN*>(10)){}
  4. };
  5. struct DN { // trie node for dictionary
  6.   bool isWord; vector<DN*> next;
  7.   DN():isWord(false),next(vector<DN*>(26)){}
  8. };
复制代码
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-11-25 12:18:55 | 显示全部楼层
新宿车站 发表于 2016-11-25 09:07.鏈枃鍘熷垱鑷1point3acres璁哄潧
LZ能详细说下第二轮的题目么?什么叫“可能在字典里的单词”?
.1point3acres缃
我不是LZ. 我的理解:就是给定一些电话号码,每个电话号码都可以代表一些string,让找出所有在字典中的那些strings.
例如:digit->chars的map就按现实中的qwer键盘,给定电话号码{342, 764}和dict = {"dhc", "rft", "vvb"}. 那么答案为{"dhc"} (被342表示),而"rft", "vvb"都不能被任何给定的电话号码表示。
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-11-25 12:25:36 | 显示全部楼层
zzgzzm 发表于 2016-11-25 12:10
第二轮 : 这里的“一串电话号码”是指多个电话号码吗?我是按最一般的假设:假设给定了一堆电话号码,而且 ...

我又想了一下,我之前的Trie也不必要。可以直接将字典中每个word转化成phone number,然后直接看是不是在给定的phone number中。
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-7-27 10:41

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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