一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推多家公司面试
Airbnb 数据科学职位
in analytics and inference
游戏初创公司
招聘工程师、Designer和游戏策划
游戏初创公司DreamCraft招聘工程师、UIUX Designer和游戏策划
电商初创公司Good Days
招聘SDE/UI/TPM实习生
把贵司招聘信息放这里
查看: 2163|回复: 33
收起左侧

9月G 昂赛

[复制链接] |试试Instant~ |关注本帖
haifengc 发表于 2017-10-28 05:40:48 | 显示全部楼层 |阅读模式

2017(7-9月) 码农类 博士 全职@Google - 猎头 - Onsite |Pass在职跳槽

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

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

x

. 1point 3acres 璁哄潧
第一轮:
给n个三角形,三角形的三个顶点分别用大于零的自然数表示
比如
三角形一  1,3,5
三角形二  2, 9, 10
三角形三  11, 23, 3
三角形四  3,5,11. Waral 鍗氬鏈夋洿澶氭枃绔,
...
要求输出一个图
每个三角形代表图中的一个节点,如果两个三角形有公共的边,则两个对应的节点之间存在一条路径(可以是一条边或者连通的路径). 1point3acres.com/bbs
比如三角形一和三角形四有公共边3,5,则在所建的图里,三角形一和三角形四对应的节点需要连通
.鏈枃鍘熷垱鑷1point3acres璁哄潧

第二轮:
李德克 私酒. 鍥磋鎴戜滑@1point 3 acres
李德克 而把衣

第三轮:
中序遍历二叉树中第k个的节点
每个节点记录了所在子树的节点的个数


第四轮:
给一个长度为n的数组,把数组分为k段,每段至少一个数
每段内的数俩俩相乘的和作为这段的权重,求如何划分数组使得所有段的权重之和最大
比如数组是这样的
[1, 2, 32, 7, 2, 23, 3, 4, 32, 2]
k是3

如果这样划分
[1, 2, 32, 7,   |   2, 23, 3,   |   4, 32, 2]. 1point 3acres 璁哄潧

第一段的权重 s1 = 1 * 2 + 1 * 32 + 1 * 7 + 2 * 32 + 2 * 7 + 32 * 7
第二段的权重 s2 = 2 * 23 + 2 * 3 + 23 * 3
第三段的权重 s3 = 4 * 32 + 4 * 2 + 32 * 2
所有权重的和则是 s = s1 + s2 + s3
返回最大可能得到的所有权重的和s
不需要返回怎么划分,只需要返回最大的和
. Waral 鍗氬鏈夋洿澶氭枃绔,

第五轮:
第一题
(1) 判断两条一维的线段是否相交
(2) 返回两条一维的线段相交的长度
(3) 返回两个二维矩阵相交的面积
第二题
李德克 丝霸气
.鐣欏璁哄潧-涓浜-涓夊垎鍦

评分

5

查看全部评分

本帖被以下淘专辑推荐:

 楼主| haifengc 发表于 2017-11-11 09:08:22 | 显示全部楼层
weiliango 发表于 2017-11-11 03:55
求教一下楼主第三题的题干,没有看明白。。。已加大米
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
就是给一颗二叉树,
树的每个节点有一个integer field,记录的是以这个节点为root的subtree的节点的个数

然后,求整棵树按中序遍历的第k个node

谢谢你的大米啊

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

大懒懒一休哥 发表于 2017-10-28 06:10:01 | 显示全部楼层
第一题楼主怎么做的啊?
回复 支持 反对

使用道具 举报

 楼主| haifengc 发表于 2017-10-28 06:11:02 | 显示全部楼层
大懒懒一休哥 发表于 2017-10-28 06:10. from: 1point3acres.com/bbs
第一题楼主怎么做的啊?

用的HashMap
把每条边对应的三角形放一起,然后再连起来
回复 支持 反对

使用道具 举报

fledgling 发表于 2017-10-28 07:36:59 | 显示全部楼层
请问楼主(4)是三维的区间DP解法么?
回复 支持 反对

使用道具 举报

m1n2b3v4 发表于 2017-10-28 07:48:40 | 显示全部楼层
恭喜!请问lz onsite 到hc的timeline是什么呀谢谢了!!
回复 支持 反对

使用道具 举报

 楼主| haifengc 发表于 2017-10-28 09:13:17 | 显示全部楼层
fledgling 发表于 2017-10-28 07:36
请问楼主(4)是三维的区间DP解法么?

2维可以的
回复 支持 反对

使用道具 举报

 楼主| haifengc 发表于 2017-10-28 09:14:08 | 显示全部楼层
m1n2b3v4 发表于 2017-10-28 07:48. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
恭喜!请问lz onsite 到hc的timeline是什么呀谢谢了!!

