谈谈使用过的几款咖啡机

一亩三分地论坛

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

最近看过此主题的会员

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

GoogleNYC跪经

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

2016(7-9月) 码农类General 本科 全职@Google - Other - Onsite  | Fail | 在职跳槽

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

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

x
上周一Google NYC面的,今天得知没有过HC。


第一轮: Print BST Kth level alternatively
比如  5 ,k = 2的话, 打印结果1 8 3 6
    /  \
   2    7
  / \  / \. From 1point 3acres bbs
  1 3 6  8
比如  5 ,k = 2的话, 打印结果3 8 6
    /  \. From 1point 3acres bbs
   2    7
    \  / \
    3 6  8
这道题虽然说是BST,但跟BST没啥关系。
一开始我没有很好的思路,然后面试官提示DFS/BFS,我就想到BFS+deque的做法:

  1. void printBSTKthLevelAlt(TreeNode *root, int k) {
  2.   if (root == nullptr || k < 0) {
  3.     return;-google 1point3acres
  4.   }
  5.   deque<TreeNode*> q;
  6.   int level = 0;
  7.   q.push_back(root);
  8.   while(!q.empty()) {. Waral 博客有更多文章,
  9.     if (level == k) {
  10.       printLevel(q);
  11.       return;
  12.     }
  13.     auto ls = q.size();.留学论坛-一亩-三分地
  14.     for(auto i = 0; i < ls; ++i) {
  15.       auto node = q.front();
  16.       q.pop_front();
  17.       if (q->left != nullptr) {
  18.         q.push_back(q->left);
  19.       }
  20.       if (q->right != nullptr) { 来源一亩.三分地论坛.
  21.         q.push_back(q->right); 来源一亩.三分地论坛.
  22.       }
  23.     }
  24.     ++k;. 一亩-三分-地,独家发布
  25.   }
  26. }

  27. void printLevel(const deque<TreeNode*>& q) {. 1point3acres
  28.   bool left = true;.本文原创自1point3acres论坛
  29.   while (!q.empty()) {
  30.     TreeNode* node;
  31.     if (left) {
  32.       node = q.front();. 留学申请论坛-一亩三分地
  33.       q.pop_front();
  34.     }
  35.     else {
  36.       node = q.back();. from: 1point3acres
  37.       q.pop_back();
  38.     }
  39.     cout << node->val << ' ';
  40.     left != left;
  41.   }
  42.   cout << endl;
  43. }
复制代码
然后面试官问我time&space complexity是什么,我答道O(n), O(2^k)。
然后他说怎么可以在保持time complexity的同时优化space。我就开始纠结了。
他提示说用DFS,我比划了半天也没想出来。然后时间快到的时候,他告诉了我他的思路:
维护两个stack,一个stack先push right child,另一个先push left child
比如我们有      a1                        这棵树,我们想打印k=3这层,
                 /            \
        a2             a3
          /    \        /      \
     a4    a5      a6      a7
    / \   /  \   /   \    /  \
   a8 a9 a10 a11 a12 a13 a14 a15

k = 1
s1: a1/a3/a2. 1point3acres
s2: a1/a2/a3
k = 2-google 1point3acres
s1: a1/a3/a2/a5/a4
s2: a1/a2/a3/a6/a7
k = 3
s1: a1/a3/a2/a5/a4/a9/a8
s2: a1/a2/a3/a6/a7/a14/a15
print: a8 a15 a9 a14
k = 2
s1: a1/a3/a2/a5
s2: a1/a2/a3/a6
k = 3
s1: a1/a3/a2/a5/a11/a10.本文原创自1point3acres论坛
s2: a1/a2/a3/a6/a12/a13
print: a10 a13 a11 a12
finish
这个思路确实比我的巧妙,但先不说这个思路写作代码会很繁琐,我就没明白这样怎么更节省空间了。. 1point3acres
因为使用了两个stack,对空间的占用应该是半斤八两的。而且在
k = 3
s1: a1/a3/a2/a5/a4/a9/a8
s2: a1/a2/a3/a6/a7/a14/a15
这个时候,至少存了10个节点,如果用BFS的做法只会存8个节点。

第二轮: Merge Two Sorted Array. Waral 博客有更多文章,
一个白人大叔+亚洲shadow。
因为第一轮多耽误了些时间,大叔就问了一个简单的问题。然后跟我一直聊天。

第三轮: LeetCode No.42 Trapping Rain Water
当时突然忘了Two Pointers的做法,用的stack的做法。代码写得不够简洁。感觉面试官随便抽了一道题来的,我阐述完stack的做法后,他说挺好的,也没有提示说有没有更简洁的做法就让我写代码了。. 1point3acres

