美国买被子or国内带被子?

一亩三分地论坛

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

最近看过此主题的会员

E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 8130|回复: 43
收起左侧

10.17 google onsite

[复制链接] |试试Instant~ |关注本帖
我的人缘0
fengzhiyu17 发表于 2016-10-18 13:05:10 | 显示全部楼层 |阅读模式
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (29)
 
 
0% (0)  踩

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

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

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

x
今天刚刚面完的google onsite。来源是google hr主动联系的,只做了oa,和地里总结的一样。oa做完后就onsite了。
-google 1point3acres
第一场:
白人大叔,题目是假想你手里有一份博物馆地图(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的最大长度。
第三场:. visit 1point3acres for more.
白人大叔,给定一个字符串表示文件内容,给定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。
. 围观我们@1point 3 acres
总体感觉题目不是很难,面试官都极其友好,会和你做很多交流,出错或者卡住也会提醒。
希望大家都找到心仪的工作!!!



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

评分

参与人数 3大米 +11 收起 理由
emilie1027 + 3 Move on!
alucardzhou + 5 感谢分享!
猫头鹰也是猫 + 3 感谢分享!

查看全部评分


上一篇:FB onsite 应不应该改成电面?
下一篇:Fitbit昂赛特

本帖被以下淘专辑推荐:

我的人缘0
cty 发表于 2016-10-19 09:20:10 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  100% (4)
 
 
0% (0)  踩
最后一题不用union find吧,先buildMap, 再扫list, 用set存出现过的node,再查新的node的neighbor有没有在set里, 没有就count--
回复

使用道具 举报

我的人缘0
Griffith♂Guts 发表于 2016-10-18 21:52:48 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
100% (1)   【踩】
全局: 顶  80% (24)
 
 
20% (6)  踩
zwcelesta 发表于 2016-10-18 20:00. 一亩-三分-地,独家发布
第一题怎么做one pass。感觉是如果G少,就对所有的G做一遍BFS,如何是. 少,就对所有的.做一遍bfs。

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

使用道具 举报

我的人缘0
chestnut9919 发表于 2016-10-18 13:38:06 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (20)
 
 
0% (0)  踩
楼主可以详细说说第三轮吗?offset只是一个字符吗?输入怎么判断分行? 还有follow up怎么答呀
回复

使用道具 举报

我的人缘0
zwcelesta 发表于 2016-10-18 20:00:05 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  93% (57)
 
 
6% (4)  踩
第一题怎么做one pass。感觉是如果G少,就对所有的G做一遍BFS,如何是. 少,就对所有的.做一遍bfs。
回复

使用道具 举报

我的人缘0
null_point_exc 发表于 2016-10-19 01:19:57 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (8)
 
 
0% (0)  踩
我也是。。我下个月。这里是我整理的onsite 面经。 感兴趣的可以看,也可以自己添加
https://docs.google.com/document/d/1C6sen6Wv2fcslHD1huc16e7FI_AhcpW__soOyXUWv_s/edit?usp=sharing
回复

使用道具 举报

我的人缘0
null_point_exc 发表于 2016-10-19 01:23:08 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (8)
 
 
0% (0)  踩
第一题是lc286?
回复

使用道具 举报

我的人缘0
 楼主| fengzhiyu17 发表于 2016-10-19 07:23:25 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (29)
 
 
0% (0)  踩
chestnut9919 发表于 2016-10-18 13:38
楼主可以详细说说第三轮吗?offset只是一个字符吗?输入怎么判断分行? 还有follow up怎么答呀

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

使用道具 举报

我的人缘0
cty 发表于 2016-10-19 08:19:57 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (4)
 
 
0% (0)  踩
null_point_exc 发表于 2016-10-19 01:19
我也是。。我下个月。这里是我整理的onsite 面经。 感兴趣的可以看,也可以自己添加
https://docs.google. ...

谢谢分享!第一题基本和lc286一样,同下个月面
回复

使用道具 举报

我的人缘0
zzgzzm 发表于 2016-10-19 09:19:41 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  98% (60)
 
 
1% (1)  踩
第一题: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>>();. Waral 博客有更多文章,
  4.     int n = r[0].size();. 牛人云集,一亩三分地
  5.     if (n == 0) return vector<vector<int>>();. Waral 博客有更多文章,
  6.     vector<vector<int>> dist(m, vector<int>(n, INT_MAX));
  7.     queue<pair<int,int>> q;
  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; }. more info on 1point3acres
  11.             else if (r[i][j] == '#') dist[i][j] = -1;
  12.         }
  13.     }
  14.    
  15.     while (!q.empty()) {
  16.         auto cur = q.front(); q.pop();. visit 1point3acres for more.
  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.     }
  23.     return dist;
  24. }
复制代码
回复

使用道具 举报

我的人缘0
zzgzzm 发表于 2016-10-19 10:25:23 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  98% (60)
 
 
1% (1)  踩
第四题:我觉得这道题的设定只要是single linked list就够了,而且无需额外的数据结构。用一次扫描从头到尾,碰到在给定集合里的就算联通集个数增加一个并同时扫遍下一个邻居。
  1. int numConnected(Node* head, unordered_set<Node*> s) {.留学论坛-一亩-三分地
  2.     int res = 0; Node* cur = head;
  3.     while (cur) {
  4.         if (s.count(cur)) {.1point3acres网
  5.             res++;
  6.             while (cur && s.count(cur)) cur = cur->next; 来源一亩.三分地论坛.
  7.         } else cur = cur->next;. 一亩-三分-地,独家发布
  8.     }-google 1point3acres
  9.     return res; 来源一亩.三分地论坛.
  10. }
