亚麻社招onsite

亚麻这个职位在湾区Sunnyvale，Lab126。 属于社会招聘。他们开了一个面试日，每个月某个周五集体面试，每人只有四轮，面试者可选上午或者下午。每一轮15min的行为题+30min技术题 （亚麻的behaviour question 很重要！）
1 系统设计：Tiny url， 白大叔主面，欧洲哥shadow
2

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

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

就到了，三哥离开。还是不懂他到底要设计什么

面试结果出的很快，面的是sde2，给的sde1的offer。 可能因为三哥那轮不好，也可能因为自己fresh EE PhD，背景不match。

祝大家找工作顺利！

仅供参考：
void recursionMerge(TreeNode root1, TreeNode root2)
//根为root1的树接收节点， 根为root2的树被遍历，挨个插入root1的那棵树
        if root2 is null, return
        TreeNode tempLeft = root2.left; TreeNode tempRight = root2.right;
        root2.left = null; root2.right = null;
        insert(root1, root2);        // 调用另外一个函数，insert a single TreeNode to BST
        recursionMerge(root1, tempLeft);
        recursionMerge(root1, tempRight);
还可以多写一个wrapper函数来快速解决，root1为空或者root2为空的情况
递归函数产生的额外空间无所谓，当然和面试官确认下是最稳的

Thanks to LZ. I used bottom-up recursion to save temporary pointers.

1. void insertBST(Node* r, Node* x) {
   
2.     if (!r || !x) return;
   
3.     if (x->val < r->val)
   
4.         if (r->left) r = r->left;
   
5.         else insertBST(r->left, x);
   
6.     else if (r->right) r = r->right;
   
7.     else insertBST(r->right, x);
   
8. }
   
9. 
   
10. void mergeBST(Node* r1, Node* r2) {
    
11.     if (!r2) return;
    
12.     mergeBST(r1, r2->left), mergeBST(r1, r2->right);
    
13.     r2->left = r2->right = nullptr;
    
14.     insertBST(r1, r2);
    
15. }

复制代码

合并二叉树O1  好像最近很火。最近几个月看到几个公司onsite都出这题

楼主报下包裹？

想问下lz 亚麻得社招 也是general？还是按组招？

amazon这个面试日是一直都有的还是最近才开的啊？

楼主能说下最后一题合并bst思路吗

包裹可以参考地里抖offer版，湾区亚麻sde1，感觉他们的包裹稍大点
这个是组招，第一轮shadow的欧洲哥就是Hire Manager
面试日应该是最近才有，recruiter说是加快招聘速度的新政策
合并BST，就是把一个BST里的node拆散了，加入到另外一个BST里。
        写一个helper来insert单一节点。
        写一个merge函数，遍历一个BST，把遍历到的每一个节点加到另一个BST
        注意insert节点前，要把该左右child设为空

TingDallas 发表于 2018-2-10 02:26
包裹可以参考地里抖offer版，湾区亚麻sde1，感觉他们的包裹稍大点
这个是组招，第一轮shadow的欧洲哥就是H ...

多谢Lz 请问为什么“insert节点前，要把该左右child设为空”？

TingDallas 发表于 2018-2-10 02:26
包裹可以参考地里抖offer版，湾区亚麻sde1，感觉他们的包裹稍大点
这个是组招，第一轮shadow的欧洲哥就是H ...

题目中要求O(1)space的话就是不能创建新的node, 所以当“insert”节点时，若左右child设为空的话如何继续traverse要拆散的BST呢？

这个题应该是只让left, right pointers重新指向吧。

而且如果严格要求O(1)space的话连recursion都不能用，否则就是O(h) space, h=tree height, 因为recursion造成的call stack memory allocation也得算了。

这个问题似乎应该是将BST and sorted double linked list进行in place转换吧： https://www.geeksforgeeks.org/me ... inary-search-trees/

LUOLUOLNSH 发表于 2018-2-15 09:57
多谢Lz 请问为什么“insert节点前，要把该左右child设为空”？

否则被拆散的节点会继续连在在以前的左右子节点上