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


一亩三分地论坛

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

[算法题] Erect the fence是个典型的凸包问题。。狗这是要往ACM的方向杀过去了么。。

[复制链接] |试试Instant~ |关注本帖
2011051305 发表于 2017-8-12 13:53:44 | 显示全部楼层 |阅读模式

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

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

x
转专业的表示好想死 == 顺便来一发 我看到的还不错的凸包问题解释...
https://segmentfault.com/a/1190000000488339


[size=14.6667px]这题如果我被面到.... 那我也就随缘了
[size=14.6667px]

[size=14.6667px]今天解决了拓扑排序的利扣和林口的题。。 我要不要也打个卡呢

评分

1

查看全部评分

fentoyal 发表于 2017-8-13 04:59:10 | 显示全部楼层
本帖最后由 fentoyal 于 2017-8-13 05:03 编辑
2011051305 发表于 2017-8-13 03:42
您好 请问cg的缩写是? 是前面版上前辈提到的“计算几何”吗? 谢谢!

是的,computational geometry。这个学科基本是个半死不活的学科。创立的很晚,但迅速得到了很多大神的兴趣,投入研究,结果瞬间把所有问题都解决的差不多了。。。没什么深度的学科。
面试按我理解,最基本的一个算法是左测试(判断一个点是否在一个向量左边)是个必须掌握的点,这个能用到N多种场合。比如判断是否是凸多边形啊,算凸包啊,都用。
其它的还有一些简单算法,比如判断一个点是否在多边形内,一个点是否能"看到“一个线段。其它的基本可以肯定不会考到了。
回复 支持 1 反对 0

使用道具 举报

fentoyal 发表于 2017-8-13 01:23:33 | 显示全部楼层
凸包不是ACM题。你写写试一试,基本是Medium里实现略麻烦级别的而已,如果知道凸包算法,它连LC hard都算不上。计算几何里基础算法而已。
回复 支持 1 反对 0

使用道具 举报

gypcmbczs 发表于 2017-8-12 20:35:44 | 显示全部楼层
貌似普林斯顿的算法I提到过凸包
回复 支持 反对

使用道具 举报

LeetCodeOJ 发表于 2017-8-12 23:44:08 | 显示全部楼层
因为bar越来越高了
回复 支持 反对

使用道具 举报

LeetCodeOJ 发表于 2017-8-12 23:46:42 | 显示全部楼层
这道题 我问一个 高中生 他秒答.....
回复 支持 反对

使用道具 举报

xiaokaneier 发表于 2017-8-13 00:00:47 | 显示全部楼层
凸包问题学过就是easy,没学过让你无中生有想这个,真让你想到解法那我建议直接去读个PhD吧
回复 支持 反对

使用道具 举报

 楼主| 2011051305 发表于 2017-8-13 03:02:53 | 显示全部楼层
fentoyal 发表于 2017-8-13 01:23
凸包不是ACM题。你写写试一试,基本是Medium里实现略麻烦级别的而已,如果知道凸包算法,它连LC hard都算不 ...

好的前辈!

我今天仔细琢磨一下看能不能把这个题过了(但说实话 第一眼看上去这道题一点思路都没有 还是看了网上题解才意识到的 == 这大概就是成长的过程嘤嘤嘤嘤~~)
回复 支持 反对

使用道具 举报

ym3fd 发表于 2017-8-13 03:08:13 | 显示全部楼层
cg的知识点还是要补充的 临时想很困难
回复 支持 反对

使用道具 举报

fentoyal 发表于 2017-8-13 03:19:28 | 显示全部楼层
2011051305 发表于 2017-8-13 03:02
好的前辈!

我今天仔细琢磨一下看能不能把这个题过了(但说实话 第一眼看上去这道题一点思路都没有  ...

哈,我都没意识到lz原来是你,你的这个ID一串数字,太难认了。

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| 2011051305 发表于 2017-8-13 03:41:02 | 显示全部楼层
fentoyal 发表于 2017-8-13 03:19
哈,我都没意识到lz原来是你,你的这个ID一串数字,太难认了。

被前辈认出来了 以后不敢在版上造次
回复 支持 反对

使用道具 举报

 楼主| 2011051305 发表于 2017-8-13 03:42:53 | 显示全部楼层
ym3fd 发表于 2017-8-13 03:08
cg的知识点还是要补充的 临时想很困难

您好 请问cg的缩写是? 是前面版上前辈提到的“计算几何”吗? 谢谢!
回复 支持 反对

使用道具 举报

staycrazy 发表于 2017-8-13 06:01:05 | 显示全部楼层
凸包算法在算法导论里就有。。。。。
回复 支持 反对

使用道具 举报

staycrazy 发表于 2017-8-13 06:02:44 | 显示全部楼层
另外大家可能对ACM这三个字母看得太重了。

实际上ACM里面的水题可以很水,就和LC的hard差不多。

而LC的一些题目其实也都是从竞赛题目转化过来的,比如最初150题里面的那个maximum rectangle.

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

ym3fd 发表于 2017-8-13 09:35:52 | 显示全部楼层
2011051305 发表于 2017-8-13 03:42
您好 请问cg的缩写是? 是前面版上前辈提到的“计算几何”吗? 谢谢!

是的. 推荐邓俊辉老师的 计算几何

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

LeetCodeOJ 发表于 2017-8-13 10:58:22 | 显示全部楼层
但是有人这题直接秒杀…
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-11-18 10:52

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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