仅限周四-周六三天
戳这里:一年VIP通行证额外打折$70,半年额外打折$30
戳这里:learn.1point3acres.com选课超过$500+折扣码thanks1p3a -> 15% off

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

有你有策略
微策略(MicroStrategy)
2019校园招聘火热进行中
E轮2.5亿美元融资
K12教育独角兽一起作业诚聘
机器学习/数据统计/教育等职位
码农求职神器Triplebyte:
不用海投
内推多家公司面试
高效直聘+内推,70%面试率
AI帮你免费完善简历
直击全美十万个科技职位
坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
把贵司招聘信息放这里
查看: 710|回复: 10
收起左侧

脸书电面不知道这个题有人见过么

[复制链接] |试试Instant~
我的人缘0
stonepeter 发表于 2018-11-10 07:32:54 | 显示全部楼层 |阅读模式
本楼: 【顶】   100% (2)
 
 
0% (0)   【踩】
全局: 顶  100% (9)
 
 
0% (0)  踩

2018(10-12月) MachineLearningEng 本科 全职@Facebook - 猎头 - 技术电面  | Other | 在职跳槽

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

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

x

题目就一道,要求后来优化时间和性能。
[hide=120]给两个数组,求所有数对的差值绝对值的总和[/120]
先是实现O(M*N)的复杂度。之后要求改进优化。
思路是先排序,然后再用二分查找第一数组里的数在第二个数组出现的位置,比第一个数组里的数小的单独计算,比第一个数组里的数大的单独计算。
我思路想出来了,代码的也写了,不过最后有个小BUG,另外二分查找的算法本来要我写,也没有时间写了。

估计已经跪了。


. 1point3acres
游客,本帖隐藏的内容需要积分高于 188 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.
-1], F(A,B) = 1+4+6 + 4+9+1 = 25. 1point3acres

补充内容 (2018-11-11 13:48):
大米,更新了我当时的思路给大家参考。

评分

参与人数 6大米 +26 收起 理由
cfgx + 3 很有用的信息!
TTTynthia + 5 给你点个赞!
gui59106375 + 5 给你点个赞!
say543 + 3 很有用的信息!
spinova + 5 很有用的信息!
zy16373soup + 5 很有用的信息!

查看全部评分


上一篇:狗狗new grad技术店面经经经
下一篇:图森一面
我的人缘0
 楼主| stonepeter 发表于 2018-11-11 13:41:14 | 显示全部楼层
本楼: 【顶】   100% (3)
 
 
0% (0)   【踩】
全局: 顶  100% (9)
 
 
0% (0)  踩
看到下面有同学很认真的回复,我还是把我当时的思路仔细写写吧。
1、对B数组排序(时间复杂度O(m*log(m))
2、对A数组的每个数,在排好序的B数组中进行二分查找,从二分查找的位置对数组B进行分两半(时间复杂度O(n*log(m))
3、用O(m)的空间和O(n)的时间保存B数组的和,用于快速计算
4、对步骤2中的两半分别进行求和运算,因为左边一半(一共有k个)小于A数组的当前数a,所以|a-b|=a-b,求和的时候就变成了k*a - sum(B[:k]),而右边一半(一共有m-k个),这些数都大于或者等于当前数a,所以|a-b|=b-a,求和的时候就变成了sum(B[k:]) - (m-k-1) * a
4.1、关于求和的说明,因为在步骤3中已经保存过B的局部和了sum_b[i] = sum(B[:i]),所以左边一半的求和实际上是sum(B[:k])=sum_b[k], 而右边的一半求和是sum[k:]=sum_
游客,本帖隐藏的内容需要积分高于 10 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.
找到了更优的解法,可以要求完成这个解法,这里最大的坑就是如果不熟悉的话可能想不起保存区部求和这个改进时间性能的做法,再一方面,如果被面的人能在三十分钟的时间内想到这个方法而且能没有BUG的写出来,的确会让人高看一线,尤其是在LEETCODE上没有原题的情况下。
回复

使用道具 举报

我的人缘0
becoo 发表于 2018-11-10 12:21:37 来自一亩三分地官方APP | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  100% (24)
 
 
0% (0)  踩
看上去有戏啊
游客,本帖隐藏的内容需要积分高于 10 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.
。。
回复

使用道具 举报

我的人缘0
xiebw 发表于 2018-11-10 09:12:29 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  90% (79)
 
 
9% (8)  踩
游客,本帖隐藏的内容需要积分高于 10 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.然后用短的数组的元素在长数组里面查找
回复

使用道具 举报

我的人缘0
鱼淼淼 发表于 2018-11-10 15:16:10 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  88% (15)
 
 
11% (2)  踩
lz这题可以举个例子
游客,本帖隐藏的内容需要积分高于 10 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.
是很理解
回复

使用道具 举报

我的人缘0
edyyy 发表于 2018-11-10 22:33:23 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  90% (171)
 
 
9% (17)  踩
好像没见这题。。。。。。。游客,本帖隐藏的内容需要积分高于 10 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.="0" alt="" />
回复

使用道具 举报

我的人缘0
 楼主| stonepeter 发表于 2018-11-11 01:31:44 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (9)
 
 
0% (0)  踩
# Given 2 arrays A,B # F(A,B) # consider all pairs (a,b) such that a is in A, b is in B # F(A,B) = sum |a-b| over al
游客,本帖隐藏的内容需要积分高于 10 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.
(of size n) # F(A,B) = 1+4+6 + 4+9+1 = 25
回复

使用道具 举报

我的人缘0
hbs198 发表于 2018-11-11 12:51:35 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (4)
 
 
0% (0)  踩
(1) 假设大数组m个数,小数组n个数, 先对小数组进行排序设为b1,b2,...,bn,这样把数轴分成了n+1个区间[-inf,b1],[b1,b2],...,[bn,+inf]

(2) 假设f(x)=|x-b1|+|x-b2|+...+|x-bn|, f(x)在每个区间都是线性函数f(x)=ax+b但是参数a,b不一样,计算出每个区间的参数a和b。
游客,本帖隐藏的内容需要积分高于 10 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.
(nlog n)+m个数二分查找O(m log n) = O[(m+n)log n]
空间复杂度为 O(m): 用来存参数ab
回复

使用道具 举报

我的人缘0
 楼主| stonepeter 发表于 2018-11-11 13:44:01 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (9)
 
 
0% (0)  踩
hbs198 发表于 2018-11-11 12:51
(1) 假设大数组m个数,小数组n个数, 先对小数组进行排序设为b1,b2,...,bn,这样把数轴分成了n+1个区间[-in ...

谢谢分析。其实当时面试官已经很友好地把公式|a-b|定义单独写出来了。|a-b|==(a-b) if a>=b, else (b-a)。他这样写出来对分析和思考很有帮助。

With React+D3v4 you'll learn the basics of building fast data visualization components in about an hour.


回复

使用道具 举报

我的人缘0
redbeanlyx 发表于 2018-11-12 04:56:07 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (1)
 
 
0% (0)  踩
A = [3,8,2], B = [4, -1], F(
游客,本帖隐藏的内容需要积分高于 10 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.
不是给错了 绝对值之和
回复

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法 - 不要多加空格: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|小黑屋|联系我们&一亩三分地论坛声明

GMT+8, 2018-11-22 19:38

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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