从旧金山人口变化,谈湾区买房地段选择

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
H1B/绿卡遥遥无期
又不想回国
来东南亚最大的互联网集团工作?
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 25097|回复: 153
收起左侧

热乎的G家onsite面经

  [复制链接] |试试Instant~ |关注本帖
我的人缘0
wangmengcathy 发表于 2016-5-28 06:37:51 | 显示全部楼层 |阅读模式
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】

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

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

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

x
一个小时前刚面完的onsite,一共四轮,难度比起上次LZ的G面经要简单些。。题目如下:. visit 1point3acres for more.

第一轮是个典型白人大姐,人挺nice,题目就是LC 对称数1 followup是2,不同的是需要返回所有长度1 - n的而不是只返回长度n的。

第二轮是个白人大叔,感觉像刚嗑药似的非常嗨,不过人不得不说非常的helpful。。LZ代码基本上是他一步步指引着写出来的,只是感觉他在旁边比我还激动。。。题目很麻烦是他们现在在做的maps的一个功能,大概是一个四叉树,然后让你调用他们已有的API,寻找距离最近的前几个饭店,主要是讨论,code时间很短。

第三轮是
游客,本帖隐藏的内容需要积分高于 188 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.


第四轮是一个印度大姐面的,人挺nice的必要的时候也给hint,题目就是单链表版addOne,不允许修改原链表,然后要求时间O(n),空间O(1)。. 一亩-三分-地,独家发布

今年找工作最后一站了,求人品!!
. visit 1point3acres for more.

补充内容 (2016-6-16 09:07):. 1point3acres
刚签了offer 感谢地里前辈们的各种面经,自己手写了很多面经题。。回馈地里准备面试想看看的留个邮箱吧!祝大家都能拿到心仪offer!!

评分

参与人数 5大米 +67 收起 理由
WhatsFLAG + 3 感谢分享!
encholl + 1 求人品!
神罗天征 + 10 感谢分享!
candy_shmily + 50
zjuzqh + 3 感谢分享!

查看全部评分


上一篇:Pure Storage OA 八题(Engineering Challenge 4A)
下一篇:sony playstation 面经,面过的童鞋进来赐教赐教呀!

本帖被以下淘专辑推荐:

我的人缘0
hkc593 发表于 2016-5-31 07:04:48 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
第三题是不是就是lc 174. Dungeon Game的变种?DP从dst开始做?
回复 支持 0 反对 4

使用道具 举报

我的人缘0
edcent 发表于 2016-6-15 06:12:50 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
第三题应该是图中寻找一条路径,这条路径的上面的最大值要是所有路径的最大值中最小的. 这条路径的最大值就是答案.
解决这个问题算法就是找 minimum spanning tree.
从起点开始,把能 access 的点都加到一个 heap 中.每次取 heap 头,再把取到的点周围能 access 的都加进 heap.已取到的就标记 visited.每次取 heap 头就要更新当前最大值.当遇到 dst 的时候就可以返回这个最大值了.. 留学申请论坛-一亩三分地
不知道对不对..
回复 支持 3 反对 0

使用道具 举报

我的人缘0
 楼主| wangmengcathy 发表于 2016-6-16 09:03:16 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】

two scan代码大概长这样 是O(n)
  1. public static ListNode addOne(ListNode head) {
  2.                 int pos = 0, pre = 0, index = 0;
  3.                 ListNode node = head;
  4.                 boolean hasCarry = false;
    . 一亩-三分-地,独家发布
  5.                 while(node != null) {
  6.                         if(node.val != 9) pre = 0;
  7.                         if(pre != 9 && node.val == 9) {
  8.                                 pos = index;
  9.                                 pre = 9;
  10.                         }
  11.                         if(node.next == null && node.val == 9) hasCarry = true;. visit 1point3acres for more.
  12.                         index++;
  13.                         node = node.next;
  14.                 }       
  15.                 if(!hasCarry) pos = index;
  16.                 node = head;. 一亩-三分-地,独家发布
  17.                 index = 0;
  18.                 while(node != null) {
  19.                         if(index >= pos - 1) node.val = (node.val + 1) % 10;
  20.                         index++;
  21.                         node = node.next;
  22.                 }
  23.                 if(hasCarry && pos == 0) {
  24.                         ListNode tmp = new ListNode(1);
  25.                         tmp.next = head;
  26.                         head = tmp;
  27.                 }
  28.                 return head;
  29.         }
复制代码
回复 支持 1 反对 0

使用道具 举报

