一亩三分地论坛

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

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

热乎的G家onsite面经

  [复制链接] |试试Instant~ |关注本帖
wangmengcathy 发表于 2016-5-28 06:37:51 | 显示全部楼层 |阅读模式

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

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

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

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

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

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

第三轮是reverse shadow,国人大哥面的,题目就是给你一个matrix,里面的数字代表bar的高度,现在说降雨量如果高于bar的高度水可以漫过去,降雨量0开始每天+1这样,问最早第几天水可以有一条路径从src漫到dst。这轮也是讨论optimization很久,最后用bfs写一个subproblem。.鐣欏璁哄潧-涓浜-涓夊垎鍦

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

今年找工作最后一站了,求人品!!.鏈枃鍘熷垱鑷1point3acres璁哄潧


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

评分

5

查看全部评分

本帖被以下淘专辑推荐:

hkc593 发表于 2016-5-31 07:04:48 | 显示全部楼层
第三题是不是就是lc 174. Dungeon Game的变种?DP从dst开始做?
回复 支持 0 反对 2

使用道具 举报

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

  1. #include <utility>
  2. #include <vector>
  3. #include <unordered_set>. Waral 鍗氬鏈夋洿澶氭枃绔,
  4. #include <queue>
  5. . visit 1point3acres.com for more.
  6. using namespace std;

  7. class Solution {
  8. public:
  9.         int leastDays(const pair<int, int>& src, const pair<int, int>& dst, const vector<vector<int>>& matrix) const {
  10.                 const vector<pair<int, int>> directions{ { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
  11.                 int n = matrix.size();
  12.                 if (n == 0) {. 鍥磋鎴戜滑@1point 3 acres
  13.                         return 0;
  14.                 }
  15.                 int m = matrix.size();. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  16.                 if (m == 0) {
  17.                         return 0;
  18.                 }
  19.                 int highest = 0;
  20.                 auto comp = [&](const node& rhs, const node& lhs){ return rhs.value != lhs.value ? rhs.value > lhs.value : rhs.index > lhs.index; };
  21.                 unordered_set<pair<int, int>, MyHash> visited;
  22.                 priority_queue<node, vector<node>, decltype(comp)> q;

  23.                 visited.insert(src);
  24.                 q.emplace(src, matrix[src.first][src.second]);
  25.                 while (!q.empty()) {
  26.                         auto p = q.top();.鏈枃鍘熷垱鑷1point3acres璁哄潧
  27.                         q.pop();
  28.                         if (p.value > highest) {
  29.                                 highest = p.value;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  30.                         }
  31.                         for (const auto& d : directions) {-google 1point3acres
  32.                                 pair<int, int> next(p.index.first + d.first, p.index.second + d.second);
  33.                                 if (next.first >= 0 && next.first < n && next.second >= 0 && next.second < m && visited.find(next) == visited.end()) {
  34.                                         if (next == dst) {
  35.                                                 highest = max(highest, matrix[dst.first][dst.second]);. more info on 1point3acres.com
  36.                                                 return highest + 1;
  37.                                         }
  38.                                         int next_value = matrix[next.first][next.second];
  39.                                         q.emplace(next, next_value);
  40.                                         visited.insert(next);
  41.                                 }
  42.                         }
  43.                 }. more info on 1point3acres.com
  44.                 return highest + 1;
  45.         }

  46. private:
  47.         struct MyHash {.鏈枃鍘熷垱鑷1point3acres璁哄潧
  48.                 inline std::size_t operator()(const std::pair<int, int>& p) const {. 1point 3acres 璁哄潧
  49.                         return (hash<int>()(p.first) + hash<int>()(p.second));
  50.                 }
  51.         };

  52.         struct node {
  53.                 pair<int, int> index;
  54.                 int value;
  55.                 node(pair<int, int> idx, int val) : index(idx), value(val) {}
  56.         };
  57. };

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

使用道具 举报

 楼主| wangmengcathy 发表于 2016-5-28 13:20:15 | 显示全部楼层
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

使用道具 举报

edcent 发表于 2016-5-28 07:28:39 | 显示全部楼层
楼主,最后一题的链表是头代表数字的最小位还是尾呢?
回复 支持 反对

使用道具 举报

 楼主| wangmengcathy 发表于 2016-5-28 07:54:07 | 显示全部楼层
尾 就是lc addone链表版
回复 支持 反对

使用道具 举报

zpx2227 发表于 2016-5-28 09:26:20 | 显示全部楼层
祝楼主 好运啦~
回复 支持 反对

使用道具 举报

hidden_track 发表于 2016-5-28 11:11:26 | 显示全部楼层
第三轮是找两点间的minimum path sum吧....
回复 支持 反对

使用道具 举报

一家衬衣厂 发表于 2016-5-28 11:22:54 | 显示全部楼层
祝楼主好运!加油啦
回复 支持 反对

使用道具 举报

 楼主| wangmengcathy 发表于 2016-5-28 12:45:25 | 显示全部楼层
hidden_track 发表于 2016-5-28 11:11
第三轮是找两点间的minimum path sum吧....
-google 1point3acres
我理解你的想法 但这个是要返回最早天数的
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-5-28 12:54:07 | 显示全部楼层
楼主第三轮的题你能说说解法吗?
回复 支持 反对

使用道具 举报

jy_121 发表于 2016-5-28 14:20:17 | 显示全部楼层
第三题应该是可以dp做的吧。
回复 支持 反对

使用道具 举报

say543 发表于 2016-5-28 14:31:12 | 显示全部楼层
第一轮的题目 是symmetric tree 这题吗 ? follow up 有点看不太懂? 能说说吗
回复 支持 反对

使用道具 举报

 楼主| wangmengcathy 发表于 2016-5-28 14:46:10 | 显示全部楼层
say543 发表于 2016-5-28 14:31
第一轮的题目 是symmetric tree 这题吗 ? follow up 有点看不太懂? 能说说吗

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

使用道具 举报

 楼主| wangmengcathy 发表于 2016-5-28 14:47:30 | 显示全部楼层
jy_121 发表于 2016-5-28 14:20
第三题应该是可以dp做的吧。

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

使用道具 举报

duduhaha 发表于 2016-5-28 14:54:22 | 显示全部楼层
第四题楼主怎么做的? 递归空间是O(n)啊。
回复 支持 反对

使用道具 举报

menderr 发表于 2016-5-28 23:05:13 | 显示全部楼层
感觉不是很难, 祝好运~~
回复 支持 反对

使用道具 举报

hidden_track 发表于 2016-5-28 23:49:04 | 显示全部楼层
wangmengcathy 发表于 2016-5-28 13:20
这道题常规解法是O(max(day)*n^2) 当mat里有个别bar相当高的时候那么day by day增长的模式会造成大量空转 ...

不是给了src和destination吗?楼主的意思是如果bfs到某个点走不动了,直接跳到下一个点继续bfs吗?这样可以吗?
回复 支持 反对

使用道具 举报

hidden_track 发表于 2016-5-28 23:55:44 | 显示全部楼层
我的想法是贪心+BFS,一旦有路就走到下面去,没有就选四个里面最小的那个走下去
回复 支持 反对

使用道具 举报

 楼主| wangmengcathy 发表于 2016-5-29 00:10:40 | 显示全部楼层
hidden_track 发表于 2016-5-28 23:55
我的想法是贪心+BFS,一旦有路就走到下面去,没有就选四个里面最小的那个走下去

这道题关键就在于“走” 其实你仔细想想用bfs维护一个queue 你贪心好以后怎么update这个queue是个问题 FIFO肯定是不对的了
回复 支持 反对

使用道具 举报

 楼主| wangmengcathy 发表于 2016-5-29 00:21:27 | 显示全部楼层
hidden_track 发表于 2016-5-28 23:49
不是给了src和destination吗?楼主的意思是如果bfs到某个点走不动了,直接跳到下一个点继续bfs吗?这样可 ...

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

使用道具 举报

Wingszero 发表于 2016-5-29 07:32:55 | 显示全部楼层
我昨天在MTV面的,也是最后一轮碰到烙印...
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 06:18

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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