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

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

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

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

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

• 二叉树最长路径 （二叉树的直径) 变种，有K个children, 并不是两个. LZ脑抽，D&C还用了HEAP，后来被要求优化，就把heap去了，用heap的时候面试官给提醒了一个bug，很快改掉。但是已经没时间给第二题写代码了。
• 给a list of sets, 如果两个set有同样的
  您好！
  本帖隐藏的内容需要积分高于 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跑细心一些

吭哧吭哧写了个morris~
class TreeNode():
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
class DoubleLinked():
    def __init__(self, val):
        self.val = val
        self.pre, self.nxt = None, None

class Solution():
    def inorderTransfer(self, root):
        if not root:
            return None

        cur = root
        head = DoubleLinked(0)
        node = head
        while cur:
            if not cur.left:
                tmp = DoubleLinked(cur.val)
                node.nxt = tmp
                tmp.pre = node
                node = node.nxt
                cur = cur.right
            else:
                pre = cur.left
                while pre.right and pre.right != cur:
                    pre = pre.right

                if not pre.right:
                    pre.right = cur
                    cur = cur.left

                else:
                    pre.right = None
                    tmp = DoubleLinked(cur.val)
                    node.nxt = tmp
                    tmp.pre = node
                    node = node.nxt
                    cur = cur.right

        return head.nxt

  

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. }

复制代码

edyyy 发表于 2018-4-15 10:38

50   TreeNode * n25 = new TreeNode (25);
51   TreeNode * n30 = new TreeNode (30);
52   TreeNode * n11 = new TreeNode (11);
53   n30->left = n11;
54   TreeNode * n12 = new TreeNode (12);
55   n12->left = n25;
56   n12->right = n30;
57   TreeNode * n15 = new TreeNode (15);
58   TreeNode * n36 = new TreeNode (36);
59   n15->left = n36;
60   TreeNode * n10 = new TreeNode (10);
61   n10->left = n12;
62   n10->right = n15;


这样的test case 过不了啊

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

idatascience 发表于 2018-4-14 02:53
第一轮就是写depth函数吧，然后diameter就是max(diameter of each children, top two max depth of childre ...

对 第一轮就recursive就可以。找max1 max2。要注意没有child和只有一个child的情况。merge set就如同你说的一样。一个map，key -> set。走一遍

第三轮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吧 还有别的么？

idatascience 发表于 2018-4-14 04:07
吭哧吭哧写了个morris~
class TreeNode():
    def __init__(self, val):

我觉得要考morris的话还挺偏门的，我觉得面试官原本的意思可能是用recursive来做，这样看起来貌似是O(1)但是O(n)
我觉得Morris还是挺偏门的，要是能写出来应该非常impressive。可惜LZ技能不够硬。

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

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

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