复制代码

补充内容 (2016-10-19 11:43):.留学论坛-一亩-三分地
请忽略此代码。题目是只给出unordered_set<Node*> s这一个参数,那么double linked list的确就是必须的。更新代码在14栊。
回复

使用道具 举报

我的人缘0
 楼主| fengzhiyu17 发表于 2016-10-19 10:45:37 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (29)
 
 
0% (0)  踩
zzgzzm 发表于 2016-10-19 10:25. 1point3acres
第四题:我觉得这道题的设定只要是single linked list就够了,而且无需额外的数据结构。用一次扫描从头到尾 ...

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

使用道具 举报

我的人缘0
zzgzzm 发表于 2016-10-19 11:12:00 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  98% (60)
 
 
1% (1)  踩
第三题:楼主的先扫描整个文件再用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 3acres 论坛
  1. class FileReader {
  2.   private:
  3.   string _file;
  4.   int _maxOffset;
  5.   unordered_map<int, int> _cachedLineNumber;.1point3acres网
  6.   
  7.   public:
  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);. Waral 博客有更多文章,
  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) {
  17.           _cachedLineNumber[i] = i>0? _cachedLineNumber[i-1] : 0;
    .1point3acres网
  18.           if (s[i] == '\n') _cachedLineNumber[i]++;
  19.       }
  20.       _maxOffset = offset;
  21.       return _cachedLineNumber[offset];.1point3acres网
  22.   }
  23. };
复制代码
. 围观我们@1point 3 acres
补充内容 (2016-10-19 11:49):-google 1point3acres
更正:楼主的时间复杂度为O(log(total line number)),空间复杂度为O(total line number)
回复

使用道具 举报

我的人缘0
zzgzzm 发表于 2016-10-19 11:37:54 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  98% (60)
 
 
1% (1)  踩
fengzhiyu17 发表于 2016-10-19 10:45-google 1point3acres
没太看明白你的代码。。
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()) 是等效的。
. 一亩-三分-地,独家发布
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;. visit 1point3acres for more.
  10.         while (s.count(cur->prev)) { // delete prev connected nodes from given set
  11.             s.erase(cur->prev); cur = cur->prev;
  12.         }. from: 1point3acres
  13.         s.erase(x); 来源一亩.三分地论坛.
  14.     }
  15.     return res;
  16. }
复制代码
回复

使用道具 举报

我的人缘0
 楼主| fengzhiyu17 发表于 2016-10-19 11:50:07 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (29)
 
 
0% (0)  踩
zzgzzm 发表于 2016-10-19 11:37. more info on 1point3acres
1. C++ STL container提供的count(T val)是数container中元素为val的个数有多少,对于unordered_set::cou ...

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

使用道具 举报

我的人缘0
zzgzzm 发表于 2016-10-19 11:55:24 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  98% (60)
 
 
1% (1)  踩
第二题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;.本文原创自1point3acres论坛
  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--;
  11.             }
  12.         }
  13.         return res;
  14.     }
复制代码
回复

使用道具 举报

我的人缘0
 楼主| fengzhiyu17 发表于 2016-10-19 12:00:26 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (29)
 
 
0% (0)  踩
zzgzzm 发表于 2016-10-19 09:19
第一题: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是边的数量。
回复

使用道具 举报

我的人缘0
zzgzzm 发表于 2016-10-19 12:08:09 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  98% (60)
 
 
1% (1)  踩
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).
如果在明确一些的话可以用一个辅助的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]
  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;. 1point3acres
  9.         while (s.count(cur->next)) {
  10.             visited[cur->next] = true; cur = cur->next;
  11.         }
  12.         cur = x;. visit 1point3acres for more.
  13.         while (s.count(cur->prev)) {
  14.             visited[cur->prev] = true; cur = cur->prev;
  15.         }
  16.         visited[x] = true;
  17.     }
  18.     return res;.1point3acres网
  19. }
复制代码
来源一亩.三分地论坛.
补充内容 (2016-10-19 12:10):
我以为可以在[code][/code]环境下再加黑体, 结果“”本省打印出来了。请忽略line 03-04的
回复

使用道具 举报

我的人缘0
zzgzzm 发表于 2016-10-19 12:54:52 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  98% (60)
 
 
1% (1)  踩
null_point_exc 发表于 2016-10-19 01:19
我也是。。我下个月。这里是我整理的onsite 面经。 感兴趣的可以看,也可以自己添加
https://docs.google. ...

非常感谢整理!
回复

使用道具 举报

我的人缘0
zzgzzm 发表于 2016-10-19 13:07:23 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  98% (60)
 
 
1% (1)  踩
fengzhiyu17 发表于 2016-10-19 12:00
这个方法其实和从每一个guard开始进行一遍dfs然后每次更新count没有本质区别。每个点还是会访问多次,时 ...

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

使用道具 举报

游客
请先登录

本版积分规则

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

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

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

custom counter

GMT+8, 2018-7-21 23:50

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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