推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 2375|回复: 10
收起左侧

SnapChat Full-Time 电面

[复制链接] |试试Instant~ |关注本帖
tj474474 发表于 2016-10-20 10:45:47 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 全职@Snapchat - 网上海投 - 技术电面 |Otherfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
今天下午的电面是一个国人小哥先聊了15分钟他的组 还有履历上的东西
然后就做题
Meeting Room ll的变化版 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
不是计算最少需要几个meeting room
还要把schedule的结果列出来
例如
Inputs: Meetings, [4, 9], [2, 6], [2, 3], [6, 7]
Outputs:
Room1 : [2, 3], [4, 9]
Room2 : [2, 6], [6, 7]. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

我的做法是先把所有的schedule根据start time sort
同时还用了一个PriorityQueue
顺序是根据schedule的end time.

PriorityQueue的Node我还多放了一个该event被存放的roomId
这样从PrioirtyQueue里面pop出来的时候就可以直接找到需要添加的room
我的面試官挺好的 因為我提出這個做法. 鍥磋鎴戜滑@1point 3 acres
他直接就跟我說那你input就用你這個List<Node>吧

不过最后compile有个小bug
因为时间到了没弄完. 1point 3acres 璁哄潧
还是希望有onsite...
附上代碼
  1. import java.util.*;
  2. . 1point 3acres 璁哄潧
  3. class Node {. more info on 1point3acres.com
  4.     public int roomId;
  5.     public List<Integer> interview;
    . 鍥磋鎴戜滑@1point 3 acres
  6.     public Node(List<Integer> interview) {
  7.         this.interview = interview;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  8.     }
  9. }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

  10. class Solution {
  11.     static void schedule(List<Node> interviews) {
  12.         List<List<List<Integer>>> result = new ArrayList<>();
  13.         PriorityQueue<Node> pq = new PriorityQueue(1, new Comparator<Node>(){
  14.             @Override
  15.             public int compare(Node a, Node b) {
  16.                 return a.interview.get(1) - b.interview.get(1);
  17.             }.1point3acres缃
  18.         });
  19.         
  20.         Collections.sort(interviews, new Comparator<Node>(){
  21.             @Override
  22.             public int compare(Node a, Node b) {
  23.                 return a.interview.get(0) - b.interview.get(0);
  24.             }
  25.         });
  26.         . visit 1point3acres.com for more.
  27.         int roomCount = 0;-google 1point3acres
  28.         for (Node n : interviews) {
  29.             if (pq.isEmpty()) {
  30.                 n.roomId = roomCount;
  31.                 result.add(new ArrayList<>());
  32.                 result.get(roomCount).add(n.interview);
  33.                 pq.offer(n);
  34.             } else {
  35.                 Node prevNode = pq.peek();
  36.                 if (n.interview.get(0) < prevNode.interview.get(1)) {
  37.                     roomCount++;
  38.                     n.roomId = roomCount;
  39.                     result.add(new ArrayList<>());
  40.                     result.get(roomCount).add(n.interview);
  41.                     pq.offer(n);-google 1point3acres
  42.                 } else {
  43.                     pq.poll();
  44.                     int prevRoomId = prevNode.roomId;
  45.                     n.roomId = prevRoomId;
  46.                     result.get(prevRoomId).add(n.interview);
  47.                     pq.offer(n);. 鍥磋鎴戜滑@1point 3 acres
  48.                 }
  49.             }
  50.         } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  51.         for (int i = 0; i < result.size(); ++i) {
  52.             System.out.print("Room");
  53.             System.out.print(i + 1);
  54.             System.out.print(": ");
  55.             for (int j = 0; j < result.get(i).size(); ++j) {
  56.                 System.out.print("[");. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  57.                 System.out.print(result.get(i).get(j).get(0));
  58.                 System.out.print(", ");
  59.                 System.out.print(result.get(i).get(j).get(1));
  60.                 System.out.print("]");
  61.                 if (j < result.get(i).size() - 1) {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  62.                     System.out.print(", ");
  63.                 } else {
  64.                     System.out.print("\n");
  65.                 }
  66.             }
  67.         }
  68.     }
  69.     . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  70.     static public void main(String args[]) {
  71.         //[4, 9], [2, 6], [2, 3], [6, 7]. 1point 3acres 璁哄潧
  72.         Node n1 = new Node(Arrays.asList(4, 9));
  73.         Node n2 = new Node(Arrays.asList(2, 6));
  74.         Node n3 = new Node(Arrays.asList(2, 3));
  75.         Node n4 = new Node(Arrays.asList(6, 7));. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  76.         List<Node> input = Arrays.asList(n1, n2, n3, n4);
  77.         schedule(input);
  78.     }   
  79. }
