Yelp onsite 面经，跪了一道题

上周五下午1点半面的yelp。是downtown里的一栋楼，8楼是吃饭休闲的地方，9楼是HR的地方，13楼是engineer的工作区域，yelp的工作环境是一排大桌子，没有隔间，员工还是蛮多的，很多白人，也有些华人。HR说近两年主要招的都是 new grads.

第一轮面，上来就问 why yelp，然后问简历的project。完了之后做题目，leetcode 121 best time to buy and sell stock 原题。我一上来居然想到了trapping water那题。。。用了两个数组来存某个位置其左边最小值，和其右边最大值。在面试官引导优化了空间，最后其实不用额外空间就可以的。。。

第二轮面，还是问 why yelp，然后问简历的project。然后是一道 smallest k elements in an array的题，用个max heap搞定。我感觉挺满意。结果面试官又来一题。简易版的 lc 290 w

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

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

讲完了思路，然后写白板code的，写完后带着对方walk through一下。讲思路的时候可以乱一点，先来个brute force也行。但开始写的时候就不能乱来了，要尽量别出错。哎，我平时题目刷的不不够熟，表现的一般吧。还跪了第三轮。。

面我的大多是做backend的，我正好最近在研究谷歌三剑客，把GFS, MapReduce和他们讲了一通，感觉还好。

面试结束后HR有和我聊了一阵，然后说负责我的HR没来，下周二她回来上班，然后如果positive的话，会问我要reference。不知道跪没跪。。哎，求人品~~~

个人的简单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. }

复制代码

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

同上周五面的，不过我是Data mining team，虽然一道面经都没有但是不难，最后碰到个三哥又被坑了下。同祝好运啊~

上周五电面完，不知道能不能onstie, 觉得楼主答的妥啊！祝好运~~~~！！！！电影那个，要我也只会dfs。。。觉得是不是可以greedy?但是还没想明白，求大神解答！

请问lz是怎么学习谷歌三剑客，GFS, MapReduce这些内容的？上公开课还是lincode?
谢谢

放电影那题，其实用dfs, backtracking复杂度反正就那样了...但是代码写出来应该很简洁.

非常有用的面经~

问一下各位，电影这道题的时间复杂度应该怎样答呢？

电影么 二分图最大匹配 O(N^3)

非常同意楼主的那句话！大家要团结！！我马上去onsite ,店面也全是原题，都是感谢大家的智慧！求问楼主后来怎么样了

请问楼主面的是哪个组的呀？