一亩三分地论坛

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

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

Facebook 电面面经

[复制链接] |试试Instant~ |关注本帖
疯狂猎手 发表于 2016-10-1 03:20:55 | 显示全部楼层 |阅读模式

2017(1-3月) 码农类 硕士 全职@Facebook - 网上海投 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
几分钟前刚面完fb的一面,一个美国大哥,上来嘚吧嘚吧了一通他们组做啥他干啥的,问了简历的一个外包项目,可能他是做前端的所以问了这个。之后直接做题。
给很多points (e.g. (1, 2), (4, 5),.....),再给一个int k,返回k个离原点最近的点的坐标。


当时我直接就brute force,之后follow up时间复杂度和空间复杂度能否优化。最后想了想,维护了一个k的heap,只提升了空间,时间还是nlogn没变。答得实在不咋地,时间复杂度一开始还答错了。 不敢求onsite了,求有个二面就行。。。

. From 1point 3acres bbs



补充内容 (2016-10-4 09:22):
运气好~刚刚收到HR邮件通知Onsite~
tank_z 发表于 2016-10-1 03:35:33 | 显示全部楼层
用heap的话时间复杂度是nlogk吧
回复 支持 反对

使用道具 举报

 楼主| 疯狂猎手 发表于 2016-10-1 04:19:58 | 显示全部楼层
tank_z 发表于 2016-10-1 03:35
用heap的话时间复杂度是nlogk吧

对对 我写错了 是nlogK
回复 支持 反对

使用道具 举报

citiy 发表于 2016-10-1 06:08:28 | 显示全部楼层
记得楼主简历被拒,后来是地里那位大哥推的成功了,恭喜
回复 支持 反对

使用道具 举报

萌萌软妹子 发表于 2016-10-1 09:22:05 | 显示全部楼层
哈哈哈又是这个高频题
回复 支持 反对

使用道具 举报

DreamBoy 发表于 2016-10-3 01:11:12 | 显示全部楼层
怎么fix的heap size。。。没办法fix成k啊
回复 支持 反对

使用道具 举报

Acex 发表于 2016-10-3 01:48:44 | 显示全部楼层
DreamBoy 发表于 2016-10-3 01:11
怎么fix的heap size。。。没办法fix成k啊

if (heap.size() > k) heap.poll() 找最大用minHeap找最小用maxHeap
回复 支持 反对

使用道具 举报

yazuibi 发表于 2016-10-3 06:34:05 | 显示全部楼层
如果用quickselect算法先找出离原点距离第k近的点和距离,然后再把原数组扫一遍和这个距离比较,如果小于该距离则放入结果数组,等于该距离则放入另一个数组最后从里面选出一些补满k个,这样的空间复杂度和时间复杂度都是O(n)。不知道这种解法有没有什么问题?
回复 支持 反对

使用道具 举报

DreamBoy 发表于 2016-10-3 07:41:09 | 显示全部楼层
yazuibi 发表于 2016-10-3 06:34. 1point 3acres 璁哄潧
如果用quickselect算法先找出离原点距离第k近的点和距离,然后再把原数组扫一遍和这个距离比较,如果小于该 ...

用heap space是O(K)吧?虽然O(n log(k))大一点但是space感觉比较重要一些 毕竟k<<n大多数情况
回复 支持 反对

使用道具 举报

Acex 发表于 2016-10-3 10:57:41 | 显示全部楼层
DreamBoy 发表于 2016-10-3 07:41
用heap space是O(K)吧?虽然O(n log(k))大一点但是space感觉比较重要一些 毕竟k

quick select可以in place解决,空间O(1)似乎就可以。除了时间复杂度worst case是O(n^2)外,感觉是一个不错的方法。
回复 支持 反对

使用道具 举报

Acex 发表于 2016-10-3 10:59:35 | 显示全部楼层
Acex 发表于 2016-10-3 10:57
quick select可以in place解决,空间O(1)似乎就可以。除了时间复杂度worst case是O(n^2)外,感觉是一个不 ...

不过comparator应该比quick select好写吧个人感觉。
回复 支持 反对

使用道具 举报

yazuibi 发表于 2016-10-3 12:32:43 | 显示全部楼层
Acex 发表于 2016-10-3 10:57
quick select可以in place解决,空间O(1)似乎就可以。除了时间复杂度worst case是O(n^2)外,感觉是一个不 ...

. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷是的,谢谢更正~
回复 支持 反对

使用道具 举报

yazuibi 发表于 2016-10-3 12:34:07 | 显示全部楼层
DreamBoy 发表于 2016-10-3 07:41 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
用heap space是O(K)吧?虽然O(n log(k))大一点但是space感觉比较重要一些 毕竟k

可以和面试官说如果k比较小用heap,如果k比较大用quick select
回复 支持 反对

使用道具 举报

DreamBoy 发表于 2016-10-3 12:34:32 | 显示全部楼层
Acex 发表于 2016-10-3 10:57
quick select可以in place解决,空间O(1)似乎就可以。除了时间复杂度worst case是O(n^2)外,感觉是一个不 ...

不可能in place input是点不是距离
回复 支持 反对

使用道具 举报