第四轮:
实现一个class支持三个API:
peer A, B-google 1point3acres
manager A, B
isManager A, B

比如. From 1point 3acres bbs
peer Tim, Bill. 牛人云集,一亩三分地
peer Bill, Mike. From 1point 3acres bbs
manager Lucy, Tim-google 1point3acres
isManager Lucy, Tim -> True
isManager Lucy, Mike -> True
manager Amy, Lucy
isManager Amy, Bill -> True

具体的来说,如果给两个人添加peer关系,他们就成为一个peer group。
如果其中一个人已经在某个peer group,另一个人没有peer group,就把后者添加到前者的peer group。
每个peer group都只有一个manager。
所以不会出现
peer Tim, Bill
manager Lucy, Tim
manager Amy, Bill
这种情况
但是, 如果两个人已经在不同的peer groups,这种情况call peer API会返回错误。
manager Lucy, Tim
manager Amy, Bill
peer Tim, Bill -> error
每个manager可以有自己的peers以及manager。. 1point 3acres 论坛
每个manager的manager也是其下属的manager。
我觉得可以用类似union-find的思路来做,当时的我给出的代码如下

  1. class ManagerSystem() {
  2. public:. 围观我们@1point 3 acres
  3.   bool peer(string p1, string p2) {
  4.     auto it1 = p_to_m_.find(p1);
  5.     auto it2 = p_to_m_.find(p2);
  6.     //if both peers show up first time, assign a dummy manager to them
  7.     if (it1 == p_to_m_.end() && it2 == p_to_m_.end()) {
  8.       employee* dummy_m = new employee();
  9.       p_to_m_[p1] = dummy_m;. 一亩-三分-地,独家发布
  10.       p_to_m_[p2] = dummy_m;
  11.       m_to_p_[dummy_m].push_back(p1);
  12.       m_to_p_[dummy_m].push_back(p2);
  13.       return true;
  14.     }
  15.     if (it1 == p_to_m_.end()) {
    . 1point3acres
  16.       auto m = p_to_m_[p1];
  17.       p_to_m_[p2] = m;.留学论坛-一亩-三分地
  18.       m_to_p_[m].push_back(p1);. Waral 博客有更多文章,
  19.       return true;
  20.     }
  21.     if (it2 == p_to_m_.end()) {. 留学申请论坛-一亩三分地
  22.       auto m = p_to_m_[p2];
  23.       p_to_m_[p1] = m;
  24.       m_to_p_[m].push_back(p2);
  25.       return true;. from: 1point3acres
  26.     }
  27.     //if both peers showed up before and have dummy managers, merge their peer groups
  28.     if (it1.second->name == "" && it2.second->name == "") {
  29.       auto m1 = it1.second;
  30.       auto m2 = it2.second;
  31.       for (auto& p : m_to_p_[m2]) {
  32.         p_to_m_[p] = m1;
  33.         m_to_p_[m1].push_back(p);
  34.       }
  35.       m_to_p_.erase(it2);.1point3acres网
  36.       delete m2;
  37.     }
  38.     //if both peers showed up before and p1 has dummy managers, merge their peer groups
  39.     ...
  40.     //if both peers showed up before and p2 has dummy managers, merge their peer groups
  41.     ...
  42.     //if both peers showed up before and have different real managers, return false
  43.     ....本文原创自1point3acres论坛
  44.   }

  45.   void manager(string m, string p) {
  46.     ...
  47.   }

  48.   bool isManager(string m, string p) {
  49.     auto it = p_to_m_.find(p);
  50.       while (it != p_to_m_.end()) {
  51.         if (it.second->name == m) {
  52.           return true;
  53.         }
  54.         it = p_to_m_.find(it.second->name);
  55.       }
  56.     return false;
  57.   }
  58. private:
  59.   struct employee {
  60.     string name = "";. From 1point 3acres bbs
  61.   }
  62.   unordered_map<string, employee*> p_to_m_;
  63.   unordered_map<employee*, vector<string>> m_to_p_;. 留学申请论坛-一亩三分地
  64. }. 1point 3acres 论坛
复制代码
这轮的问题属于比较开放性的,我觉得思路不难,但是做起来比较繁琐(或者我的思路比较繁琐,有更好的思路我没有想到)。. 一亩-三分-地,独家发布
最关键的是,我一开始没有考虑好所有的情况,写到peer function一半时,发现有所遗漏,又开始打补丁。总体上我把我的思路阐明给了面试官,他也觉得没问题,但是代码并没有写完就到时间了。

