一亩三分地论坛

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

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

GoogleNYC跪经

[复制链接] |试试Instant~ |关注本帖
dg7743 发表于 2016-8-5 07:00:46 | 显示全部楼层 |阅读模式

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

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

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

x
上周一Google NYC面的,今天得知没有过HC。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
. more info on 1point3acres.com

第一轮: Print BST Kth level alternatively
比如  5 ,k = 2的话, 打印结果1 8 3 6
.鏈枃鍘熷垱鑷1point3acres璁哄潧    /  \
   2    7
  / \  / \
  1 3 6  8
比如  5 ,k = 2的话, 打印结果3 8 6
    /  \
   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;. more info on 1point3acres.com
  4.   }
  5.   deque<TreeNode*> q;
  6.   int level = 0;
  7.   q.push_back(root);
  8.   while(!q.empty()) {
  9.     if (level == k) {
  10.       printLevel(q);
  11.       return;
  12.     }
  13.     auto ls = q.size();
  14.     for(auto i = 0; i < ls; ++i) {. from: 1point3acres.com/bbs
  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) {. more info on 1point3acres.com
  21.         q.push_back(q->right);
  22.       }
  23.     }
  24.     ++k;
  25.   }
  26. }

  27. void printLevel(const deque<TreeNode*>& q) {
  28.   bool left = true;
  29.   while (!q.empty()) {
  30.     TreeNode* node;
  31.     if (left) {
  32.       node = q.front();
  33.       q.pop_front();
  34.     }
  35.     else {. more info on 1point3acres.com
  36.       node = q.back();
  37.       q.pop_back();
  38.     }.1point3acres缃
  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. 1point3acres.com/bbs
比如我们有      a1                        这棵树,我们想打印k=3这层,
                 /            \
        a2             a3
          /    \        /      \
     a4    a5      a6      a7. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
    / \   /  \   /   \    /  \
   a8 a9 a10 a11 a12 a13 a14 a15

k = 1
s1: a1/a3/a2-google 1point3acres
s2: a1/a2/a3
k = 2
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-google 1point3acres
s2: a1/a2/a3/a6/a12/a13
print: a10 a13 a11 a12
finish.鏈枃鍘熷垱鑷1point3acres璁哄潧
这个思路确实比我的巧妙,但先不说这个思路写作代码会很繁琐,我就没明白这样怎么更节省空间了。
因为使用了两个stack,对空间的占用应该是半斤八两的。而且在
k = 3. 1point3acres.com/bbs
s1: a1/a3/a2/a5/a4/a9/a8
s2: a1/a2/a3/a6/a7/a14/a15
这个时候,至少存了10个节点,如果用BFS的做法只会存8个节点。

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

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

第四轮:. Waral 鍗氬鏈夋洿澶氭枃绔,
实现一个class支持三个API:
peer A, B
manager A, B
isManager A, B

比如
peer Tim, Bill. 1point3acres.com/bbs
peer Bill, Mike
manager Lucy, Tim
isManager Lucy, Tim -> True
isManager Lucy, Mike -> True
manager Amy, Lucy
isManager Amy, Bill -> True

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

  1. class ManagerSystem() {
  2. public:
  3.   bool peer(string p1, string p2) {. visit 1point3acres.com for more.
  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()) {
  16.       auto m = p_to_m_[p1];
  17.       p_to_m_[p2] = m;
  18.       m_to_p_[m].push_back(p1);
  19.       return true;. visit 1point3acres.com for more.
  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);. From 1point 3acres bbs
  25.       return true;
  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);
  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.     .... From 1point 3acres bbs
  42.     //if both peers showed up before and have different real managers, return false
  43.     ...
  44.   }

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

  48.   bool isManager(string m, string p) {. visit 1point3acres.com for more.
  49.     auto it = p_to_m_.find(p);
  50.       while (it != p_to_m_.end()) {
  51.         if (it.second->name == m) {. from: 1point3acres.com/bbs
  52.           return true;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  53.         }
  54.         it = p_to_m_.find(it.second->name);
  55.       }
  56.     return false;
  57.   }. more info on 1point3acres.com
  58. private:. 鍥磋鎴戜滑@1point 3 acres
  59.   struct employee {
  60.     string name = "";
  61.   }
  62.   unordered_map<string, employee*> p_to_m_;
  63.   unordered_map<employee*, vector<string>> m_to_p_;
  64. }
复制代码
这轮的问题属于比较开放性的,我觉得思路不难,但是做起来比较繁琐(或者我的思路比较繁琐,有更好的思路我没有想到)。
最关键的是,我一开始没有考虑好所有的情况,写到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特别大,另一个特别小咋办。. From 1point 3acres bbs
我说可以用小的在大的上做binary search。time complexity为min(s1,s2)*log(max(s1,s2))。
其实问到这里,应该很容易想到用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没有跟上面试官的逻辑。
整体上感觉自己题解虽然还可以,但还是面试经历太少,自己有点儿跳,板书也有点儿慢。
再接再厉吧。. 1point3acres.com/bbs


补充内容 (2016-8-5 07:06):
第四轮代码
if (it1 == p_to_m_.end()) 和 if (it2 == p_to_m_.end())
里面有bug

