回复: 14
收起左侧

Snap新鲜出炉电面挂经...哭...求大米安慰

本楼:   👍  0
0%
0%
0   👎
全局:   119
96%
4%
5

2019(4-6月) 码农类General 硕士 全职@snapchat - Other - 技术电面  | Fail | 在职跳槽

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
似乎没有见过的题目,当天很不在状态,连brute-force的方法也没有写出来,被据在情理之中。

上题目:

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


最开始想的是greedy,然后很快发现不行。后来想着仿照minimum classroom的思路来做 - 还是greedy的思路。分析到一半还是发现不行。然后面试官让brute-force写。想着写一个dfs,但当时心态可能已经崩了,所以brute-force也没有写完。

大家有什么好的思路吗?

求大米安慰

评分

参与人数 7大米 +18 收起 理由
jlin705 + 1 很有用的信息!
清道神君 + 10
drool + 2 赞一个!
lordofone + 1 赞一个
konghaician + 1 赞一个

查看全部评分


上一篇:克鲁兹现场表演
下一篇:图钉家肮赛
desmile 2019-8-23 11:15:19 | 显示全部楼层
本楼:   👍  1
100%
0%
0   👎
全局:   81
98%
2%
2
本帖最后由 desmile 于 2019-8-23 11:16 编辑
  1. public static void main(String[] args) {
  2.         Playground pg = new Playground();
  3.         int[][] intervals1 = new int[][]{{1,3}, {4,10}, {4,6}, {9,10}};
  4.         int[][] intervals2 = new int[][]{{1,3}, {8,9}, {2,100}, {99, 300}};
  5.         System.out.println(pg.getMaxProfit(intervals1));        System.out.println(pg.getMaxProfit(intervals2));
  6.     }
  7.   
  8.     public int getMaxProfit(int[][] intervals){
  9.         Arrays.sort(intervals, (a,b) -> (a[1] - b[1]));
  10.         int n = intervals.length;
  11.         int[] dp = new int[n];
  12.         int max = 0;
  13.         for(int i = 0; i < n; i++) {
  14.             dp[i] = intervals[i][1] - intervals[i][0]; // initial value is the current interval
  15.             for(int j = 0; j < i; j++) {
  16.                 if(intervals[i][0] >= intervals[j][1]) {
  17.                     dp[i] = Math.max(dp[i], dp[j] + intervals[i][1] - intervals[i][0]); // dp[i] represents the maximum profit on if ith interval is included
  18.                     max = Math.max(max, dp[i]);
  19.                 }
  20.             }
  21.         }
  22.         return max * 100;
  23.     }
复制代码
[/i][/i][/i][/i][/i][/i][/i][/i][/i][/i]

评分

参与人数 2大米 +3 收起 理由
crazybadboy + 2 很有用的信息!
nlackx + 1 很有用的信息!

查看全部评分

回复

使用道具 举报

nlackx 2019-10-29 09:12:44 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   98
100%
0%
0
思路
对于任意一个interval,以它结尾的合理schedule的所有可能性是:它自己加上比他早结束的任意0个,1个或多个 intervals。
因为所有interval的时间跨度都是正数,所以可以贪心地认为以某个interval结束的schedule所包含的intervals最多的那个就代表了以它结束的最大收益。
为了方便地找比当前结束更早的interval,我们可以按interval 结束的时间从小到大排序(开始时间怎么排都无所谓)。

code
  1. class Solution {
  2.     public int maxProfitAirBnb(int[][] reservations) {
  3.         Arrays.sort(reservations, ((o1, o2) -> o1[1] - o2[1]));
  4.         
  5.         int res = 0;
  6.         int[] memo = new int[reservations.length];

  7.         for (int i = 0; i < reservations.length; i++) {
  8.             int max = 0;
  9.             for (int j = 0; j < i; j++) {
  10.                 if (reservations[j][1] <= reservations[i][0]) {
  11.                     max = Math.max(max, memo[j]);
  12.                 }
  13.             }
  14.             memo[i] = max + (reservations[i][1] - reservations[i][0]);
  15.             res = Math.max(res, memo[i]);
  16.         }

  17.         return res * 100;
  18.     }
  19. }
