一亩三分地论坛

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

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

[找工就业] yelp phone 面经

[复制链接] |试试Instant~ |关注本帖
ann0612 发表于 2015-11-23 12:48:02 | 显示全部楼层 |阅读模式

2015(10-12月)-[14]CS硕士+fresh grad 无实习/全职 - 校园招聘会| 码农类全职@Yelpfresh grad应届毕业生

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

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

x
上周三面了yelp 来报个面经 是个印度小哥 交流微微有点儿障碍 偶尔需要重复几次 1. why webpage load low?
       我的答案:  1. check network connection 2. check 图片/ CSS /JS 等太多了 3. check ddos
2. 给定一组Array 表示每个起始位置和线段长度 {[1,2],[2,5],[3,6],[5,8],[6,10]}  return 不重复的线段最多的条数。例子 return 3
这个题 最开始没有理解清楚他的意思  当成线段树 去做了 并没有做出来。
感觉跪了。

评分

2

查看全部评分

ningchris 发表于 2015-11-24 09:51:39 | 显示全部楼层
写了个dfs 但是觉得非常不efficient
. more info on 1point3acres.com. Waral 鍗氬鏈夋洿澶氭枃绔,
  1. def maxUniqueLines(array):
  2.     toRet = []
  3.     dfs(toRet,[],array)
  4.     num = 0
  5.     if toRet:
  6.         for i in toRet:
  7.             num = max(len(i),num)
  8.     return num
  9.    
  10. def dfs(toRet,temp,array):
  11.     for i in range(len(array)):. from: 1point3acres.com/bbs
  12.         if temp:
  13.             if temp[-1][-1] <= array[i][0]:
  14.                 temp.append(array[i])
  15.                 toRet.append(temp[::])
  16.         else:
  17.             temp.append(array[i]). 1point3acres.com/bbs
  18.         dfs(toRet,temp[::],array[i+1:]).鏈枃鍘熷垱鑷1point3acres璁哄潧
  19.         temp.pop()
复制代码
回复 支持 0 反对 1

使用道具 举报

ningchris 发表于 2015-11-23 23:20:55 | 显示全部楼层
求面试官first name
回复 支持 反对

使用道具 举报

ningchris 发表于 2015-11-23 23:51:53 | 显示全部楼层
还有楼主可以讲一下第二题吗?
我不是太明白
不重复是指区间 不重叠或者区间刚刚好交接 对吧?
回复 支持 反对

使用道具 举报

 楼主| ann0612 发表于 2015-11-24 00:49:41 | 显示全部楼层
ningchris 发表于 2015-11-23 23:51
还有楼主可以讲一下第二题吗?
我不是太明白
不重复是指区间 不重叠或者区间刚刚好交接 对吧?

shi zhege yisi
回复 支持 反对

使用道具 举报

ningchris 发表于 2015-11-24 00:52:15 | 显示全部楼层

感谢!!!!!!!!!!
回复 支持 反对

使用道具 举报

ningchris 发表于 2015-11-24 00:58:16 | 显示全部楼层

还有一个问题
根据这个理解 以上的那道题 是哪三条线段不重复呢?
回复 支持 反对

使用道具 举报

silenceleaf 发表于 2015-11-24 03:33:03 | 显示全部楼层
ningchris 发表于 2015-11-24 00:58
还有一个问题
根据这个理解 以上的那道题 是哪三条线段不重复呢?
. more info on 1point3acres.com
怎么看都只有两个啊,[1,2][3,6] 怎么会有三个
回复 支持 反对

使用道具 举报

 楼主| ann0612 发表于 2015-11-24 05:40:59 | 显示全部楼层
ningchris 发表于 2015-11-24 00:58
还有一个问题
根据这个理解 以上的那道题 是哪三条线段不重复呢?

[1,2][2,5][5,8]-google 1point3acres
或者
[1,2][2,5][5,10]

补充内容 (2015-11-24 05:41):. Waral 鍗氬鏈夋洿澶氭枃绔,
第二个是【1,2】【2,5】【6,10】
回复 支持 反对

使用道具 举报

 楼主| ann0612 发表于 2015-11-24 05:43:17 | 显示全部楼层
ningchris 发表于 2015-11-24 00:58
还有一个问题
根据这个理解 以上的那道题 是哪三条线段不重复呢?
. 鍥磋鎴戜滑@1point 3 acres
[1,2][2,5][5,8]
[1,2][2,5][6,10]

估计要用DFS 挺麻烦的感觉 yelp题不是一般都挺简单的嘛, 哪位同学给个解法?. 鍥磋鎴戜滑@1point 3 acres

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

ningchris 发表于 2015-11-24 06:35:02 | 显示全部楼层
ann0612 发表于 2015-11-24 05:43
[1,2][2,5][5,8]
[1,2][2,5][6,10]

