狗家10月底Onsite挂经

10月底MTV Onsite
第一轮：国人大哥 求2个BST相同的元素 要求O1 space 强制要求写Morris Traversal Iterator 血跪。。。
第二轮：Snake an

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

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

(2019-1-2 02:36):
第四题是要求小于n^2 时间复杂度 类似LIS的题

第一题真狠，我写了下代码，应该是对的，大家可以看看

1. class Solution {
   
2.    
   
3.     private Node {
   
4.         int val;
   
5.         Node left, right;
   
6.         public Node (int val) {
   
7.             this.val = val;
   
8.         }
   
9.     }
   
10.    
    
11.     public List<Integer> commonElem(Node a, Node b) {
    
12.         List<Integer> res = new ArrayList<>();
    
13.         if (a == null || b == null) return res;
    
14.         
    
15.         Node cur1 = a, cur2 = b;
    
16.         
    
17.         //move cur1 and cur2 to the smallest node.. and
    
18.         //establish the the predecessor to successor link for inorder traverse...
    
19.         findLeftMostNode(cur1);
    
20.         findLeftMostNode(cur2);
    
21.         
    
22.         //compare the node one by one...
    
23.         //if same, add value to the res.. and move both node to next;
    
24.         //if cur1 < cur2.. only move cur1
    
25.         // else move cur2...
    
26.         while (cur1 != null && cur2 != null) {
    
27.             if (cur1.val == cur2.val) {
    
28.                 res.add(cur1.val);
    
29.                 getNext(cur1);
    
30.                 getNext(cur2);
    
31.             } else if (cur1.val < cur2.val) {
    
32.                 getNext(cur1);
    
33.             } else {
    
34.                 getNext(cur2);
    
35.             }
    
36.         }
    
37.         
    
38.         return res;
    
39.     }
    
40.    
    
41.     private void getNext(TreeNode cur) {
    
42.         if (cur.left == null) { cur = cur.right; }
    
43.         TreeNode prev = cur.left;
    
44.         while (prev.right != null && prev.right != cur) {
    
45.             prev = prev.right;
    
46.         }
    
47.         if (prev.right == cur) {
    
48.             prev.right = null;
    
49.             cur = cur.right;
    
50.         } else {
    
51.             prev.right = cur;
    
52.             cur = cur.left;
    
53.         }
    
54.     }
    
55.    
    
56.     private void findLeftMostNode(TreeNode cur) {
    
57.         while (cur != null) {
    
58.             if (cur.left == null) break;
    
59.             TreeNode prev = cur.left;
    
60.             while (prev.right != null) {
    
61.                 prev = prev.right;
    
62.             }
    
63.             prev.right = cur;
    
64.             cur = cur.left;
    
65.         }
    
66.     }
    
67. }

复制代码

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

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

zhangzitong001 发表于 2019-1-2 03:15
第四轮楼主应该是二分  dp 定义为长度i的increasing subsequence的最小ending值

这题长度为k-1的所有比当前值小的ending都可以用来组成长度为k的subsequence,只保存最小ending应该不行吧。。。

国人大哥就喜欢morris  kmp什么的 背了就会 不然肯定不会的考法lol

第四轮楼主应该是二分  dp 定义为长度i的increasing subsequence的最小ending值

背一个morris真没什么意思啊，还不如加个parent node写

求问围成是怎么定义的？这个下面中间的1算是被围了吗？谢谢
0  1  0
1  1  1
0  1  0

补充内容 (2019-1-2 04:02):
还是说要这样？中间的1才算被围了？
1 1 1
1 1 1
1 1 1

当横压一代 发表于 2019-1-2 04:00
求问围成是怎么定义的？这个下面中间的1算是被围了吗？谢谢
0  1  0
1  1  1

只看上下左右4个方向

zhangzitong001 发表于 2019-1-2 03:15
第四轮楼主应该是二分  dp 定义为长度i的increasing subsequence的最小ending值

不是要求最长的Sub 是要输出实际那个Sequence的具体内容

canoee 发表于 2019-1-2 03:05
第一个太狠了

唉人生第一次onsite  啥也不懂就遭遇十万点暴击。。。。。

45 分钟完成BST那道还是很有难度的。。。