近期论坛无法登录的解决方案


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 6640|回复: 33
收起左侧

GoogleNYC跪经

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

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

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

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

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


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

  1. void printBSTKthLevelAlt(TreeNode *root, int k) {
  2.   if (root == nullptr || k < 0) {
  3.     return;
  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) {
  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;. 鍥磋鎴戜滑@1point 3 acres
  25.   }
  26. }
  27. . From 1point 3acres bbs
  28. void printLevel(const deque<TreeNode*>& q) {. Waral 鍗氬鏈夋洿澶氭枃绔,
  29.   bool left = true;
  30.   while (!q.empty()) {
  31.     TreeNode* node;
  32.     if (left) {
  33.       node = q.front();
  34.       q.pop_front();
  35.     }.鏈枃鍘熷垱鑷1point3acres璁哄潧
  36.     else {. visit 1point3acres.com for more.
  37.       node = q.back();
  38.       q.pop_back();
  39.     }
  40.     cout << node->val << ' ';
  41.     left != left;
  42.   }
  43.   cout << endl;
  44. }
复制代码
然后面试官问我time&space complexity是什么,我答道O(n), O(2^k)。
然后他说怎么可以在保持time complexity的同时优化space。我就开始纠结了。
他提示说用DFS,我比划了半天也没想出来。然后时间快到的时候,他告诉了我他的思路:.鏈枃鍘熷垱鑷1point3acres璁哄潧
维护两个stack,一个stack先push right child,另一个先push left child
比如我们有      a1                        这棵树,我们想打印k=3这层,. Waral 鍗氬鏈夋洿澶氭枃绔,
                 /            \.1point3acres缃
        a2             a3
          /    \        /      \. From 1point 3acres bbs
     a4    a5      a6      a7. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
    / \   /  \   /   \    /  \
   a8 a9 a10 a11 a12 a13 a14 a15

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

第二轮: Merge Two Sorted Array
一个白人大叔+亚洲shadow。
因为第一轮多耽误了些时间,大叔就问了一个简单的问题。然后跟我一直聊天。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

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

第四轮:
实现一个class支持三个API:.鏈枃鍘熷垱鑷1point3acres璁哄潧
peer A, B
manager A, B. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
isManager A, B

比如.鐣欏璁哄潧-涓浜-涓夊垎鍦
peer Tim, Bill
peer Bill, Mike
manager Lucy, Tim
isManager Lucy, Tim -> True
isManager Lucy, Mike -> True
manager Amy, Lucy. 1point3acres.com/bbs
isManager Amy, Bill -> True

具体的来说,如果给两个人添加peer关系,他们就成为一个peer group。
如果其中一个人已经在某个peer group,另一个人没有peer group,就把后者添加到前者的peer group。
每个peer group都只有一个manager。. Waral 鍗氬鏈夋洿澶氭枃绔,
所以不会出现
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。.鐣欏璁哄潧-涓浜-涓夊垎鍦
每个manager的manager也是其下属的manager。
我觉得可以用类似union-find的思路来做,当时的我给出的代码如下

  1. class ManagerSystem() {
  2. public:.鏈枃鍘熷垱鑷1point3acres璁哄潧
  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;. more info on 1point3acres.com
  14.     }
  15.     if (it1 == p_to_m_.end()) {
  16.       auto m = p_to_m_[p1];. 1point 3acres 璁哄潧
  17.       p_to_m_[p2] = m;
  18.       m_to_p_[m].push_back(p1);
  19.       return true;
  20.     }. 鍥磋鎴戜滑@1point 3 acres
  21.     if (it2 == p_to_m_.end()) {
  22.       auto m = p_to_m_[p2];.鏈枃鍘熷垱鑷1point3acres璁哄潧
  23.       p_to_m_[p1] = m;
  24.       m_to_p_[m].push_back(p2);
  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 == "") {. visit 1point3acres.com for more.
  29.       auto m1 = it1.second;
  30.       auto m2 = it2.second;.1point3acres缃
  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;. from: 1point3acres.com/bbs
  37.     }
  38.     //if both peers showed up before and p1 has dummy managers, merge their peer groups. from: 1point3acres.com/bbs
  39.     ... 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  40.     //if both peers showed up before and p2 has dummy managers, merge their peer groups
  41.     ...-google 1point3acres
  42.     //if both peers showed up before and have different real managers, return false
  43.     ...
  44.   }. 鍥磋鎴戜滑@1point 3 acres
  45. . 1point 3acres 璁哄潧
  46.   void manager(string m, string p) {
  47.     ... . more info on 1point3acres.com
  48.   }

  49.   bool isManager(string m, string p) {
  50.     auto it = p_to_m_.find(p);
  51.       while (it != p_to_m_.end()) {
  52.         if (it.second->name == m) {
  53.           return true;
  54.         }
  55.         it = p_to_m_.find(it.second->name);
  56.       }
  57.     return false;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  58.   }
  59. private:
  60.   struct employee {. 1point3acres.com/bbs
  61.     string name = "";
  62.   }
  63.   unordered_map<string, employee*> p_to_m_;
  64.   unordered_map<employee*, vector<string>> m_to_p_;
  65. }