复制代码

评分

2

查看全部评分

本帖被以下淘专辑推荐:

zwcelesta 发表于 2016-10-20 20:44:36 | 显示全部楼层
    public Queue<LinkedList<Interval>> scheduledRooms (List<Interval> meetings) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
        Queue<LinkedList<Interval>> q = new PriorityQueue<>((o1, o2) -> o1.getLast().end - o2.getLast().end); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
        Collections.sort(meetings, (o1, o2) -> o1.start == o2.start ? o1.end - o2.end : o1.start - o2.start);
        for (Interval meeting : meetings) {
            LinkedList<Interval> room = (q.isEmpty() || meeting.start < q.peek().getLast().end) ? new LinkedList<>() : q.poll();
            room.add(new Interval(meeting.start, meeting.end));
            q.offer(room);
        }
        while (!q.isEmpty()) {
            List<Interval> room = q.poll();
            room.forEach(i -> System.out.print("[" + i.start + "," + i.end + "], "));
            System.out.println(" ");
        }
        return q;
    }

评分

1

查看全部评分

回复 支持 4 反对 0

使用道具 举报

edyyy 发表于 2016-10-20 11:43:48 | 显示全部楼层
谢谢楼主分享,祝好运
回复 支持 反对

使用道具 举报

 楼主| tj474474 发表于 2016-10-20 22:40:31 | 显示全部楼层
zwcelesta 发表于 2016-10-20 20:44
public Queue scheduledRooms (List meetings) {. From 1point 3acres bbs
        Queue q = new PriorityQueue((o1, o2) -> o ...

好简洁的方法!把LinkedList直接拿来当PriorityQueue的Key
还有Java 8的语法让代码看起来简单多了看来得多学学
回复 支持 反对

使用道具 举报

linweihua0 发表于 2016-10-21 03:02:54 | 显示全部楼层
zwcelesta 发表于 2016-10-20 20:44
public Queue scheduledRooms (List meetings) {
        Queue q = new PriorityQueue((o1, o2) -> o ...
. Waral 鍗氬鏈夋洿澶氭枃绔,
这个 你还得考虑merge interval  [1,2] [2,4] -> [1,4]
回复 支持 反对

使用道具 举报

telepathy 发表于 2016-10-31 11:36:17 | 显示全部楼层
楼主我也面倒了这题!可惜没提前看到你的帖子。求问面完多久收到结果啊?
回复 支持 反对

使用道具 举报

pocketnail 发表于 2016-10-31 11:45:46 | 显示全部楼层
我第一轮也是面了这道题,当时也是出了小bug,但也过了,楼主加油!
回复 支持 反对

使用道具 举报

freemail165 发表于 2016-10-31 12:35:41 | 显示全部楼层
linweihua0 发表于 2016-10-21 03:02
这个 你还得考虑merge interval  [1,2] [2,4] -> [1,4]

题目没要求merge..鐣欏璁哄潧-涓浜-涓夊垎鍦
上面这个解法的问题是不能按room的使用顺序来输出。

不知道题目是否要求
回复 支持 反对

使用道具 举报

 楼主| tj474474 发表于 2016-10-31 12:40:07 | 显示全部楼层
telepathy 发表于 2016-10-31 11:36
楼主我也面倒了这题!可惜没提前看到你的帖子。求问面完多久收到结果啊?

兩天後收到結果 被拒了
回复 支持 反对

使用道具 举报

 楼主| tj474474 发表于 2016-10-31 12:40:43 | 显示全部楼层
pocketnail 发表于 2016-10-31 11:45
我第一轮也是面了这道题,当时也是出了小bug,但也过了,楼主加油!

謝謝啦 不過我還是被拒了 可能bug的嚴重程度不一樣吧
回复 支持 反对

使用道具 举报

 楼主| tj474474 发表于 2016-10-31 12:41:03 | 显示全部楼层
freemail165 发表于 2016-10-31 12:35
题目没要求merge.
上面这个解法的问题是不能按room的使用顺序来输出。

題目沒有要求要照順序輸出
回复 支持 反对

使用道具 举报

本版积分规则

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-8-17 15:56

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表