Yelp onsite 面经，跪了一道题

huangrui199126 发表于 2016-4-27 01:55
非常同意楼主的那句话！大家要团结！！我马上去onsite ,店面也全是原题，都是感谢大家的智慧！求问楼主后来 ...

不幸收到拒信了。。祝你好运啊！！

huangrui199126 发表于 2016-4-27 01:55
非常同意楼主的那句话！大家要团结！！我马上去onsite ,店面也全是原题，都是感谢大家的智慧！求问楼主后来 ...

不幸收到拒信了。。祝你好运啊！！

qjw1992 发表于 2016-4-29 13:55
请问楼主面的是哪个组的呀？

做后端的应该是。别人帮我推的，我也不知道哪个组。。

我觉得可以用BFS，基本数据类型设置为[not seen movie(set), movie schedule(list)]，然后在每个时刻根据这个时刻上映的电影进行遍历，根据上面的例子可以写成这样
第一层在14点：[(B,C,D), [A]], [(A,C,D), [B]], [(A,B,D), [C]], [(A,B,C), [D]]
第二层在15点：[(C,D), [A,B]], [(B,D), [A,C]], [(B,C), [A,D]], ...
直到最后一层17点，如果有则返回movie schedule，否则返回false

zsz1990ustc 发表于 2016-4-29 14:22
做后端的应该是。别人帮我推的，我也不知道哪个组。。

哎，感觉楼主很牛啊。。。yelp onsite果然难啊

想到一种greedy的做法，是把问题表示成矩阵，每行代表一个电影，每列代表一个时间段。1代表这个时间这个电影可以放，0代表不能放。然后每次迭代都去找行sum和列sum中最小的。如果最小sum是1就挑那个1的元素。如果最小sum不为1就挑另外一个维度最小对应的元素。挑中之后把对应的行和列删掉，继续迭代。。过程中一旦某行或列的sum为0就throw exception。不晓得靠不靠谱

楼主有详细的解答吗 关于看电影的那道题

Greedy O(n)方法：电影那个题可以先从最短的时间列表看起，例如，电影C: 14, 15 随便选一个，电影c时间确定，然后把那个时间点从所有的list里边除去。
不知道这样对不对啊？

bcc 发表于 2016-10-5 01:44
Greedy O(n)方法：电影那个题可以先从最短的时间列表看起，例如，电影C: 14, 15 随便选一个，电影c时间确定 ...

该解法并不是O(n)吧, 因为你本质上还是backtracking啊. 你提到的"把那个时间点从所有list除去", 其实直接把这个时间点放到一个Set里就好啦.

个人的简单backtracking解法:

1. public class Moive {
   
2.     /*
   
3.         给一串movie，假定每个movie都是一个小时，并且都在整点播放；给你一个List的movies，让你安排播放时间，如果没有答案throw一个exception。
   
4.         比如
   
5.         电影A: 14, 15, 16, 17
   
6.         电影B: 14, 15, 16
   
7.         电影C: 14, 15
   
8.         电影D: 14, 15, 17
   
9.         返回一个解就行，比如 A 14, B 16, C 15, D 17。 如果你要 A 14, B 15, 后面 C就没法看了.
   
10.      */
    
11.     class MoviePlay{
    
12.         String name;
    
13.         int time;
    
14. 
    
15.         public MoviePlay(String name, int time){
    
16.             this.name = name;
    
17.             this.time = time;
    
18.         }
    
19. 
    
20.         public String toString(){
    
21.             return name + ":" + time;
    
22.         }
    
23.     }
    
24.     public List<MoviePlay> arrange(Map<String, List<Integer>> movies) throws Exception{
    
25.         List<MoviePlay> rlt = new ArrayList<>();
    
26.         if(helper(rlt, new HashSet<>(), movies, new ArrayList<>(movies.keySet()), 0)) return rlt;
    
27.         throw new Exception("No valid arrangement");
    
28.     }
    
29. 
    
30.     public boolean helper(List<MoviePlay> rlt, Set<Integer> timeTaken, Map<String, List<Integer>> times, List<String> movieList, int index){
    
31.             if(index == movieList.size()) return true;
    
32.             String movie = movieList.get(index);
    
33.             List<Integer> playtime = times.get(movie);
    
34.             for(Integer time: playtime){
    
35.                 if(!timeTaken.contains(time)){
    
36.                     timeTaken.add(time);
    
37.                     rlt.add(new MoviePlay(movie, time));
    
38.                     if(helper(rlt, timeTaken, times, movieList, index + 1)) return true;
    
39.                     rlt.remove(rlt.size()-1);
    
40.                     timeTaken.remove(time);
    
41.                 }
    
42.             }
    
43.             return false;
    
44.     }
    
45. 
    
46.     public static void main(String[] args){
    
47.         Map<String, List<Integer>> movies = new HashMap<>();
    
48.         movies.put("A", new ArrayList());
    
49.         movies.put("B", new ArrayList());
    
50.         movies.put("C", new ArrayList());
    
51.         movies.put("D", new ArrayList());
    
52.         movies.get("A").addAll(Arrays.asList(14, 15, 16, 17));
    
53.         movies.get("B").addAll(Arrays.asList(14, 15));
    
54.         movies.get("C").addAll(Arrays.asList(14, 15));
    
55.         movies.get("D").addAll(Arrays.asList(14, 15, 16, 17));
    
56.         Moive m = new Moive();
    
57.         try{
    
58.             List<MoviePlay> rlt = m.arrange(movies);
    
59.             System.out.println(rlt);
    
60.         }catch (Exception e){
    
61.             e.printStackTrace();
    
62.         }
    
63.     }
    
64. }

复制代码