复制代码

扫码关注一亩三分地求职移民公众号
更多干货内容等你发现
回复

使用道具 举报

GenesisXXX 2019-5-17 11:37:14 来自APP | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   103
98%
2%
2
猜dp?sort by end time first
回复

使用道具 举报

 楼主| user123456 2019-5-17 11:46:15 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   119
96%
4%
5
GenesisXXX 发表于 2019-5-17 11:37
猜dp?sort by end time first

当时写dfs的时候,也有想着加一个memoization,但不知道memoize什么,或者说dp的公式是什么
回复

使用道具 举报

x1111 2019-5-17 12:35:49 来自APP | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   16
100%
0%
0
对所有的reversation每天都是100?还是不同的给不同的价格
回复

使用道具 举报

tipoup2011 2019-5-17 12:58:19 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   0
0%
0%
0
先根据end sort,[s1,e1], [s2,e2]...[si,ei]...,然后dp[i]代表截止到第i天的结果,dp[i]只有当i属于e的时候再更新,否则就等于dp[上一个e]的结果因为反正也没法租出去。当i属于e的时候,假设等于ej, 那么过一遍所有interval以ej结尾的,看他们要不要租,大概就是dp[i] = max(dp[i] (不租), (ej-sj)*100 + dp[sj-1] (租))。这样行吗
回复

使用道具 举报

shwanfan 2019-5-17 13:30:58 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   9
100%
0%
0
好奇呀. snap现在行业内的地位如何呢?
回复

使用道具 举报

的萨菲 2019-5-17 13:33:20 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   102
98%
2%
2
和meeting room有什么区别吗?应该就是只有一个房间然后尽可能多的安排meeting吧。我想的是按照start 排序,然后看下一个的start有没有和当下的end冲突,不知道这个思路怎么样?
回复

使用道具 举报

foryou 2019-5-17 13:42:07 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   14
100%
0%
0
  1. public class MaxIncome {
  2.     public static int solution(int[][] intervals) {
  3.         Arrays.sort(intervals, (o1, o2) -> (o1[1] - o2[1]));
  4.         int[] dp = new int[intervals[intervals.length - 1][1] + 1];
  5.         dp[0] = 0;
  6.         int max = 0;
  7.         for (int[] interval : intervals) {
  8.             int from = interval[0];
  9.             int to = interval[1];
  10.             int before = 0;
  11.             for (int i = 0; i < from; i++) {
  12.                 before = Math.max(dp[i], before);
  13.             }
  14.             dp[to] = Math.max(dp[to], to - from + 1 + before);
  15.             max = Math.max(dp[to], max);
  16.         }
  17.         return max * 100;
  18.     }

  19.     public static void main(String[] args) {
  20.         int[][] intervals = new int[][]{{1, 5}, {3, 7}, {6, 8}};
  21.         System.out.println(MaxIncome.solution(intervals));
  22.     }
  23. }
复制代码


按照楼上的思路写了一个...

评分

参与人数 1大米 +2 收起 理由
maxnima + 2 给你点个赞!

查看全部评分

回复

使用道具 举报

foryou 2019-5-17 13:51:09 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   14
100%
0%
0
的萨菲 发表于 2019-5-17 13:33
和meeting room有什么区别吗?应该就是只有一个房间然后尽可能多的安排meeting吧。我想的是按照start 排序 ...

这个不行, 这个方法就是贪心, 等于选择当前的meeting, 否决下一个meeting. 例如 1-3, 2-100, 4-5 会得出1-3, 4-5这个组合
回复

使用道具 举报

 楼主| user123456 2019-5-17 14:33:47 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   119
96%
4%
5
x1111 发表于 2019-5-17 12:35
对所有的reversation每天都是100?还是不同的给不同的价格

价格都是一样的:1天100
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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