评分

4

查看全部评分

本帖被以下淘专辑推荐:

 楼主| dg7743 发表于 2016-8-5 08:24:05 | 显示全部楼层
第四轮可以用trie来代替hash table来节省空间,面试时也忘了提了
回复 支持 反对

使用道具 举报

bluepp 发表于 2016-8-5 22:53:11 | 显示全部楼层
1. 不是level order 遍历么?
回复 支持 反对

使用道具 举报

yiwen_15 发表于 2016-8-6 00:01:24 | 显示全部楼层
第一题我觉得你的思路更好啊
回复 支持 反对

使用道具 举报

 楼主| dg7743 发表于 2016-8-6 00:28:45 | 显示全部楼层
bluepp 发表于 2016-8-5 22:53
1. 不是level order 遍历么?

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

使用道具 举报

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

使用道具 举报

白羽幸 发表于 2016-8-6 01:40:24 | 显示全部楼层
第一题用dfs的话space complexity只有O(k)
回复 支持 反对

使用道具 举报

 楼主| dg7743 发表于 2016-8-6 02:52:39 | 显示全部楼层
hxtang 发表于 2016-8-6 01:36
第一题从空间complexity来说确实是他的小。stack就是前序遍历非递归算法那个stack,栈内元素照理说是不超过 ...
. visit 1point3acres.com for more.
了解了,谢谢
回复 支持 反对

使用道具 举报

pushazhiniao 发表于 2016-8-6 03:17:20 | 显示全部楼层
楼主,感觉第一题面试官的意思是不是只存到上一层啊,这样省一半空间?不过也就一半吧。

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

谢谢!祝找工顺利!

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

使用道具 举报

YoYoqiekenow 发表于 2016-8-6 03:41:13 | 显示全部楼层
第四题,直接用hash table 存储每个名字的manager 不行吗? 这样不是每个功能都能实现?
回复 支持 反对

使用道具 举报

 楼主| dg7743 发表于 2016-8-6 08:46:30 | 显示全部楼层
pushazhiniao 发表于 2016-8-6 03:17
楼主,感觉第一题面试官的意思是不是只存到上一层啊,这样省一半空间?不过也就一半吧。

另外,想请教一 ...

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

我的话可能有歧义歧义。不过我的意思转化为图的话:. 鍥磋鎴戜滑@1point 3 acres
   A
   /
  B
/ \. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
C  D
我之所以说是"类似union-find",是因为isManager的代码跟union-find中find parent的部分很相似。
回复 支持 反对

使用道具 举报

 楼主| dg7743 发表于 2016-8-6 08:49:24 | 显示全部楼层
YoYoqiekenow 发表于 2016-8-6 03:41
第四题,直接用hash table 存储每个名字的manager 不行吗? 这样不是每个功能都能实现?
. 1point3acres.com/bbs
大体上是你这个意思。因为input是乱序的,有些需要考虑的corner cases:
比如
peer A, B
这时候A与B在一个peer group,但他们并没有manager
peer C, D
同理,C与D在另一个peer group
manager E, A
E称为A,B的manager
回复 支持 反对

使用道具 举报

csushin1992 发表于 2016-8-6 14:58:42 | 显示全部楼层
全部看完,感觉自己也经历了一遍面试,多谢楼主的面经!
回复 支持 反对

使用道具 举报

YoYoqiekenow 发表于 2016-8-7 04:05:44 | 显示全部楼层
dg7743 发表于 2016-8-6 08:49
大体上是你这个意思。因为input是乱序的,有些需要考虑的corner cases:
比如
peer A, B

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

使用道具 举报

pushazhiniao 发表于 2016-8-7 05:19:52 | 显示全部楼层
dg7743 发表于 2016-8-6 08:46
第一轮确实是应该双向DPS,我当时把自己绕晕了。

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

谢谢楼主
回复 支持 反对

使用道具 举报

wzs9988 发表于 2016-8-7 12:26:14 | 显示全部楼层
谢谢LZ分享经验!请问LZ有几年工作经验了?
回复 支持 反对

使用道具 举报

pushazhiniao 发表于 2016-8-8 01:13:19 | 显示全部楼层
dg7743 发表于 2016-8-6 08:46
第一轮确实是应该双向DPS,我当时把自己绕晕了。

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

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

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

使用道具 举报

 楼主| dg7743 发表于 2016-8-8 07:44:07 | 显示全部楼层
wzs9988 发表于 2016-8-7 12:26
谢谢LZ分享经验!请问LZ有几年工作经验了?

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

使用道具 举报

sunraincyq 发表于 2016-8-8 08:31:23 | 显示全部楼层
谢谢LZ分享这么详细的面经。请问是你要求到NYC ONSITE的吗还是你本来申请的POSITION是在NYC?
回复 支持 反对

使用道具 举报

hijkstra 发表于 2016-8-8 08:50:01 | 显示全部楼层
同感啊LZ,上周去面G有个别问到LC上的题,当时一边思考一边回想最佳解法,最后感觉做的比新题还差。。。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 11:11

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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