复制代码
这轮的问题属于比较开放性的,我觉得思路不难,但是做起来比较繁琐(或者我的思路比较繁琐,有更好的思路我没有想到)。
最关键的是,我一开始没有考虑好所有的情况,写到peer function一半时,发现有所遗漏,又开始打补丁。总体上我把我的思路阐明给了面试官,他也觉得没问题,但是代码并没有写完就到时间了。. from: 1point3acres.com/bbs
-google 1point3acres
第五轮:
也是一个比较开放性的问题。.1point3acres缃
先问我还记不记得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). from: 1point3acres.com/bbs
面试官又问如果一个vector特别大,另一个特别小咋办。
我说可以用小的在大的上做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。.1point3acres缃

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

. from: 1point3acres.com/bbs
补充内容 (2016-8-5 07:06):. 1point 3acres 璁哄潧
第四轮代码
if (it1 == p_to_m_.end()) 和 if (it2 == p_to_m_.end())
里面有bug

评分

4

查看全部评分

本帖被以下淘专辑推荐:

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

使用道具 举报

bluepp 发表于 2016-8-5 22:53:11 | 显示全部楼层
关注一亩三分地微博:
Warald
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.鏈枃鍘熷垱鑷1point3acres璁哄潧
第一题从空间complexity来说确实是他的小。stack就是前序遍历非递归算法那个stack,栈内元素照理说是不超过 ...

了解了,谢谢
回复 支持 反对

使用道具 举报

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

另外,想请教一下,manager peer设计那题,在A是B的经理,B是C的经理,C和D是peer的情况下,你怎样存A,B两个经理呀?Union-find不是只有一个parent节点吗?. Waral 鍗氬鏈夋洿澶氭枃绔,

谢谢!祝找工顺利!

补充内容 (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
楼主,感觉第一题面试官的意思是不是只存到上一层啊,这样省一半空间?不过也就一半吧。
. more info on 1point3acres.com
另外,想请教一 ...

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

我的话可能有歧义歧义。不过我的意思转化为图的话:
   A
   /. 1point 3acres 璁哄潧
  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 不行吗? 这样不是每个功能都能实现?

大体上是你这个意思。因为input是乱序的,有些需要考虑的corner cases:. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
比如. more info on 1point3acres.com
peer A, B. 鍥磋鎴戜滑@1point 3 acres
这时候A与B在一个peer group,但他们并没有manager. 鍥磋鎴戜滑@1point 3 acres
peer C, D
同理,C与D在另一个peer group. 1point 3acres 璁哄潧
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有几年工作经验了?

. visit 1point3acres.com for more.3年工作经验
回复 支持 反对

使用道具 举报

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

使用道具 举报

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-6-26 03:19

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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