📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
回复: 17
跳转到指定楼层
上一主题 下一主题
收起左侧

Facebook 实习两轮店面

全局:

2016(1-3月) 码农类General 硕士 实习@meta - 内推 - 技术电面  | | Pass | 应届毕业生

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

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

x
报一个FB两轮店面面经
第一轮:
1.判断有效回文串
2.decode ways
3.number of islands
其中第一题稍微改得复杂了些,第三题要求返回个数
第二轮:
给定一堆interval(如果我们管这个list叫IntervalList), 和一个target interval
我们的目标是去merge这些interval,让merge的结果能够『cover』这个target interval, 求这种merge所需的原interval的最少个数是多少

有点抽象,举个栗子
IntervalList: [-1,
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
trong>补充内容 (2017-1-25 12:24):
最终再遍历一次dp,看下curEnd是否大于targetEnd,如果是的话,就可以去更新最终的答案了
(直接也应该对达不到targetStart的interval进行特殊处理)
这样最终的复杂度是O(n^2)

评分

参与人数 10大米 +91 收起 理由
qq274880049 + 5 很有用的信息!
橙小夕 + 10 感谢分享!
dobbin + 3 感谢分享!
翻滚吧豆子 + 2 感谢分享!
玉米种植专业户 + 3 感谢分享!

查看全部评分


上一篇:Facebook 电话面试
下一篇:Airbnb Android 实习一面

本帖被以下淘专辑推荐:

全局:
cntototo 发表于 2017-2-1 06:25
感觉第二轮的题更像是greedy。先把所有intervals按start排序,然后遍历。首先我们要从那些start小于等于tar ...

可以简化一点,不用全部排序,之排序那些和target有交集的interver。然后greedy
回复

使用道具 举报

推荐
AaronD 2017-2-22 05:10:56 | 只看该作者
全局:
用greedy来做可以到O(nlogn)复杂度。
  1. def find_min_intervals(intervals, target):
  2.     intervals.sort()
  3.     res = 0
  4.     cur_target = target[0]
  5.     i = 0
  6.     max_step = 0
  7.     while i < len(intervals) and cur_target < target[1]:
  8.         while i < len(intervals) and intervals[i][0] <= cur_target:
  9.             max_step = max(max_step, intervals[i][1])
  10.             i += 1
  11.         cur_target = max_step
  12.         res += 1
  13.     return res if cur_target >= target[1] else 0
复制代码
回复

使用道具 举报

推荐
cntototo 2017-2-1 06:25:44 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
回复

使用道具 举报

🔗
icetraveller 2017-1-25 11:58:12 | 只看该作者
全局:
问下楼主第二轮是怎么做的呀
回复

使用道具 举报

🔗
king_lm 2017-1-25 12:08:34 | 只看该作者
全局:
同问第二轮
回复

使用道具 举报

🔗
qzheng93 2017-1-25 12:21:30 | 只看该作者
全局:
第二轮好像是set cover?
回复

使用道具 举报

🔗
WhatsFLAG 2017-1-26 06:57:30 | 只看该作者
全局:
第二题是求最短路径长度使用标准的bfs应该就可以了吧
回复

使用道具 举报

🔗
zhangxi1994 2017-2-20 08:41:13 | 只看该作者
全局:
第二题代码,欢迎大家指正!
  1.         public int find(Interval[] intervals, Interval target){
  2.                 if(intervals == null || intervals.length == 0) return -1;
  3.                 Arrays.sort(intervals, new Comparator<Interval>(){
  4.                         public int compare(Interval a, Interval b){
  5.                                 return a.start - b.start;
  6.                         }
  7.                 });
  8.                 int res = 0;
  9.                 int i = 0;
  10.                 int start = target.start;
  11.                 while(i < intervals.length){
  12.                         int cur = greedy(intervals, i, start);
  13.                         res++;
  14.                         if(intervals[cur].end >= target.end) return res;
  15.                         i = cur;
  16.                         start = intervals[cur].end;
  17.                 }
  18.                 return -1;
  19.         }

  20.         public int greedy(Interval[] intervals, int i, int tar){
  21.                 int res = i;
  22.                 while(i < intervals.length){
  23.                         if(intervals[i].start <= tar && intervals[i].end > intervals[res].end){
  24.                                 res = i;
  25.                         }else if(intervals[i].start > tar) return res;
  26.                         i++;
  27.                 }
  28.                 return res;
  29.         }
复制代码

补充内容 (2017-2-20 08:41):
nlogn
回复

使用道具 举报

全局:
zhangxi1994 发表于 2017-2-20 08:41
第二题代码,欢迎大家指正!

层主考虑下特殊情况,所有区间都比target区间大,这样的话层主的第一个loop是跳不出来的
回复

使用道具 举报

🔗
zhangxi1994 2017-2-21 06:59:22 | 只看该作者
全局:
英伦十六世纪 发表于 2017-2-21 05:11
层主考虑下特殊情况,所有区间都比target区间大,这样的话层主的第一个loop是跳不出来的

有道理!不过这样就没有答案了诶。那就在loop前加一行判断好了!
回复

使用道具 举报

全局:
楼主请问 第一面是 45 分钟吗? 45 分钟 3题代码都要写出来?
回复

使用道具 举报

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

本版积分规则

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