非死不可 热乎昂赛面经 NEW GRAD

借别人的号发的。LZ朋友给的内推。电面很危险过。昂赛想点一首凉凉送给自己。看坛子里的面经说要两题hire，感觉特别难做到。
总的说面试体验还是不错，四个人里南亚有两雄一雌，LZ确实运气欠佳。

店面 有shadow，面试官一开始以为是白人，后来看给的sheet发现应该是个ABC

• 给两个Binary字符串，返回它们和的字符串 （硬做）
• 给两个整数，返回他们的商，不能用除法（二分查找）
  

昂赛
    第一轮：三哥，只有第一题写了代码。第二题来不及了，就说了思路。这一轮的小三哥很nice，聊得很开心

• 二叉树最长路径 （二叉树的直径) 变种，有K个children, 并不是两个. LZ脑抽，D&C还用了HEAP，后来被要求优化，就把heap去了，用heap的时候面试官给提醒了一个bug，很快改掉。但是已经没时间给第二题写代码了。
• 给a list of sets, 如果两个set有同样的element, 把他们合并。返回合并好的list of sets。（并查集）Follow up: 如何优化查找时间。答，可以在查找root的时候flatten the
  您好！
  本帖隐藏的内容需要积分高于 188 才可浏览
  您当前积分为 0。
  使用VIP即刻解锁阅读权限或查看其他获取积分的方式

  游客，您好！
  本帖隐藏的内容需要积分高于 188 才可浏览
  您当前积分为 0。
  VIP即刻解锁阅读权限 或 查看其他获取积分的方式
  Unlock interview details and practice with AI
  Curated Interview Questions from Top Companies
  
  补充内容 (2018-4-14 02:05):
  顺便替号主人求大米，谢谢各位看官。祝大家offer多多。
  
  补充内容 (2018-4-14 02:06):
  LZ也要move on了，求湾区公司内推或者有没有什么在招人的好公司推荐？
  
  补充内容 (2018-4-14 05:50):
  各位很抱歉，写的时候，问题是加了下划线的。可惜发帖以后就不见了。每一个黑点后面第一句话就是题
  
  补充内容 (2018-4-14 06:07):
  LZ补充一句，FB题简单，所以定要bug free. test case跑细心一些

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

  

1. //left = next; right = prev; head->prev = tail
   
2. pair<TreeNode*,TreeNode*> helper(TreeNode* root) {// return {head, tail}
   
3.     if (root == NULL || (root->left == NULL && root->right == NULL)) return make_pair(root,root);
   
4.     pair<TreeNode*,TreeNode*> l = helper(root->left);
   
5.     pair<TreeNode*,TreeNode*> r = helper(root->right);
   
6.     //head = l.first; tail = r.second
   
7.     root->left = l.second;
   
8.     if (l.second)l.second->right = root;
   
9.     root->right = r.first;
   
10.     if (r.first) r.first->left = root;
    
11.     return make_pair(l.first, r.second);
    
12. }
    
13. TreeNode* bt2dl(TreeNode* root) {
    
14.     return helper(root).first;
    
15. }

复制代码

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

第一轮就是写depth函数吧，然后diameter就是max(diameter of each children, top two max depth of children)吧
第二轮，是说先每个set每个element走一边，然后生成ｄｉｃｔ{element value: [set ]}
然后走一遍dict，凡是element对应两个及以上的set id就union对吧？

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

第三轮O（1）的要求不包括扩新建的ListNode是吧？除node之外O（1），correct？

idatascience 发表于 2018-4-14 03:07
第三轮O（1）的要求不包括扩新建的ListNode是吧？除node之外O（1），correct？

也想知道这个问题的答案

inorder traversal, 要O(1) 就只有threaded morris 和parent pointer吧 还有别的么？

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

liu5395 发表于 2018-4-14 04:15
也想知道这个问题的答案

确实，O(1)是extra space. 你output的是output space，是必须要的。

真心不易，bar真高，10分钟单单写Morris traversal都够呛。压力之下，楼主已经表现很好了，祝楼主拿offer！