谈谈使用过的几款咖啡机

一亩三分地论坛

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

最近看过此主题的会员

H1B/绿卡遥遥无期
又不想回国
来东南亚最大的互联网集团工作?
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 3103|回复: 34
收起左侧

9月G 昂赛

[复制链接] |试试Instant~ |关注本帖
我的人缘0
alex.chan 发表于 2017-10-28 05:40:48 | 显示全部楼层 |阅读模式
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】

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

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

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

x


第一轮:
给n个三角形,三角形的三个顶点分别用大于零的自然数表示. visit 1point3acres for more.
比如
. 围观我们@1point 3 acres三角形一  1,3,5. 1point3acres
三角形二  2, 9, 10
三角形三  11, 23, 3
三角形四  3,5,11
...
要求输出一个图
每个三角形代表图中的一个节点,如果两个三角形有公共的边,则两个对应的节点之间存在一条路径(可以是一条边或者连通的路径). 留学申请论坛-一亩三分地
比如三角形一和三角形四有公共边3,5,则在所建的图里,三角形一和三角形四对应的节点需要连通
. 一亩-三分-地,独家发布

第二轮:
李德克 私酒
李德克 而把衣

第三轮:
中序遍历二叉树中第k个的节点.本文原创自1point3acres论坛
每个节点记录了所在子树的节点的个数


第四轮:
给一个长度为n的数组,把数组分为k段,每段至少一个数
每段内的数俩俩相乘的和作为这段的权重,求如何划分数组使得所有段的权重之和最大. 一亩-三分-地,独家发布
比如数组是这样的
[1, 2, 32, 7, 2, 23, 3, 4, 32, 2]
k是3. Waral 博客有更多文章,
.本文原创自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
不需要返回怎么划分,只需要返回最大的和


第五轮:
第一题
(1) 判断两条一维的线段是否相交
(2) 返回两条一维的线段相交的长度
(3) 返回两个二维矩阵相交的面积
. 一亩-三分-地,独家发布第二题. 1point3acres
李德克 丝霸气. 留学申请论坛-一亩三分地

. From 1point 3acres bbs

评分

参与人数 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 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
weiliango 发表于 2017-11-11 03:55
求教一下楼主第三题的题干,没有看明白。。。已加大米

就是给一颗二叉树,
树的每个节点有一个integer field,记录的是以这个节点为root的subtree的节点的个数
.本文原创自1point3acres论坛
然后,求整棵树按中序遍历的第k个node

谢谢你的大米啊

评分

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

查看全部评分

回复 支持 1 反对 0

使用道具 举报

我的人缘0
大懒懒一休哥 发表于 2017-10-28 06:10:01 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
第一题楼主怎么做的啊?
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| alex.chan 发表于 2017-10-28 06:11:02 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
大懒懒一休哥 发表于 2017-10-28 06:10
第一题楼主怎么做的啊?

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

使用道具 举报

我的人缘0
fledgling 发表于 2017-10-28 07:36:59 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
请问楼主(4)是三维的区间DP解法么?
回复 支持 反对

使用道具 举报

我的人缘0
m1n2b3v4 发表于 2017-10-28 07:48:40 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
恭喜!请问lz onsite 到hc的timeline是什么呀谢谢了!!
回复 支持 反对

使用道具 举报

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

2维可以的
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| alex.chan 发表于 2017-10-28 09:14:08 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
m1n2b3v4 发表于 2017-10-28 07:48
恭喜!请问lz onsite 到hc的timeline是什么呀谢谢了!!
.1point3acres网
谢谢,
还没有HC
面完两周说要先team match
然后再hc
match了一个月,至今没有人理
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

我的人缘0
fledgling 发表于 2017-10-28 09:56:31 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】

多谢楼主!
回复 支持 反对

使用道具 举报

我的人缘0
hzyfree 发表于 2017-10-28 10:05:30 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
求问第四轮有O(N2)的做法吗? 我只想到了O(N3)的做法...
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| alex.chan 发表于 2017-10-28 10:08:43 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
我当时想到的就是O(n^2 * k)的方法,
应该有更好一点的,没有时间,就先写了这个代码,后来代码写完,时间也到了
回复 支持 反对

使用道具 举报

我的人缘0
春山寒 发表于 2017-10-30 04:04:37 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
第四题 vector 里的数 是可正可负吗
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| alex.chan 发表于 2017-10-30 05:19:35 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
春山寒 发表于 2017-10-30 04:04
第四题 vector 里的数 是可正可负吗

应该都可以吧,.留学论坛-一亩-三分地
对算法没有什么影响
回复 支持 反对

使用道具 举报

我的人缘0
billyli8866 发表于 2017-10-30 06:40:55 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
第五轮是不是应该是二维矩形呀? 二维矩阵相交是什么?
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

我的人缘0
 楼主| alex.chan 发表于 2017-10-30 10:29:40 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
weixinding 发表于 2017-10-30 06:48
有的,保证是正数有O(nk)的做法
. 牛人云集,一亩三分地
讲讲,没有想过,
回复 支持 反对

使用道具 举报

我的人缘0
weixinding 发表于 2017-10-30 14:18:04 | 显示全部楼层
  此人我要顶:
 
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% (暂未有人投票) 【我投】
haifengc 发表于 2017-10-30 10:29
讲讲,没有想过,

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

使用道具 举报

我的人缘0
 楼主| alex.chan 发表于 2017-10-30 15:03:50 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
billyli8866 发表于 2017-10-30 06:40
第五轮是不是应该是二维矩形呀? 二维矩阵相交是什么?

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

使用道具 举报

我的人缘0
 楼主| alex.chan 发表于 2017-10-30 15:04:03 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
haifengc 发表于 2017-10-30 15:03
嗯,就是两个矩阵相交的面试

面积           
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

游客
请先登录

本版积分规则

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

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

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

custom counter

GMT+8, 2018-6-23 12:36

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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