A_rain 发表于 2016-10-4 08:21:33 | 显示全部楼层
这道题应该是最优 Klog(n) 吧,,Klog(n) 优于Nlog(k)因为k <= n.    直接把所有点放进heap, 取k个出来就行。
回复 支持 反对

使用道具 举报

LumiG 发表于 2016-10-7 02:06:25 | 显示全部楼层
A_rain 发表于 2016-10-4 08:21
这道题应该是最优 Klog(n) 吧,,Klog(n) 优于Nlog(k)因为k
-google 1point3acres
放进去就nlgn了
回复 支持 反对

使用道具 举报

minggr 发表于 2016-10-12 14:27:38 | 显示全部楼层
DreamBoy 发表于 2016-10-3 12:34
不可能in place input是点不是距离

一样in place, 写一个如下:
  1. struct point {. visit 1point3acres.com for more.
  2.     int x, y;
  3. };.鐣欏璁哄潧-涓浜-涓夊垎鍦

  4. bool compare(vector<point> &points, int i, int j)
  5. {
  6.     return (points[i].x * points[i].x + points[i].y * points[i].y) >
  7.            (points[j].x * points[j].x + points[j].y * points[j].y);
  8. }

  9. int random_partition(vector<point> &points, int start, int end). from: 1point3acres.com/bbs
  10. {
  11.     int p;
  12. . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  13.     p = start + rand() % (end - start + 1);
  14.     if (p != end)
  15.         swap(points[p], points[end]);

  16.     int i = start;
  17.     while (start <= end) {
  18.         if (start == end || compare(points, i, start))
  19.             swap(points[i++], points[start]);. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  20.         start++;
  21.     }

  22.     return i - 1;
  23. }
  24. . visit 1point3acres.com for more.
  25. vector<point> quick_select(vector<point> &points, int k)
  26. {
  27.     int start = 0;
  28.     int end = (int)points.size() - 1;

  29.     while (start <= end) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  30.         int index = random_partition(points, start, end);

  31.         if (index == k -1). 1point 3acres 璁哄潧
  32.             break;
  33.         else if (index > k - 1)
  34.             end = index - 1;
  35.         else
  36.             start = index + 1;
  37.     }. From 1point 3acres bbs

  38.     vector<point> result;
  39.     while (k > 0) {
  40.         result.push_back(points[k-1]);
  41.         k--;
  42.     }
  43. .鏈枃鍘熷垱鑷1point3acres璁哄潧
  44.     return result;. Waral 鍗氬鏈夋洿澶氭枃绔,
  45. }

  46. int main()
  47. {
  48.     vector<point> points = {{3, 3}, {1, 2}, {-1, 1}, {-1, -3}, {-1, -1}};.鏈枃鍘熷垱鑷1point3acres璁哄潧

  49.     int k = 2;
  50.     vector<point> result = quick_select(points, k);. 1point 3acres 璁哄潧

  51.     for (point p: result)
  52.         cout << p.x << ", " << p.y << endl;

  53.     return 0;
  54. }
复制代码
回复 支持 反对

使用道具 举报

西法的洛 发表于 2016-10-12 21:50:04 | 显示全部楼层

建堆的复杂度是O(n)吧,然后你取出来k个,复杂度应该是O(n + k log n)
回复 支持 反对

使用道具 举报

西法的洛 发表于 2016-10-12 21:57:10 | 显示全部楼层
看了楼上的解法,总结一下,欢迎指正:
维护一个大小为k的heap,时间复杂度O(nlogk),空间复杂度O(k)
建个大小为n的堆,然后取k次,时间复杂度O(n + k log n), 空间复杂度O(n).鐣欏璁哄潧-涓浜-涓夊垎鍦
quick select方法,时间复杂度O(n + n) = O(n), 空间复杂度O(1). visit 1point3acres.com for more.
k 很大时 quick select办法比较好,k很小时候维护大小为k的堆比较好
回复 支持 反对

使用道具 举报

西法的洛 发表于 2016-10-12 22:59:10 | 显示全部楼层
我也写了个二维快排的,欢迎指正。public double partition(Point[] points, int i, int j, int k) {
    int start = i;
    int pivot = j;
    int end = j - 1;
    while (start <= end) {
        if (points[start].compareTo(points[pivot]) == 1) {
            Point tmp = points[end];
            points[end--] = points[start];
            points[start] = tmp;
        } else {
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴            start++;-google 1point3acres
        }
    }
    Point tmp = points[start];. From 1point 3acres bbs
    points[start] = points[pivot];
    points[pivot] = tmp;
. 鍥磋鎴戜滑@1point 3 acres
    int rank = start + 1;
    if (rank == k) return getDistance(points[start]);. Waral 鍗氬鏈夋洿澶氭枃绔,
    else if (rank < k) return partition(points, start + 1, j, k);. 1point 3acres 璁哄潧
    else return partition(points, i, start - 1, k);-google 1point3acres
}

public double getDistance(Point p) {
    return Math.sqrt(p.x * p.x + p.y * p. y);
}.鏈枃鍘熷垱鑷1point3acres璁哄潧
. 1point3acres.com/bbs
public void retrieveKNear(Point[] points, int k) {
    double distance = partition(points, 0, points.length - 1, k);.1point3acres缃
    for (Point point : points) {
        if (getDistance(point) <= distance) System.out.println(point);
    }
}
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 13:45

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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