谢谢, 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
还没有HC
面完两周说要先team match
然后再hc
match了一个月,至今没有人理
回复 支持 反对

使用道具 举报

fledgling 发表于 2017-10-28 09:56:31 | 显示全部楼层

多谢楼主!
回复 支持 反对

使用道具 举报

hzyfree 发表于 2017-10-28 10:05:30 | 显示全部楼层
求问第四轮有O(N2)的做法吗? 我只想到了O(N3)的做法...
回复 支持 反对

使用道具 举报

 楼主| haifengc 发表于 2017-10-28 10:08:43 | 显示全部楼层
我当时想到的就是O(n^2 * k)的方法,
应该有更好一点的,没有时间,就先写了这个代码,后来代码写完,时间也到了. Waral 鍗氬鏈夋洿澶氭枃绔,
回复 支持 反对

使用道具 举报

春山寒 发表于 2017-10-30 04:04:37 | 显示全部楼层
第四题 vector 里的数 是可正可负吗
回复 支持 反对

使用道具 举报

 楼主| haifengc 发表于 2017-10-30 05:19:35 | 显示全部楼层
春山寒 发表于 2017-10-30 04:04
第四题 vector 里的数 是可正可负吗

应该都可以吧,
对算法没有什么影响
回复 支持 反对

使用道具 举报

billyli8866 发表于 2017-10-30 06:40:55 | 显示全部楼层
第五轮是不是应该是二维矩形呀? 二维矩阵相交是什么?
回复 支持 反对

使用道具 举报

weixinding 发表于 2017-10-30 06:48:24 | 显示全部楼层
haifengc 发表于 2017-10-30 05:19
应该都可以吧,
对算法没有什么影响

有的,保证是正数有O(nk)的做法
回复 支持 反对

使用道具 举报

 楼主| haifengc 发表于 2017-10-30 10:29:40 | 显示全部楼层
weixinding 发表于 2017-10-30 06:48
有的,保证是正数有O(nk)的做法

讲讲,没有想过,
回复 支持 反对

使用道具 举报

weixinding 发表于 2017-10-30 14:18:04 | 显示全部楼层
haifengc 发表于 2017-10-30 10:29
讲讲,没有想过,

说错了,好像没有要求。。不过复杂度在O(knlog(n))
记a为原数组,sum表示数组前i个元素的前缀和,即sum = \sigma_{j=0..i}{a[j]}。
你可以认为一开始所有元素都在一个段里,然后可以算出来权重之和,这时候如果我们把前x1个分到另外一组,那么权重之和减少了sum[x1] * (sum[n-1] - sum[x1]),假如我们再把(x1+1)...x2分为第二组,那么权重之和减少了(sum[x2] - sum[x1]) * (sum[n-1] - sum[x2])。
记f[j]表示分完前i组,第i组的末尾是j的最少减少多少权重(因为我们要让权重最大,所以等价让减少的最少),那么有f[j] = \min_{k=1..j-1}{f[i-1][k] + (sum[j] - sum[k]) * (sum[n-1] - sum[j])} = \min_{k=1..j-1}{f[i-1][k] - sum[k] * (sum[n-1] - sum[j])} + sum[j] * (sum[n-1] - sum[j]),这里我们可以遍历k来求,不过这其实是一个经典的凸优化问题,可以在O(logn)时间内找到最优的k。.鐣欏璁哄潧-涓浜-涓夊垎鍦
好像过于复杂了,也不像是面试想要考察的内容。。。不知道有没有更简单或者更优的做法。
回复 支持 反对

使用道具 举报

heiqilin 发表于 2017-10-30 14:41:19 | 显示全部楼层
haifengc 发表于 2017-10-30 10:29
讲讲,没有想过,

请问楼主面试的时候第四题是怎么做的啊?谢谢!
回复 支持 反对

使用道具 举报

 楼主| haifengc 发表于 2017-10-30 15:03:50 | 显示全部楼层
billyli8866 发表于 2017-10-30 06:40
第五轮是不是应该是二维矩形呀? 二维矩阵相交是什么?

嗯,就是两个矩阵相交的面试
回复 支持 反对

使用道具 举报

 楼主| haifengc 发表于 2017-10-30 15:04:03 | 显示全部楼层
haifengc 发表于 2017-10-30 15:03. From 1point 3acres bbs
嗯,就是两个矩阵相交的面试

面积           
回复 支持 反对

使用道具 举报

 楼主| haifengc 发表于 2017-10-30 15:05:00 | 显示全部楼层
weixinding 发表于 2017-10-30 14:18
说错了,好像没有要求。。不过复杂度在O(knlog(n))
记a为原数组,sum表示数组前i个元素的前缀和,即sum  ...

嗯,谢谢。.1point3acres缃
我明天看看你的解法,好好想一想
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-1-19 00:07

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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