详谈如何最大化利用career fair

一亩三分地论坛

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

最近看过此主题的会员

坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
前Google华人高管创立
面试offer一键直通
Leap.ai助你进入热门独角兽
查看: 3473|回复: 34
收起左侧

9月G 昂赛

[复制链接] |试试Instant~
我的人缘0
alex.chan 发表于 2017-10-28 05:40:48 | 显示全部楼层 |阅读模式
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  95% (124)
 
 
4% (6)  踩

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

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

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

x


第一轮:
给n个三角形,三角形的三个顶点分别用大于零的自然数表示
比如
三角形一  1,3,5
三角形二  2, 9, 10.本文原创自1point3acres论坛
三角形三  11, 23, 3
三角形四  3,5,11
...
要求输出一个图
每个三角形代表图中的一个节点,如果两个三角形有公共的边,则两个对应的节点之间存在一条路径(可以是一条边或者连通的路径)
比如三角形一和三角形四有公共边3,5,则在所建的图里,三角形一和三角形四对应的节点需要连通


第二轮:.1point3acres网
李德克 私酒
李德克 而把衣
. visit 1point3acres for more.
第三轮:
中序遍历二叉树中第k个的节点
每个节点记录了所在子树的节点的个数


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

如果这样划分
[1, 2, 32, 7,   |   2, 23, 3,   |   4, 32, 2]

第一段的权重 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
不需要返回怎么划分,只需要返回最大的和

. from: 1point3acres
第五轮:
第一题
(1) 判断两条一维的线段是否相交. 1point3acres
(2) 返回两条一维的线段相交的长度
(3) 返回两个二维矩阵相交的面积
第二题
李德克 丝霸气


评分

参与人数 5大米 +19 收起 理由
weiliango + 3 很有用的信息!
丑猪宝 + 5 很有用的信息!
wuzup + 3 给你点个赞!
m1n2b3v4 + 3 很有用的信息!
edyyy + 5 很有用的信息!

查看全部评分


上一篇:Pocket Gems 1面跪经
下一篇:bb校园面试4轮面经

本帖被以下淘专辑推荐:

我的人缘0
 楼主| alex.chan 发表于 2017-11-11 09:08:22 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  95% (124)
 
 
4% (6)  踩
weiliango 发表于 2017-11-11 03:55
求教一下楼主第三题的题干,没有看明白。。。已加大米

就是给一颗二叉树,
树的每个节点有一个integer field,记录的是以这个节点为root的subtree的节点的个数

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

谢谢你的大米啊

评分

参与人数 1大米 +3 收起 理由
weiliango + 3 给你点个赞!

查看全部评分

回复

使用道具 举报

我的人缘0
大懒懒一休哥 发表于 2017-10-28 06:10:01 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (11)
 
 
0% (0)  踩
第一题楼主怎么做的啊?
回复

使用道具 举报

我的人缘0
 楼主| alex.chan 发表于 2017-10-28 06:11:02 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  95% (124)
 
 
4% (6)  踩
大懒懒一休哥 发表于 2017-10-28 06:10
第一题楼主怎么做的啊?

用的HashMap. visit 1point3acres for more.
把每条边对应的三角形放一起,然后再连起来
回复

使用道具 举报

我的人缘0
fledgling 发表于 2017-10-28 07:36:59 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (1)
 
 
0% (0)  踩
请问楼主(4)是三维的区间DP解法么?

21.000+ students read the Road to learn React. The course weaves all the opinionated roadmaps into one roadmap to master React. It gives you all the fundamentals in React. You will build a Hacker News App along the way.

回复

使用道具 举报

我的人缘0
m1n2b3v4 发表于 2017-10-28 07:48:40 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  62% (204)
 
 
37% (124)  踩
恭喜!请问lz onsite 到hc的timeline是什么呀谢谢了!!
回复

使用道具 举报

我的人缘0
 楼主| alex.chan 发表于 2017-10-28 09:13:17 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  95% (124)
 
 
4% (6)  踩
fledgling 发表于 2017-10-28 07:36
请问楼主(4)是三维的区间DP解法么?

2维可以的.1point3acres网
回复

使用道具 举报

我的人缘0
 楼主| alex.chan 发表于 2017-10-28 09:14:08 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  95% (124)
 
 