第五轮:
也是一个比较开放性的问题。
先问我还记不记得vector dot product。
然后说用什么数据结构表示sparse vector好,并写一个function返回两个sparse vectors的dot product。
我就想用vector<pair<int, int>>存,记录value和其原本的index。
比如[0, 0, 0, 3, 4, 0, 0, 5]就是[(3, 2), (4, 3), (5, 7)]。
然后dot product function写了一段类似merge two sorted array的代码。 time complexity为O(s1+s2)
面试官又问如果一个vector特别大,另一个特别小咋办。-google 1point3acres
我说可以用小的在大的上做binary search。time complexity为min(s1,s2)*log(max(s1,s2))。. 1point 3acres 论坛
其实问到这里,应该很容易想到用hash table来解: unordered_map<int, int> //key:original index, value:value。time complexity为O(min(s1, s2))
我之所以没想到,一是脑子抽风,二是我觉得用hash table会破化原本index的顺序。但对于做dot product来说,我们根本不需要原本的顺序,只要知道两个vector有哪些相同的indexes就好了。. 牛人云集,一亩三分地
而且面试官也没有说要再把我们的数据结构还原成sparse vector。赖我自己没有精确的理解面试官的意图。
然后面试官又问我如果是matrix的话,怎么表示。我这个时候又特别跳的说不知道可不可以用quardTtree。面试官微笑的说,因垂丝汀,用quardTree的话,space complexity是什么?我,。。。
不过也没有过多的询问我,最后让我用别的数据结构表示。我就告诉面试官类似的思路,不过是two d array。

面试官人都挺好的,交流的也都挺愉快的。除了第二轮外,感觉都是东欧人。
没有遇到难题,第二,三轮都挺水的。第一轮解决了问题,但follow up没有跟上面试官的逻辑。
整体上感觉自己题解虽然还可以,但还是面试经历太少,自己有点儿跳,板书也有点儿慢。
再接再厉吧。


补充内容 (2016-8-5 07:06):. more info on 1point3acres
第四轮代码
if (it1 == p_to_m_.end()) 和 if (it2 == p_to_m_.end()).本文原创自1point3acres论坛
里面有bug

评分

参与人数 4大米 +33 收起 理由
chenqidi + 10 感谢分享!
muybienw + 10 感谢分享!
mnmunknown + 10 感谢分享!
oceanator + 3 感谢分享!

查看全部评分


上一篇:Two Sigma 电面
下一篇:G家第一轮电面,5分钟前的新鲜狗粮_(:3TZ)_

本帖被以下淘专辑推荐:

我的人缘0
 楼主| dg7743 发表于 2016-8-5 08:24:05 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
第四轮可以用trie来代替hash table来节省空间,面试时也忘了提了
回复 支持 反对

使用道具 举报

我的人缘0
bluepp 发表于 2016-8-5 22:53:11 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
1. 不是level order 遍历么?
回复 支持 反对

使用道具 举报

我的人缘0
yiwen_15 发表于 2016-8-6 00:01:24 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
第一题我觉得你的思路更好啊
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| dg7743 发表于 2016-8-6 00:28:45 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
bluepp 发表于 2016-8-5 22:53
1. 不是level order 遍历么?

差不多,打印顺序不同
回复 支持 反对

使用道具 举报

我的人缘0
hxtang 发表于 2016-8-6 01:36:55 | 显示全部楼层
  此人我要顶:
 
71% (5) 【我投】
  此人我要踩:
 
29% (2) 【我投】
第一题从空间complexity来说确实是他的小。stack就是前序遍历非递归算法那个stack,栈内元素照理说是不超过树的高度的k。但是BFS需要维护每层所有元素,空间上是2^k。. 围观我们@1point 3 acres
另外对DFS来说假设树是BST是有意义的。因为两个指针有可能会相互错过对方。BST可以用来判断终止条件(左指针指向的元素<右指针)。
回复 支持 反对

使用道具 举报

我的人缘0
白羽幸 发表于 2016-8-6 01:40:24 | 显示全部楼层
  此人我要顶:
 
31% (5) 【我投】
  此人我要踩:
 
69% (11) 【我投】
第一题用dfs的话space complexity只有O(k)
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| dg7743 发表于 2016-8-6 02:52:39 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
hxtang 发表于 2016-8-6 01:36
第一题从空间complexity来说确实是他的小。stack就是前序遍历非递归算法那个stack,栈内元素照理说是不超过 ...

了解了,谢谢
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

