《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 1667|回复: 9
收起左侧

F, G, L, U, A 店面

[复制链接] |试试Instant~ |关注本帖
vbnmmnbv 发表于 2017-9-17 02:06:19 | 显示全部楼层 |阅读模式

2017(7-9月) 码农类 博士 全职@Google - 网上海投 - 技术电面 |Other在职跳槽

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

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

x
F: 伞一思G: 尔尔爸; 给一个tree node,  return in order successor
L: 而丝丝, 可以有dup;  一个ordered list, 找到正确插入位置. from: 1point3acres.com/bbs
U: 一个int list, return start 到 end 里 的最小数, 可以pre-processing. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
A: 两个list, 输出不相同element的list. 鍥磋鎴戜滑@1point 3 acres

评分

3

查看全部评分

lcq123 发表于 2017-9-17 06:12:45 | 显示全部楼层
请问A家那道题楼主是怎么做的?谢谢!
回复 支持 反对

使用道具 举报

 楼主| vbnmmnbv 发表于 2017-9-17 11:14:26 | 显示全部楼层
lcq123 发表于 2017-9-17 06:12
请问A家那道题楼主是怎么做的?谢谢!

我就先保存到两个set, 然后traverse set1找不在set2的元素, 再traverse set2 找不在set1的元素, 加起来
回复 支持 反对

使用道具 举报

lcq123 发表于 2017-9-17 11:50:12 | 显示全部楼层
vbnmmnbv 发表于 2017-9-17 11:14
我就先保存到两个set, 然后traverse set1找不在set2的元素, 再traverse set2 找不在set1的元素, 加起来 ...

哦哦,好的,谢谢楼主!!!
回复 支持 反对

使用道具 举报

kevintong 发表于 2017-9-23 20:56:48 | 显示全部楼层
请教楼主Uber的题怎么做啊?
回复 支持 反对

使用道具 举报

 楼主| vbnmmnbv 发表于 2017-9-26 00:37:13 | 显示全部楼层
kevintong 发表于 2017-9-23 20:56
请教楼主Uber的题怎么做啊?

可以用dp做, 后来知道好像也可以用什么segment tree.
回复 支持 反对

使用道具 举报

kevintong 发表于 2017-9-26 10:19:38 | 显示全部楼层
segment tree不是很说得通啊,因为要存i,i+1每个区间的min,这和直接使用数组没什么区别呀。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
. From 1point 3acres bbs
dp什么思路呢?时间复杂度能优化到多少呀?感谢楼主了!
回复 支持 反对

使用道具 举报

 楼主| vbnmmnbv 发表于 2017-9-27 14:10:47 | 显示全部楼层
kevintong 发表于 2017-9-26 10:19
segment tree不是很说得通啊,因为要存i,i+1每个区间的min,这和直接使用数组没什么区别呀。

dp什么思路 ...

我是计算一个二维数组,存i 到 j的最小值,  二维数组的建立过程用到dp,这个应该是平方的吧。 然后query 就是O(1)了。

segment tree我不了解,但是估计可以做的比平方好?
回复 支持 反对

使用道具 举报

kevintong 发表于 2017-9-27 21:41:07 | 显示全部楼层
vbnmmnbv 发表于 2017-9-27 14:10
我是计算一个二维数组,存i 到 j的最小值,  二维数组的建立过程用到dp,这个应该是平方的吧。 然后query ...

. Waral 鍗氬鏈夋洿澶氭枃绔,恩恩,DP这样很有道理。我觉得线段树不好做,不是很说得通
回复 支持 反对

使用道具 举报

 楼主| vbnmmnbv 发表于 2017-9-28 10:48:49 | 显示全部楼层
kevintong 发表于 2017-9-27 21:41
恩恩,DP这样很有道理。我觉得线段树不好做,不是很说得通
. 1point3acres.com/bbs
你看这个不行吗?

http://www.geeksforgeeks.org/seg ... ange-minimum-query/
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-11-20 04:10

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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