SnapChat电面

一个白人哥们, 一看就是geek, Google hangout的时候还躺在沙发上跟我说。。 先问了一下最喜欢的一个project。直接上题。
class Person {
    int id;
    String name;
    List<Person> frien

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

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

    }
}

其实很简单。。最后问了下时间复杂度，LZ没说出他要的精确答案。。前面说的很磕巴感觉特别虚。。。希望发发慈悲再给个电面。求保佑！！！

最后过了吗

感谢分享~~ 写了一个 不知道对否

1. import java.util.*;
   
2. 
   
3. //class friendList {
   
4.        
   
5.         class Person {
   
6.                 int id;
   
7.                 String name;
   
8.                 List<Person> friends;
   
9.                 public Person(String n, List<Person> list){
   
10.                         name = n;
    
11.                         friends = list;
    
12.                 }
    
13. 
    
14.                 // mike => {miller, Jelly, Billy}
    
15.                 // miller => {miller, Cathy}
    
16.                 // Billy => {Henry, John}
    
17.                 // Cathy => {miller}. more info on 1point3acres.com
    
18.                 // print friends list of current person, e.g, mike -> miller, Jelly, Billy, Henry, John
    
19.                 public void printFriend() {
    
20.                         // implement here
    
21.                         HashSet<String> set = new HashSet<String>();
    
22.                         Queue<Person> queue = new LinkedList<Person>();
    
23.                         for(Person p : friends){
    
24.                                 queue.add(p);
    
25.                         }
    
26.                        
    
27.                         while(!queue.isEmpty()){
    
28.                                 Person cur = queue.poll();
    
29.                                 if(set.contains(cur.name)) continue;
    
30.                                 set.add(cur.name);
    
31.                                 for(Person nextPerson : cur.friends){
    
32.                                         queue.add(nextPerson);
    
33.                                 }
    
34.                         }
    
35.                         for(String s : set){
    
36.                                 if(s.equals(name)) continue;
    
37.                                 System.out.println(s);
    
38.                         }
    
39.                 }
    
40.        
    
41.         public static void main(String[] args) {
    
42.                 List<Person> list1 = new ArrayList<Person>();
    
43.                 List<Person> list2 = new ArrayList<Person>();
    
44.                 List<Person> list3 = new ArrayList<Person>();
    
45.                 List<Person> list4 = new ArrayList<Person>();
    
46.                 List<Person> list5 = new ArrayList<Person>();
    
47.                 List<Person> list6 = new ArrayList<Person>();
    
48.                 //list1.addAll(Arrays.asList("Miller", "Jelly", "Billy"));
    
49.                 //list1.addAll(Arrays.asList("0", "1", "8"));
    
50.                 Person p1 = new Person("mike", list1);
    
51.                 Person p2 = new Person("miller", list2);
    
52.                 Person p3 = new Person("Billy", list3);
    
53.                 Person p4 = new Person("Cathy", list4);
    
54.                 Person p5 = new Person("Henry", list5);
    
55.                 Person p6 = new Person("Jelly", list6);
    
56.                
    
57.                
    
58.                 list1.addAll(Arrays.asList(p2, p3, p6));
    
59.                 list2.addAll(Arrays.asList(p1, p3));
    
60.                 list3.addAll(Arrays.asList(p5));
    
61.                 list3.addAll(Arrays.asList(p1));
    
62.                
    
63.                 p1.printFriend();
    
64. 
    
65.                
    
66.         }
    
67.         }
    
68. //}

复制代码

letsdoit666 发表于 2016-1-20 14:30
lz麻烦再解释一吧，为啥mike的朋友中有billy，但是billy的朋友中没有mike？难道是有向图的遍历，感觉这种应 ...

应该是有向图才有意义吧？不然无向图的话 如果朋友的朋友也是朋友 不就等于把所有人都放进去好了？

怎么看到在沙发的...难道有要求开视讯? LZ问下照答案来看是朋友的朋友也算朋友吗?  因为mile 的朋友只有miller jelly and billy? 但是答案是miller, jelly, billy ,henry ,John?

lz麻烦再解释一吧，为啥mike的朋友中有billy，但是billy的朋友中没有mike？难道是有向图的遍历，感觉这种应该是无向图啊

请问楼主时间复杂度如何回答~

楼主最后过了吗？

感觉跟楼主是同一个小哥面的同一个题。。。最后也问了复杂度。。求问楼主过了吗？小哥人好吗？好紧张。。。

求问时间复杂度lz！ 祝onsite 祝offer

应该是问几度之内的朋友 bfs应该能解决 注意有环的情况

请问楼主，这个的时间复杂度是多少勒