懂了 感觉好像只有DFS 可以做啊
回复 支持 反对

使用道具 举报

silenceleaf 发表于 2015-11-24 08:32:38 | 显示全部楼层
ann0612 发表于 2015-11-24 05:43. from: 1point3acres.com/bbs
[1,2][2,5][5,8]
[1,2][2,5][6,10]

楼主请问如果[1,2][2,5][5,8], 第二条线段从2开始,可是第一条是1到3, 不是有overlap吗??
回复 支持 反对

使用道具 举报

yejingxin 发表于 2015-12-18 17:05:37 | 显示全部楼层
第二题用dp做?O(n log n) in time, O(n) in space

对线段按tail排序,对于第k条线段,f(k) 表示 从开头到 k线段结尾最多有多少nonoverlaping线段,接下来找f(k) 与之前 f(0, ...., k-1) 的关系, 分两种情况-google 1point3acres

1. 第k条线段没有被包含在f(k) 中, 那么f(k) = f(k - 1)

2. 第k条线段被包含在f(k) 中, 那么 f(k) = 1 + f(j), 其中的第j条线段tail,恰好在第k条线段head之前, j = max (i)  where interval.tail <= interval[k].head, j可以用binary search来找

所以 f(k) = max(f(k-1), 1 + f(j))

f(n - 1)即为所求
  1. class Solution{. more info on 1point3acres.com
  2.         public int maxNumOfNonOverlapInteval(ArrayList<Interval> intervals) {
  3.                 Comparator<Interval> endComparator = new Comparator<Interval> () {
  4.                         public int compare (Interval i1, Interval i2) {
  5.                                 if (i1.end != i2.end) {
  6.                                         return i1.end - i2.end;
  7.                                 }
  8.                                 return i1.start - i2.start;
  9.                         }
  10.                 };
  11.                 Collections.sort(intervals, endComparator);
    -google 1point3acres
  12.                 int[] result = new int[intervals.size()];.1point3acres缃
  13.                 result[0] = 1;
  14.                 for (int i = 1; i < intervals.size(); i++) {
  15.                         result[i] = result[i - 1];
  16.                         int index = binarySearch(intervals, intervals.get(i).start);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  17.                         if (index != -1) {. 鍥磋鎴戜滑@1point 3 acres
  18.                                 result[i] = Math.max(result[i - 1], result[index] + 1);
    . more info on 1point3acres.com
  19.                         }
  20.                         System.out.println(result[i]);
  21.                 }
  22.                 return result[intervals.size() - 1];. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

  23.         }. 1point 3acres 璁哄潧
  24.         int binarySearch(ArrayList<Interval> intervals, int start) {
  25.                 int left = 0;
  26.                 int right = intervals.size() - 1;
  27.                 while (left < right - 1) {
  28.                         int mid = (right - left) / 2 + left;. 1point 3acres 璁哄潧
  29.                         if (intervals.get(mid).end <= start) {
  30.                                 left = mid;
  31.                         } else {
  32.                                 right = mid;
  33.                         }
  34.                 }
  35.                 if (intervals.get(right).end <= start) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  36.                         return right;
  37.                 } else if (intervals.get(left).end <= start) {
  38.                         return left;
  39.                 }
  40.                 return -1;. from: 1point3acres.com/bbs
  41.         }. visit 1point3acres.com for more.
  42. }

  43. class Interval {
  44.         int start;
  45.         int end;
  46.         Interval(int start, int end) {
  47.                 this.start = start;
  48.                 this.end = end;. from: 1point3acres.com/bbs
  49.         }
  50. }
复制代码
回复 支持 反对

使用道具 举报

yyboyz 发表于 2016-1-12 12:21:07 | 显示全部楼层
楼主你应该想说区间是 [起点,终点]吧?. from: 1point3acres.com/bbs
怎么会是[起点,线段长度]
回复 支持 反对

使用道具 举报

yyboyz 发表于 2016-1-12 12:41:27 | 显示全部楼层
yejingxin 发表于 2015-12-18 17:05
. 1point3acres.com/bbs第二题用dp做?O(n log n) in time, O(n) in space

对线段按tail排序,对于第k条线段,f(k) 表示 从开头 ...

不错的dp解法
回复 支持 反对

使用道具 举报

seblsb 发表于 2016-1-13 09:38:39 | 显示全部楼层
yejingxin 发表于 2015-12-18 17:05
第二题用dp做?O(n log n) in time, O(n) in space

对线段按tail排序,对于第k条线段,f(k) 表示 从开头 ...

很好的解法~
回复 支持 反对

使用道具 举报

David.S 发表于 2016-1-20 07:12:13 | 显示全部楼层
貌似用greddy 可以做,根据线段的结束位置排序,每次找最早的开始位置
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 03:59

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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