我的人缘0
pushazhiniao 发表于 2016-8-6 03:17:20 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
楼主,感觉第一题面试官的意思是不是只存到上一层啊,这样省一半空间?不过也就一半吧。

另外,想请教一下,manager peer设计那题,在A是B的经理,B是C的经理,C和D是peer的情况下,你怎样存A,B两个经理呀?Union-find不是只有一个parent节点吗?

谢谢!祝找工顺利!

补充内容 (2016-8-6 03:20):
我上面写的关于第一题错了,感觉面试官是想让你按照深度来存跑dfs,一个存左边开始的,一个存右边开始的,这样保证空间是linear to height
回复 支持 反对

使用道具 举报

我的人缘0
YoYoqiekenow 发表于 2016-8-6 03:41:13 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
第四题,直接用hash table 存储每个名字的manager 不行吗? 这样不是每个功能都能实现?
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| dg7743 发表于 2016-8-6 08:46:30 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
pushazhiniao 发表于 2016-8-6 03:17
楼主,感觉第一题面试官的意思是不是只存到上一层啊,这样省一半空间?不过也就一半吧。

另外,想请教一 ...

第一轮确实是应该双向DPS,我当时把自己绕晕了。

我的话可能有歧义歧义。不过我的意思转化为图的话:
   A
   /
  B
/ \
C  D
我之所以说是"类似union-find",是因为isManager的代码跟union-find中find parent的部分很相似。
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| dg7743 发表于 2016-8-6 08:49:24 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
YoYoqiekenow 发表于 2016-8-6 03:41
第四题,直接用hash table 存储每个名字的manager 不行吗? 这样不是每个功能都能实现?

大体上是你这个意思。因为input是乱序的,有些需要考虑的corner cases:. visit 1point3acres for more.
比如. 牛人云集,一亩三分地
peer A, B
这时候A与B在一个peer group,但他们并没有manager
peer C, D
同理,C与D在另一个peer group
manager E, A. visit 1point3acres for more.
E称为A,B的manager
回复 支持 反对

使用道具 举报

我的人缘0
csushin1992 发表于 2016-8-6 14:58:42 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
全部看完,感觉自己也经历了一遍面试,多谢楼主的面经!
回复 支持 反对

使用道具 举报

我的人缘0
YoYoqiekenow 发表于 2016-8-7 04:05:44 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
dg7743 发表于 2016-8-6 08:49
大体上是你这个意思。因为input是乱序的,有些需要考虑的corner cases:. Waral 博客有更多文章,
比如
peer A, B

哦。明白了。谢谢。
回复 支持 反对

使用道具 举报

我的人缘0
pushazhiniao 发表于 2016-8-7 05:19:52 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
dg7743 发表于 2016-8-6 08:46
第一轮确实是应该双向DPS,我当时把自己绕晕了。

我的话可能有歧义歧义。不过我的意思转化为图的话:
...
. from: 1point3acres
谢谢楼主
回复 支持 反对

使用道具 举报

我的人缘0
wzs9988 发表于 2016-8-7 12:26:14 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
谢谢LZ分享经验!请问LZ有几年工作经验了?
回复 支持 反对

使用道具 举报

我的人缘0
pushazhiniao 发表于 2016-8-8 01:13:19 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
dg7743 发表于 2016-8-6 08:46
第一轮确实是应该双向DPS,我当时把自己绕晕了。

我的话可能有歧义歧义。不过我的意思转化为图的话:
...

楼主 我想了想 觉得manager peer可能用树做更合适 用hash实现peer到manager的指针 就像每个node只有parent指针一样 isManager就像问是不是parent一样 感觉并不需要union-find   trie的结构就好(只是这里是孩子指向家长)

谢过楼主的详细面经
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| dg7743 发表于 2016-8-8 07:44:07 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
wzs9988 发表于 2016-8-7 12:26
谢谢LZ分享经验!请问LZ有几年工作经验了?

3年工作经验
回复 支持 反对

使用道具 举报

我的人缘0
sunraincyq 发表于 2016-8-8 08:31:23 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
谢谢LZ分享这么详细的面经。请问是你要求到NYC ONSITE的吗还是你本来申请的POSITION是在NYC?
回复 支持 反对

使用道具 举报

我的人缘0
hijkstra 发表于 2016-8-8 08:50:01 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
同感啊LZ,上周去面G有个别问到LC上的题,当时一边思考一边回想最佳解法,最后感觉做的比新题还差。。。
回复 支持 反对

使用道具 举报

游客
请先登录

本版积分规则

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

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

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

custom counter

GMT+8, 2018-6-24 15:30

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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