Linkedin二面面经

第一个题是很简单的pow,第二题题目很长，加上面试官大姐的东南亚口音听得不太习惯，花了挺长时间理解题意，其实就是BFS，虽然大姐说track是对的但是最后没有写出完整的代码，感觉已跪，发出来给之后的面试攒点RP吧

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

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

hildren

补充内容 (2014-10-18 00:02):
还有一个条件：父子关系不能颠倒（但可以为sibling）

赞面经。第二题，可以把所有的节点先放到一个数组里面。然后把这些点连成一个N叉树。连起来的时候需要注意，因为你可以连成一个完全树，所以A[i]的N个儿子分别是i*N+1到i*N+N。这样一个个连起来就好了，连起来很方便。所以就是1.按level 遍历存到数组里面，preorder应该也可以。这样保证不违反那个sibling的条件。2.在数组里面连出一个full N tree. 主要考察的是遍历和完全树的trick

如果实在要优化的话，可以把数组变成一个queue。然后用按level遍历。如果把A[i]和N个儿子连起来之后，可以从队列里面pop出A[i]。只是一点小优化而已。

1. public class CompactTreeBuilder {
   
2. 
   
3.     public static TreeNode compact(TreeNode root, int n) {
   
4.         if (root == null || n == 0) return root;
   
5.         Queue<TreeNode> q1 = new LinkedList<TreeNode>();
   
6.         Queue<TreeNode> q2 = new LinkedList<TreeNode>();
   
7.         q1.offer(root);
   
8.         q2.offer(root);
   
9.         int currLevel = 1, nextLevel = 0;
   
10.         while (!q1.isEmpty()) {
    
11.             TreeNode front = q1.poll();
    
12.             for (TreeNode child : front.children) {
    
13.                 q1.offer(child);
    
14.                 q2.offer(child);
    
15.                 nextLevel++;
    
16.             }
    
17.             if (--currLevel == 0) {
    
18.                 currLevel = nextLevel;
    
19.                 nextLevel = 0;
    
20.             }
    
21.         }
    
22.         TreeNode newRoot = q2.poll();
    
23.         fillChildren(newRoot, q2, n);
    
24.         return newRoot;
    
25.     }
    
26.    
    
27.     private static void fillChildren(TreeNode root, Queue<TreeNode> queue, int n) {
    
28.         if (root == null || queue.isEmpty()) return;
    
29.         int count = 0;
    
30.         root.children = new ArrayList<TreeNode>();
    
31.         while (!queue.isEmpty() && count < n) {
    
32.             root.children.add(queue.poll());
    
33.             count++;
    
34.         }
    
35.         for (TreeNode child : root.children) {
    
36.             fillChildren(child, queue, n);
    
37.         }
    
38.     }
    
39. }
    
40. 
    
41. class TreeNode {
    
42.     int value;
    
43.     List<TreeNode> children;
    
44.     public TreeNode(int vlaue) {
    
45.         this.value = value;
    
46.         children = new ArrayList<TreeNode>();
    
47.     }
    
48. }

复制代码

不知道大神们对难的定义是什么，不过我估计我面的这么多公司的题目都没有能被称的上难的吧

因为Linkedin非常明显是有题库的，所以发发面经希望能造福下之后面试的小伙伴们

为啥没有权限下载。。

就用BFS走一下咯，copy过去的tree也用一个queue存，满了就dequeue这样，这题应该不难吧

lz可以更新下第二题么？好像看不到哎。

wjl2525 发表于 2014-10-17 08:32
lz可以更新下第二题么？好像看不到哎。

不知道为什么我没办法复制文本，所以贴的截图，没有设置权限应该能点开？

NANA1123 发表于 2014-10-17 08:34
不知道为什么我没办法复制文本，所以贴的截图，没有设置权限应该能点开？

不知道哎，反正我打开链接的时候提示是：抱歉，您没有权限下载本附件

我怎么觉得第二题很难呢。。。如果用一个queue先把树存下来，有点浪费空间，可以满了的话就添加在新树上,不过worst case都一样，因为假如是原来的每层node比transform的大的话，必须要把整个树存下来。
下面是代码，大家帮忙看一下，看看有没有什么bug。。。

1. TreeNode *compact(TreeNode *root, int n) {
   
2.         queue<TreeNode *> q;
   
3.         q.push(root);
   
4.         queue <TreeNode *> new_q;
   
5.         TreeNode *new_root = new TreeNode(root->val)
   
6.         new_q.push(new_root);
   
7.         while (!root->adj.empty()) {
   
8.                 q.push(root->adj.pop_front());
   
9.         }
   
10.         while (!q.empty()) {
    
11.                 while (q.size() >= n) {
    
12.                         TreeNode *new_node = new_q.pop();
    
13.                         for (int i = 0; i < n; i++) {
    
14.                                 TreeNode *temp = q.pop();
    
15.                                 new_node->adj.push_back(new TreeNode(temp->val));
    
16.                                 while (!temp->adj.empty()) {
    
17.                                         q.push(temp->adj.pop_first());
    
18.                                 }
    
19.                         }
    
20.                 }
    
21.                 TreeNode *node = q.peek();
    
22.                 while (!node->adj.empty()) {
    
23.                         q.push(node->adj.pop_first());
    
24.                 }
    
25.         }
    
26.         return new_root;
    
27. }

复制代码

3652ltc 发表于 2014-10-17 13:07
我怎么觉得第二题很难呢。。。如果用一个queue先把树存下来，有点浪费空间，可以满了的话就添加在新树上,不 ...

我看不到题目，层主能麻烦你简单复述下题目要求吗？谢谢啦。

NANA1123 发表于 2014-10-17 08:32
不知道大神们对难的定义是什么，不过我估计我面的这么多公司的题目都没有能被称的上难的吧

因为Linkedin ...

我怎么感觉这题挺难的。。。