脸家店面

1. 树的直径。
2. 给一些sets，保证每个set内元素不重复，如果两个sets有任何共同元素，则让其合并，直到不能合并为

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

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

注意。
HR也没有说冷冻时间，只是Thanks了一下。Move on。

根据楼上的讨论，写了下代码，楼主看对不对？
time: 建图O(N), N是所有set的元素总和， BFS: O(n), n所有sets的unique 元素个数， 所以总的时间复杂度应该是O(N)
space: O(N)

1. package Problems;
   
2. 
   
3. import java.util.*;
   
4. 
   
5. public class MergeSets {
   
6.         public List<List<Integer>> mergeSet(List<List<Integer>> sets) {
   
7.                 Map<Integer, List<Integer>> graph = new HashMap<>();//treat it as undirected graph
   
8.                 //construct graph adjacent list
   
9.                 for(List<Integer> set : sets) {
   
10.                         for(int i = 0; i < set.size(); i++) {
    
11.                                 int u = set.get(i);
    
12.                                 if(!graph.containsKey(u)) {
    
13.                                         graph.put(u, new ArrayList<Integer>());
    
14.                                 }
    
15.                                 if(i != 0) {
    
16.                                         int v = set.get(i - 1);//only to get the former neighbor which must exist in graph
    
17.                                         graph.get(v).add(u);
    
18.                                         graph.get(u).add(v);
    
19.                                 }
    
20.                         }
    
21.                 }
    
22.                
    
23.                 System.out.println("Graph:");
    
24.                
    
25.                 List<List<Integer>> res = new ArrayList<>();
    
26.                 Set<Integer> visited = new HashSet<Integer>();
    
27.                 Queue<Integer> q = new LinkedList<Integer>();
    
28.                
    
29.                 for(Map.Entry<Integer, List<Integer>> entry : graph.entrySet()) {
    
30.                         //travse all nodes in graph
    
31.                         int u = entry.getKey();
    
32.                         List<Integer> component = new ArrayList<Integer>();
    
33.                         //if not traverse before, use this node as start to find component by BFS
    
34.                         if(!visited.contains(u)) {
    
35.                                 q.offer(u);
    
36.                                 visited.add(u);
    
37.                                 while(!q.isEmpty()) {
    
38.                                         int cur = q.poll();
    
39.                                         component.add(cur);//add to current component
    
40.                                         for(int adj : graph.get(cur)) {
    
41.                                                 if(!visited.contains(adj)) {
    
42.                                                         q.offer(adj);
    
43.                                                         visited.add(adj);
    
44.                                                 }
    
45.                                         }
    
46.                                 }
    
47.                                 res.add(new ArrayList<Integer>(component));
    
48.                         }
    
49.                 }
    
50.                 return res;
    
51.         }
    
52.        
    
53.         public static void main(String[] args) {
    
54.                 MergeSets obj = new MergeSets();
    
55.                 int[][] input = {{1,2},{2,3},{3,4},{5,6,7},{7,8},{9},{9}};
    
56.                 List<List<Integer>> sets = new ArrayList<>();
    
57.                 for(int[] nums : input) {
    
58.                         List<Integer> set = new ArrayList<>();
    
59.                         for(int num : nums) {
    
60.                                 set.add(num);
    
61.                         }
    
62.                         sets.add(new ArrayList<Integer>(set));
    
63.                 }
    
64.                
    
65.                 for(List<Integer> set : sets) {
    
66.                         System.out.println(set);
    
67.                 }
    
68.                
    
69.                 System.out.println("After merge:");
    
70.                
    
71.                 for(List<Integer> set : obj.mergeSet(sets)) {
    
72.                         System.out.println(set);
    
73.                 }
    
74.                
    
75.         }
    
76. }
    

复制代码

lucas13 发表于 2017-10-17 18:18
第二题Union Find哇，时间空间复杂度是元素总数。话说楼主什么时候面的呢？不是说new grad已经freeze了吗？

union find 要怎么实现。。？

第二题Union Find哇，时间空间复杂度是元素总数。话说楼主什么时候面的呢？不是说new grad已经freeze了吗？

感谢楼主分享！
请问第一题是什么意思？
第二题的话应该是merge intervals变形，我觉得可以只考虑每个set里面第一个和最后一个数。 楼主是怎么解决的呢？

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

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

Lz不是都做出来了么 这样也不行？

Sai_L 发表于 2017-10-17 14:25
一就是求树的最长路径，lc原题。
二跟merge intervals还不太一样，不能只看第一个和最后一个了，像{1,3} ...

我只想到 brute force 解 .... 只有同个set elements in order 的条件吗?

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

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

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

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

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

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