一亩三分地论坛

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

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

10.17 google onsite

[复制链接] |试试Instant~ |关注本帖
fengzhiyu17 发表于 2016-10-18 13:05:10 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@Google - Other - Onsite |Otherfresh grad应届毕业生

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

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

x
今天刚刚面完的google onsite。来源是google hr主动联系的,只做了oa,和地里总结的一样。oa做完后就onsite了。

第一场:. From 1point 3acres bbs
白人大叔,题目是假想你手里有一份博物馆地图(square matrix of char),G代表guard #代表locked room,. 代表empty room。 计算每一个空房间,最近的guard 到他需要多久(移动一格消耗一个单位时间,只能横向竖向移动,locked room是打不开的)。try to do it in one pass。
第二场:
印度小哥,给定一个只包含小写英文字母的字符串S和一个整数N,请返回这个字符串S中,所有只包含不超过N个不同字符的substring的最大长度。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
第三场:
白人大叔,给定一个字符串表示文件内容,给定offset。返回该offset指示的字符所在行行号。follow up: 假设这个查询行号的函数会被调用多次。如何优化?(每次查询的都是同一个文件内容
第四场:
华人小哥,假设有一个double linked list A<->B<->C<->D<->E。给定a list of node(unique), 返回里面connected component 的数量比如针对这个list,给定[A,C,B,E] 返回2.  ACB 是一个connected component, E 单独是一个。我的解法是union find。做了一个小改动,遍历给定的list的时候,只考虑目前已经见过的node。比如对于[a,c,b,e] 但遍历到C的时候,尽管c与b,d相连,但是不做记录(因为bd尚未出现)。把其当作单独的一个component。

总体感觉题目不是很难,面试官都极其友好,会和你做很多交流,出错或者卡住也会提醒。
希望大家都找到心仪的工作!!!. Waral 鍗氬鏈夋洿澶氭枃绔,



补充内容 (2016-10-26 04:02):
更新下结果:跪在了HC.... anyway move on 了

评分

3

查看全部评分

本帖被以下淘专辑推荐:

Griffith♂Guts 发表于 2016-10-18 21:52:48 | 显示全部楼层
zwcelesta 发表于 2016-10-18 20:00. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
第一题怎么做one pass。感觉是如果G少,就对所有的G做一遍BFS,如何是. 少,就对所有的.做一遍bfs。

我觉得就是把所有G放进queue然后BFS就行了,距离就是深度,一个pass而且linear complexity.
回复 支持 0 反对 1

使用道具 举报

cty 发表于 2016-10-19 09:20:10 | 显示全部楼层
最后一题不用union find吧,先buildMap, 再扫list, 用set存出现过的node,再查新的node的neighbor有没有在set里, 没有就count--
回复 支持 1 反对 0

使用道具 举报

chestnut9919 发表于 2016-10-18 13:38:06 | 显示全部楼层
楼主可以详细说说第三轮吗?offset只是一个字符吗?输入怎么判断分行? 还有follow up怎么答呀
回复 支持 反对

使用道具 举报

zwcelesta 发表于 2016-10-18 20:00:05 | 显示全部楼层
第一题怎么做one pass。感觉是如果G少,就对所有的G做一遍BFS,如何是. 少,就对所有的.做一遍bfs。
回复 支持 反对

使用道具 举报

null_point_exc 发表于 2016-10-19 01:19:57 | 显示全部楼层
我也是。。我下个月。这里是我整理的onsite 面经。 感兴趣的可以看,也可以自己添加
https://docs.google.com/document/d/1C6sen6Wv2fcslHD1huc16e7FI_AhcpW__soOyXUWv_s/edit?usp=sharing
回复 支持 反对

使用道具 举报

null_point_exc 发表于 2016-10-19 01:23:08 | 显示全部楼层
第一题是lc286?
回复 支持 反对

使用道具 举报

 楼主| fengzhiyu17 发表于 2016-10-19 07:23:25 | 显示全部楼层
chestnut9919 发表于 2016-10-18 13:38
楼主可以详细说说第三轮吗?offset只是一个字符吗?输入怎么判断分行? 还有follow up怎么答呀

offset就是一个Integer,'\n'是换行符。follow up我的答法是建一个文件类,初始化的时候给定文件内容。对这个文件扫一遍,记录每一行的换行符的offset是多少,然后查询的时候binary search
回复 支持 反对

使用道具 举报

cty 发表于 2016-10-19 08:19:57 | 显示全部楼层
null_point_exc 发表于 2016-10-19 01:19. 1point 3acres 璁哄潧
我也是。。我下个月。这里是我整理的onsite 面经。 感兴趣的可以看,也可以自己添加
https://docs.google. ...
. from: 1point3acres.com/bbs
谢谢分享!第一题基本和lc286一样,同下个月面
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-10-19 09:19:41 | 显示全部楼层
第一题:Push coordinate (i, j) of each guard to a queue and do BFS to fill min distance for each empty room.
  1. vector<vector<int>> distToGuard(vector<vector<char>>& r) {
  2.     int m = r.size();
  3.     if (m == 0) return vector<vector<int>>();-google 1point3acres
  4.     int n = r[0].size();
  5.     if (n == 0) return vector<vector<int>>();
  6.     vector<vector<int>> dist(m, vector<int>(n, INT_MAX));. more info on 1point3acres.com
  7.     queue<pair<int,int>> q;
    .鏈枃鍘熷垱鑷1point3acres璁哄潧
  8.     for (int i = 0; i < m; ++i) {
  9.         for (int j = 0; j < n; ++j) {
  10.             if (r[i][j] == 'G') { q.emplace(i, j); dist[i][j] = 0; }
  11.             else if (r[i][j] == '#') dist[i][j] = -1;
  12.         }
  13.     }
  14.    
  15.     while (!q.empty()) {
  16.         auto cur = q.front(); q.pop();
  17.         int i = cur.first, j = cur.second, next = 1+dist[i][j];. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  18.         if (i > 0 && dist[i-1][j] > dist) { dist[i-1][j] = next; q.emplace(i-1,j); }
  19.         if (i < m-1 && dist[i+1][j] > dist) { dist[i+1][j] = next; q.emplace(i+1,j); }
  20.         if (j > 0 && dist[i][j-1] > dist) { dist[i][j-1] = next; q.emplace(i,j-1); }
  21.         if (j < n-1 && dist[i][j+1] > dist) { dist[i][j+1] = next; q.emplace(i,j+1); }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  22.     }. more info on 1point3acres.com
  23.     return dist;
  24. }
复制代码
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-10-19 10:25:23 | 显示全部楼层
第四题:我觉得这道题的设定只要是single linked list就够了,而且无需额外的数据结构。用一次扫描从头到尾,碰到在给定集合里的就算联通集个数增加一个并同时扫遍下一个邻居。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  1. int numConnected(Node* head, unordered_set<Node*> s) {
    . 1point 3acres 璁哄潧
  2.     int res = 0; Node* cur = head;
  3.     while (cur) {
  4.         if (s.count(cur)) {
  5.             res++;. 鍥磋鎴戜滑@1point 3 acres
  6.             while (cur && s.count(cur)) cur = cur->next;
  7.         } else cur = cur->next;
  8.     }
  9.     return res;
  10. }
复制代码
. 鍥磋鎴戜滑@1point 3 acres
补充内容 (2016-10-19 11:43):
请忽略此代码。题目是只给出unordered_set<Node*> s这一个参数,那么double linked list的确就是必须的。更新代码在14栊。
回复 支持 反对

使用道具 举报

 楼主| fengzhiyu17 发表于 2016-10-19 10:45:37 | 显示全部楼层
zzgzzm 发表于 2016-10-19 10:25
第四题:我觉得这道题的设定只要是single linked list就够了,而且无需额外的数据结构。用一次扫描从头到尾 ...

没太看明白你的代码。。
. From 1point 3acres bbs1. s.count方法是干啥的?. 1point 3acres 璁哄潧
2.为何你这个函数有两个输入? 这道题是假设存在一个double linked list L,但是这个list你是不知道。给你的a list of nodeL1仅仅是把L中的几个node拿出来组成的一个新的list,或者说a sub set of Nodes in L更加合适吧。
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-10-19 11:12:00 | 显示全部楼层
第三题:楼主的先扫描整个文件再用binary search查行号的时间和空间复杂度均为O(log(total line number))。  follow既然有“假设这个查询行号的函数会被调用多次”,我个人认为这时候就应该以优化时间复杂度为主,牺牲空间优化。所以我的做法是cache所有已经查询过的结果在class里以便以后再次查询,这样空间存储增加到O(file length), 但只要给的offset是以前查询过的范围之内(i.e., offset <= maxOffset, 有"cache hit")时间复杂度均为O(1). 只有查询不在cache范围内的结果时在计算并同时更新cache. 这个技术似乎在system scalability里有用到。. 鍥磋鎴戜滑@1point 3 acres
  1. class FileReader {
  2.   private:
  3.   string _file;
  4.   int _maxOffset;
  5.   unordered_map<int, int> _cachedLineNumber;
  6.   
  7.   public:.鏈枃鍘熷垱鑷1point3acres璁哄潧
  8.   FileReader(const string& file):_file(file),_maxOffset(-1) {}. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  9.   
  10.   int lineNumber(int offset) {
  11.       if (offset < 0 || _file.empty()) return -1;
  12.       offset = min(offset, _file.length()-1);.鏈枃鍘熷垱鑷1point3acres璁哄潧
  13.       // get result from cache if available
  14.       if (offset <= _maxOffset) return _cachedLineNumber[offset];
  15.       // update cache
  16.       for (int i = _maxOffset+1; i <= offset; ++i) {. from: 1point3acres.com/bbs
  17.           _cachedLineNumber[i] = i>0? _cachedLineNumber[i-1] : 0;
  18.           if (s[i] == '\n') _cachedLineNumber[i]++;
  19.       }
  20.       _maxOffset = offset;
  21.       return _cachedLineNumber[offset];
  22.   }. 鍥磋鎴戜滑@1point 3 acres
  23. };
复制代码

补充内容 (2016-10-19 11:49):
更正:楼主的时间复杂度为O(log(total line number)),空间复杂度为O(total line number)
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-10-19 11:37:54 | 显示全部楼层
fengzhiyu17 发表于 2016-10-19 10:45
没太看明白你的代码。。
1. s.count方法是干啥的?
2.为何你这个函数有两个输入? 这道题是假设存在一 ...

1. C++ STL container提供的count(T val)是数container中元素为val的个数有多少,对于unordered_set::count(T val)返回值就是1(set包含元素val)或者0(set不包含元素val).这个和判断 if(s.find(val) == s.end()) 是等效的。
. 1point 3acres 璁哄潧
2. 哦我明白你的意思了,题目是只给出unordered_set<Node*> s这一个参数。那么double linked list的确就是必须的,因为这时候无法track head了。但解法应该类似,也不需要额外的数据结构。只要对于集合中每个node向前后两个方向同时搜索并及时删除找到的node就行。这个和Leetcode里“find longest consecutive subsequence”或者“number of islands”是类似的思路。
  1. int numConnected(unordered_set<Node*> s) {
  2.     int res = 0;
  3.     for (auto x:s) {
  4.         res++; // found a new connected component
  5.         Node* cur = x;
  6.         while (s.count(cur->next)) { // delete next connected nodes from given set
  7.             s.erase(cur->next); cur = cur->next;
  8.         }
  9.         cur = x;. 1point3acres.com/bbs
  10.         while (s.count(cur->prev)) { // delete prev connected nodes from given set
  11.             s.erase(cur->prev); cur = cur->prev;
  12.         }
  13.         s.erase(x);
  14.     }
  15.     return res;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  16. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| fengzhiyu17 发表于 2016-10-19 11:50:07 | 显示全部楼层
zzgzzm 发表于 2016-10-19 11:37
1. C++ STL container提供的count(T val)是数container中元素为val的个数有多少,对于unordered_set::cou ...

一个小问题,你的这个算法里面只看到res++,但是为什么没有UNION的状况?这种情况下res应该要减一的。
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-10-19 11:55:24 | 显示全部楼层
第二题Leetcode 340: 个人用two pointer + unordered_map来统计频率O(s.length)时间复杂度,O(min(s.length, k))空间复杂度。
  1. int lengthOfLongestSubstringKDistinct(string s, int k) {
  2.         int n = s.length();
  3.         int i = 0, j = 0, len = 0, res = 0;
  4.         unordered_map<char, int> freq;
  5.         while (j < n) {
  6.             freq[s[j++]]++; len++;
  7.             if (freq.size() <= k) res = max(res, len);
  8.             while (freq.size() > k) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  9.                 freq[s[i]]--; if (freq[s[i]] == 0) freq.erase(s[i]);
  10.                 i++; len--;. Waral 鍗氬鏈夋洿澶氭枃绔,
  11.             } . 1point 3acres 璁哄潧
  12.         }
  13.         return res;. 1point 3acres 璁哄潧
  14.     }
复制代码
回复 支持 反对

使用道具 举报

 楼主| fengzhiyu17 发表于 2016-10-19 12:00:26 | 显示全部楼层
zzgzzm 发表于 2016-10-19 09:19. 1point 3acres 璁哄潧
第一题:Push coordinate (i, j) of each guard to a queue and do BFS to fill min distance for each emp ...

这个方法其实和从每一个guard开始进行一遍dfs然后每次更新count没有本质区别。每个点还是会访问多次,时间复杂度是O(k*n)k是guard的数量,n是node的数量。我给的方法大致和这个一致,但是同时我还维持了一个边集合hashmap<node,node> edges,这个hashmap里面只存了所有的guard 到empty room以及empty room到empty room的边。每次bfs从q里面拿出一个点n_i的时候,就从edges里面取出所有与这个点相连的边,更新他们连接的点的count,然后删除这些边。然后把这些点放入q。重复这一过程直到q为空。这样可以保证每条边只被访问一次。时间复杂度是O(e),E是边的数量。
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-10-19 12:08:09 | 显示全部楼层
fengzhiyu17 发表于 2016-10-19 11:50
一个小问题,你的这个算法里面只看到res++,但是为什么没有UNION的状况?这种情况下res应该要减一的。

这个算法不是用union-find的。每次找到新的connected component并前后遍历时都将node从set s中直接删除了,所以下一次再进入loop "for (auto x:s)"是一定是一个新的和之前不连起来的connected component. 这也证明每个node访问没有重复的,时间O(N). . visit 1point3acres.com for more.
如果在明确一些的话可以用一个辅助的unordered_set<Node*, bool>来记录每个node是否访问过:(这个和“number of island”中把访问过的陆地“1”变为“0”是一个意思)
  1. int numConnected(unordered_set<Node*> s) {
  2.     int res = 0;
  3.     [b]unordered_set<Node*, bool> visited;[/b].1point3acres缃
  4.    [b] for (auto x:s) visited[x] = false;[/b]. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  5.     for (auto x:s) {
  6.         if (visited[x]) continue;
  7.         res++;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  8.         Node* cur = x;
  9.         while (s.count(cur->next)) {. 鍥磋鎴戜滑@1point 3 acres
  10.             visited[cur->next] = true; cur = cur->next;
  11.         }
  12.         cur = x;
  13.         while (s.count(cur->prev)) {
  14.             visited[cur->prev] = true; cur = cur->prev;
  15.         }
  16.         visited[x] = true;
  17.     }
  18.     return res;
  19. }
复制代码

补充内容 (2016-10-19 12:10):
我以为可以在[code][/code]环境下再加黑体, 结果“”本省打印出来了。请忽略line 03-04的
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-10-19 12:54:52 | 显示全部楼层
null_point_exc 发表于 2016-10-19 01:19
我也是。。我下个月。这里是我整理的onsite 面经。 感兴趣的可以看,也可以自己添加
https://docs.google. ...
. 鍥磋鎴戜滑@1point 3 acres
非常感谢整理!
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-10-19 13:07:23 | 显示全部楼层
fengzhiyu17 发表于 2016-10-19 12:00. Waral 鍗氬鏈夋洿澶氭枃绔,
这个方法其实和从每一个guard开始进行一遍dfs然后每次更新count没有本质区别。每个点还是会访问多次,时 ...

有道理,你的想法更适用于更广泛的图G(V,E).
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 21:51

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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