我的人缘0
dg7743 发表于 2016-6-8 10:57:18 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
第三题我的思路是:
先假设这个问题是一维的,那么从src能够淹没到dst的日期取决于他俩之间最高的bar的高度。
转换为一个matrix的话,我们其实就是要找一条从src到dst的路径,这条路径上最高bar的高度越小越好。然后最短日期其实就是这条路径上最高bar的高度+1。
我们可以用BFS,然后把一般BFS其中的queue换成priority queue,在priority queue顶端的是当前未走过的高度最小的bar的index。
C++代码如下,注意我假设了src bar的高度是全局最小的,如果这个假设不成立的话,代码需要稍作修改:

  1. #include <utility>
  2. #include <vector>
  3. #include <unordered_set>
  4. #include <queue>

  5. using namespace std;

  6. class Solution {
  7. public:
  8.         int leastDays(const pair<int, int>& src, const pair<int, int>& dst, const vector<vector<int>>& matrix) const {
  9.                 const vector<pair<int, int>> directions{ { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
  10.                 int n = matrix.size();
  11.                 if (n == 0) {
  12.                         return 0;
  13.                 }
  14.                 int m = matrix.size();
  15.                 if (m == 0) {
  16.                         return 0;
  17.                 }.1point3acres网
  18.                 int highest = 0;
  19.                 auto comp = [&](const node& rhs, const node& lhs){ return rhs.value != lhs.value ? rhs.value > lhs.value : rhs.index > lhs.index; };
  20.                 unordered_set<pair<int, int>, MyHash> visited;
  21.                 priority_queue<node, vector<node>, decltype(comp)> q;

  22.                 visited.insert(src);
  23.                 q.emplace(src, matrix[src.first][src.second]);
  24.                 while (!q.empty()) {
  25.                         auto p = q.top();
  26.                         q.pop();. from: 1point3acres
  27.                         if (p.value > highest) {
  28.                                 highest = p.value;
  29.                         }
  30.                         for (const auto& d : directions) {
  31.                                 pair<int, int> next(p.index.first + d.first, p.index.second + d.second);-google 1point3acres
  32.                                 if (next.first >= 0 && next.first < n && next.second >= 0 && next.second < m && visited.find(next) == visited.end()) {
  33.                                         if (next == dst) {. From 1point 3acres bbs
  34.                                                 highest = max(highest, matrix[dst.first][dst.second]);
  35.                                                 return highest + 1;
  36.                                         }.留学论坛-一亩-三分地
  37.                                         int next_value = matrix[next.first][next.second];
  38.                                         q.emplace(next, next_value);
  39.                                         visited.insert(next);
  40.                                 }
  41.                         }
  42.                 }. 留学申请论坛-一亩三分地
  43.                 return highest + 1;
  44.         }

  45. private:
  46.         struct MyHash {
  47.                 inline std::size_t operator()(const std::pair<int, int>& p) const {
  48.                         return (hash<int>()(p.first) + hash<int>()(p.second));
  49.                 }
  50.         };

  51.         struct node {
  52.                 pair<int, int> index;
  53.                 int value;
  54.                 node(pair<int, int> idx, int val) : index(idx), value(val) {}. visit 1point3acres for more.
  55.         };
  56. };

  57. int main() {
  58.         vector<vector<int>> m1 = { { 1, 3, 2, 4 }, { 2, 7, 5, 11 }, { 12, 13, 7, 8 }, { 1, 2, 9, 4 } };
  59.         Solution s;-google 1point3acres
  60.         pair<int, int> src(0, 0);
  61.         pair<int, int> dst(3, 3);
  62.         s.leastDays(src, dst, m1);
  63.         return 0;. 1point3acres
  64. }
复制代码
回复 支持 1 反对 0

使用道具 举报

我的人缘0
 楼主| wangmengcathy 发表于 2016-5-28 13:20:15 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
wtcupup 发表于 2016-5-28 12:54
楼主第三轮的题你能说说解法吗?

这道题常规解法是O(max(day)*n^2) 当mat里有个别bar相当高的时候那么day by day增长的模式会造成大量空转 所以一个办法来避免是先把所有bar寻到一个数组并排好序 然后每当bfs到某几个bar不能再move的时候 我们从那个数组里找到某天天数大于当前bound某个bar 然后继续bfs到不能再走 这样一直到找到终点 这样总能最早到达目的地因为每次bfs完我们都是从那个数组里找到下一个最早能继续move的时间。
回复 支持 1 反对 0

使用道具 举报

我的人缘0
edcent 发表于 2016-5-28 07:28:39 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
楼主,最后一题的链表是头代表数字的最小位还是尾呢?
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| wangmengcathy 发表于 2016-5-28 07:54:07 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
尾 就是lc addone链表版
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

我的人缘0
zpx2227 发表于 2016-5-28 09:26:20 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
祝楼主 好运啦~
回复 支持 反对

使用道具 举报

我的人缘0
hidden_track 发表于 2016-5-28 11:11:26 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
第三轮是找两点间的minimum path sum吧....
回复 支持 反对

使用道具 举报

我的人缘0
一家衬衣厂 发表于 2016-5-28 11:22:54 | 显示全部楼层
  此人我要顶:
 
100% (9) 【我投】
  此人我要踩:
 
0% (0) 【我投】
祝楼主好运!加油啦
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| wangmengcathy 发表于 2016-5-28 12:45:25 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
hidden_track 发表于 2016-5-28 11:11
第三轮是找两点间的minimum path sum吧....

我理解你的想法 但这个是要返回最早天数的
回复 支持 反对

使用道具 举报

我的人缘0
wtcupup 发表于 2016-5-28 12:54:07 | 显示全部楼层
  此人我要顶:
 
12% (1) 【我投】
  此人我要踩:
 
88% (7) 【我投】
楼主第三轮的题你能说说解法吗?
回复 支持 反对

使用道具 举报

我的人缘0
jy_121 发表于 2016-5-28 14:20:17 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
第三题应该是可以dp做的吧。
回复 支持 反对

使用道具 举报

我的人缘0
say543 发表于 2016-5-28 14:31:12 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
第一轮的题目 是symmetric tree 这题吗 ? follow up 有点看不太懂? 能说说吗
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| wangmengcathy 发表于 2016-5-28 14:46:10 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
say543 发表于 2016-5-28 14:31
第一轮的题目 是symmetric tree 这题吗 ? follow up 有点看不太懂? 能说说吗

LC 247......
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| wangmengcathy 发表于 2016-5-28 14:47:30 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
jy_121 发表于 2016-5-28 14:20. 1point 3acres 论坛
第三题应该是可以dp做的吧。

讨论过dp解法 略complicated 讨论了下就回到了原解法上了
回复 支持 反对

使用道具 举报

我的人缘0
duduhaha 发表于 2016-5-28 14:54:22 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
第四题楼主怎么做的? 递归空间是O(n)啊。
回复 支持 反对

使用道具 举报

我的人缘0
menderr 发表于 2016-5-28 23:05:13 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
感觉不是很难, 祝好运~~
回复 支持 反对

使用道具 举报

我的人缘0
hidden_track 发表于 2016-5-28 23:49:04 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
wangmengcathy 发表于 2016-5-28 13:20-google 1point3acres
这道题常规解法是O(max(day)*n^2) 当mat里有个别bar相当高的时候那么day by day增长的模式会造成大量空转 ...
. 围观我们@1point 3 acres
不是给了src和destination吗?楼主的意思是如果bfs到某个点走不动了,直接跳到下一个点继续bfs吗?这样可以吗?
回复 支持 反对

使用道具 举报

我的人缘0
hidden_track 发表于 2016-5-28 23:55:44 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
我的想法是贪心+BFS,一旦有路就走到下面去,没有就选四个里面最小的那个走下去
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| wangmengcathy 发表于 2016-5-29 00:10:40 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
hidden_track 发表于 2016-5-28 23:55
我的想法是贪心+BFS,一旦有路就走到下面去,没有就选四个里面最小的那个走下去
.本文原创自1point3acres论坛
这道题关键就在于“走” 其实你仔细想想用bfs维护一个queue 你贪心好以后怎么update这个queue是个问题 FIFO肯定是不对的了
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| wangmengcathy 发表于 2016-5-29 00:21:27 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
hidden_track 发表于 2016-5-28 23:49
不是给了src和destination吗?楼主的意思是如果bfs到某个点走不动了,直接跳到下一个点继续bfs吗?这样可 ...

是的 就是从那个排好序的数字搜索下一个直接跳 其实找下一个的这个时间复杂度我感觉是降不下来的 好像面试官也这么认为..
回复 支持 反对

使用道具 举报

我的人缘0
Wingszero 发表于 2016-5-29 07:32:55 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
我昨天在MTV面的,也是最后一轮碰到烙印...
回复 支持 反对

使用道具 举报

游客
请先登录

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2018-6-18 07:46

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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