一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1244|回复: 10
收起左侧

SnapChat Full-Time 电面

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

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

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
今天下午的电面是一个国人小哥先聊了15分钟他的组 还有履历上的东西. Waral 鍗氬鏈夋洿澶氭枃绔,
然后就做题
Meeting Room ll的变化版
不是计算最少需要几个meeting room
还要把schedule的结果列出来
例如
Inputs: Meetings, [4, 9], [2, 6], [2, 3], [6, 7]
Outputs:
Room1 : [2, 3], [4, 9]. visit 1point3acres.com for more.
Room2 : [2, 6], [6, 7]

我的做法是先把所有的schedule根据start time sort
同时还用了一个PriorityQueue
顺序是根据schedule的end time.
-google 1point3acres
PriorityQueue的Node我还多放了一个该event被存放的roomId
这样从PrioirtyQueue里面pop出来的时候就可以直接找到需要添加的room
我的面試官挺好的 因為我提出這個做法
他直接就跟我說那你input就用你這個List<Node>吧

不过最后compile有个小bug
因为时间到了没弄完
还是希望有onsite...
附上代碼
  1. import java.util.*;

  2. class Node {
  3.     public int roomId;
  4.     public List<Integer> interview;
  5.     public Node(List<Integer> interview) {
  6.         this.interview = interview;
  7.     }
  8. }

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

评分

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(" ");
        }. visit 1point3acres.com for more.
        return q;
.鐣欏璁哄潧-涓浜-涓夊垎鍦    }. Waral 鍗氬鏈夋洿澶氭枃绔,

评分

1

查看全部评分

回复 支持 3 反对 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) {
        Queue q = new PriorityQueue((o1, o2) -> o ...
-google 1point3acres
好简洁的方法!把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 ...
. more info on 1point3acres.com
这个 你还得考虑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-google 1point3acres
这个 你还得考虑merge interval  [1,2] [2,4] -> [1,4]

题目没要求merge.
上面这个解法的问题是不能按room的使用顺序来输出。
. 鍥磋鎴戜滑@1point 3 acres
不知道题目是否要求
回复 支持 反对

使用道具 举报

 楼主| 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的使用顺序来输出。

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

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-4 15:16

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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