4% (6)  踩
m1n2b3v4 发表于 2017-10-28 07:48
恭喜!请问lz onsite 到hc的timeline是什么呀谢谢了!!

谢谢,
还没有HC
面完两周说要先team match
然后再hc
match了一个月,至今没有人理

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

回复

使用道具 举报

我的人缘0
fledgling 发表于 2017-10-28 09:56:31 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (1)
 
 
0% (0)  踩

多谢楼主!
回复

使用道具 举报

我的人缘0
hzyfree 发表于 2017-10-28 10:05:30 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  94% (64)
 
 
5% (4)  踩
求问第四轮有O(N2)的做法吗? 我只想到了O(N3)的做法...
回复

使用道具 举报

我的人缘0
 楼主| alex.chan 发表于 2017-10-28 10:08:43 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  95% (124)
 
 
4% (6)  踩
我当时想到的就是O(n^2 * k)的方法,
应该有更好一点的,没有时间,就先写了这个代码,后来代码写完,时间也到了. 1point3acres

Learn React.js, Redux & Immutable.js while building a weather app

回复

使用道具 举报

我的人缘0
春山寒 发表于 2017-10-30 04:04:37 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  90% (28)
 
 
9% (3)  踩
第四题 vector 里的数 是可正可负吗
回复

使用道具 举报

我的人缘0
 楼主| alex.chan 发表于 2017-10-30 05:19:35 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  95% (124)
 
 
4% (6)  踩
春山寒 发表于 2017-10-30 04:04
第四题 vector 里的数 是可正可负吗

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

使用道具 举报

我的人缘0
billyli8866 发表于 2017-10-30 06:40:55 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  88% (132)
 
 
11% (17)  踩
第五轮是不是应该是二维矩形呀? 二维矩阵相交是什么?
回复

使用道具 举报

我的人缘1
weixinding 发表于 2017-10-30 06:48:24 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (1)
 
 
0% (0)  踩
haifengc 发表于 2017-10-30 05:19
应该都可以吧,
对算法没有什么影响

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

使用道具 举报

我的人缘0
 楼主| alex.chan 发表于 2017-10-30 10:29:40 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  95% (124)
 
 
4% (6)  踩
weixinding 发表于 2017-10-30 06:48
有的,保证是正数有O(nk)的做法

讲讲,没有想过,
回复

使用道具 举报

我的人缘1
weixinding 发表于 2017-10-30 14:18:04 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (1)
 
 
0% (0)  踩
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。
好像过于复杂了,也不像是面试想要考察的内容。。。不知道有没有更简单或者更优的做法。
回复

使用道具 举报

我的人缘0
heiqilin 发表于 2017-10-30 14:41:19 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (9)
 
 
0% (0)  踩
haifengc 发表于 2017-10-30 10:29
讲讲,没有想过,
. 1point 3acres 论坛
请问楼主面试的时候第四题是怎么做的啊?谢谢!
回复

使用道具 举报

我的人缘0
 楼主| alex.chan 发表于 2017-10-30 15:03:50 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  95% (124)
 
 
4% (6)  踩
billyli8866 发表于 2017-10-30 06:40
第五轮是不是应该是二维矩形呀? 二维矩阵相交是什么?
. From 1point 3acres bbs
嗯,就是两个矩阵相交的面试
回复

使用道具 举报

我的人缘0
 楼主| alex.chan 发表于 2017-10-30 15:04:03 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  95% (124)
 
 
4% (6)  踩
haifengc 发表于 2017-10-30 15:03
嗯,就是两个矩阵相交的面试

面积           
回复

使用道具 举报

我的人缘0
 楼主| alex.chan 发表于 2017-10-30 15:05:00 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  95% (124)
 
 
4% (6)  踩
weixinding 发表于 2017-10-30 14:18
说错了,好像没有要求。。不过复杂度在O(knlog(n)). 1point 3acres 论坛
记a为原数组,sum表示数组前i个元素的前缀和,即sum  ...

嗯,谢谢。
我明天看看你的解法,好好想一想
回复

使用道具 举报

游客
请先登录

本版积分规则

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

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

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

GMT+8, 2018-9-23 19:07

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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