一亩三分地论坛

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

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

谷歌10月onsite

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

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

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

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

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

本帖被以下淘专辑推荐:

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

使用道具 举报

 楼主| evasuka 发表于 2016-11-19 13:00:42 | 显示全部楼层
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
麻烦问一下楼主, 那迷宫可不可以详细说一下

迷宫那题是面经题, 就是给一个球,一个起点,一个终点, 有四种操作,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. more info on 1point3acres.com
不一样的地方就是球要走到墙才会停, 其他都一样

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

使用道具 举报

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
  2. vector<string> res; // result to store all phone words
  3. map<int, set<char>> i2chars; // given map from digit to chars
  4. .1point3acres缃
  5. void dfs(PN* x, unordered_map<DN*, string>& toStr) {
  6.   // add only dictionary words to result represented by current phone number   
  7.   for (auto d2s : toStr)
  8.     if (x->isPhoneNumber && d2s.first->isWord) res.push_back(d2s.second);  
  9.   // get next phone numbers and represented strings
  10.   for (int i = 0; i <= 9; ++i) {
  11.     if (!i2chars.count(i) || !x->next[i]) continue;
  12.     unordered_map<DN*, string> tmp;   
  13.     for (auto d2s : toStr) . more info on 1point3acres.com
  14.       for (char c : i2chars[i])
  15.         if (auto dn = d2s.first->next[c-'a']) tmp[dn] = d2s.second + c;
  16.     dfs(x->next[i], tmp);
  17.   }.鐣欏璁哄潧-涓浜-涓夊垎鍦
  18.   toStr.clear();
  19. }
  20. . 鍥磋鎴戜滑@1point 3 acres
  21. vector<string> getAllWords(vector<string>& phoneNumbers, set<string>& dict) {
  22.   PN* proot;// = createPhoneTrie(phoneNumbers); // assume Trie is built
  23.   DN* nroot;// = createDictTrie(dict);
  24.   unordered_map<DN*, string> toStr = {{nroot, ""}}; dfs(proot, toStr);
  25.   return res;
  26. }
复制代码

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
LZ能详细说下第二轮的题目么?什么叫“可能在字典里的单词”?

我不是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中。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 18:59

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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