一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 843|回复: 25
收起左侧

palantir 共线问题

[复制链接] |试试Instant~ |关注本帖
wendychueng 发表于 2014-5-31 03:21:08 | 显示全部楼层 |阅读模式

2014(4-6月) 码农类 硕士 全职@palantir - 网上海投 - 在线笔试 |Fail

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

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

x
palantir point test 4点共线问题 题目说了一句不能用计算和比较浮点数斜率!!!
想到 就是转化到比较整型的向量.1point3acres缃
转化到 x1 == x2  , check y1 ? y2
or       y1 == y2, check x1 ? x2
思路: 4点共线-->两个3点共线的判断 -->3个点, 分别求出第1个和后面2个的gradient, 用向量表示如下. visit 1point3acres.com for more.
2,4
1999, 4000
接下来比较这2组向量是否相同
转化成 2000, 4000 and 1999, 4000
2000 != 1999 不共线

大家说说有什么好方法啊
leetcode上的max num in a line 都是用double slope做的oj也全过了
kongweihan 发表于 2015-1-17 11:37:42 | 显示全部楼层
ABCD四点共线转为判断两个三点共线,ABC和ABD。三点共线可以计算ABC这个三角形的面积,如果为0则共线,公式是AC和BC的叉乘,(A.x - C.x)*(B.y - C.y) - (A.y - C.y)*(B.x - C.x) == 0,只要这个等式成立就共线啦,注意两个向量都是以C为原点的。
回复 支持 1 反对 0

使用道具 举报

ohmystill 发表于 2014-6-3 00:59:17 | 显示全部楼层
ohmystill 发表于 2014-6-3 00:56
四点共线 是couresera 的 算法课的课后题啊 我给你找找

用浮点做的
转化成 整形向量可以啊
用一个类来存值 里面自动实例化的时候 就把公约数约掉. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
就一个 分母 和 一个 分子了
复写 equals();
回复 支持 1 反对 0

使用道具 举报

 楼主| wendychueng 发表于 2014-5-31 03:33:16 | 显示全部楼层
题目 提示不能用浮点数的运算和比较,所以只能用整型的加减乘和求余吧
回复 支持 反对

使用道具 举报

 楼主| wendychueng 发表于 2014-6-3 00:02:14 | 显示全部楼层
不要沉。。。有没有人做过这个,请教一下好方法
回复 支持 反对

使用道具 举报

ohmystill 发表于 2014-6-3 00:56:01 | 显示全部楼层
四点共线 是couresera 的 算法课的课后题啊 我给你找找
回复 支持 反对

使用道具 举报

 楼主| wendychueng 发表于 2014-6-3 03:58:23 | 显示全部楼层
ohmystill 发表于 2014-6-2 11:59
用浮点做的. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
转化成 整形向量可以啊
用一个类来存值 里面自动实例化的时候 就把公约数约掉

你意思是还是算slope, 不过存成分数的形式,然后比较整型向量?但是加上求最大公约数这个performance就很慢了吧
回复 支持 反对

使用道具 举报

notbad 发表于 2014-6-4 09:34:56 | 显示全部楼层
假设这四个点分别是p1,p2,p3,p4。只需要判断p3,p4是否都在p1p2形成的直线就行了。判断p3是否在p1p2所有的直线,可以通过计算向量叉积来做,就是需要判断这个叉积的绝对值是否是两个向量长度的乘积,为了避免开方的浮点运算,可以两边同时平方,也就是计算 ((p2.x-p1.x)(p3.x-p1.x)+(p2.y-p1.y)(p3.y-p1.y))^2 =? ((p1.x-p2.x)^2+(p1.y-p2.y)^2)((p3.x-p1.x)^2+(p3.y-p1.y)^2),然后类似的方式判断p4,可能需要注意点是否重合的情况,不过这个方程可能已经包含了这种情况。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
其实,不用计算斜率,也可以利用斜率的比较来判断,例如判断p1,p2,p3是否共线,是可以计算两个斜率,然后看绝对值是否相同,同时也可以对斜率比较做简单的变现,直接使用下面的方程:
(p2.x-p1.x)(p3.y-p1.y) =? (p3.x-p1.x)*(p2.y-p1.y), (考虑绝对值的情况,可以两边同时平方)这个本质是比较斜率,只不过不用在计算斜率了。.鐣欏璁哄潧-涓浜-涓夊垎鍦
回复 支持 反对

使用道具 举报

notbad 发表于 2014-6-4 09:36:38 | 显示全部楼层
应该是"点积",不是叉积。
回复 支持 反对

使用道具 举报

readman 发表于 2014-6-4 09:57:11 | 显示全部楼层
wendychueng 发表于 2014-6-3 03:58. 1point3acres.com/bbs
你意思是还是算slope, 不过存成分数的形式,然后比较整型向量?但是加上求最大公约数这个performance就很 ...
. 1point3acres.com/bbs
cracking the coding interview 原题.
page 272

回复 支持 反对

使用道具 举报

readman 发表于 2014-6-4 10:04:39 | 显示全部楼层
哦 不能比较....鏈枃鍘熷垱鑷1point3acres璁哄潧
- = 能不能算个方程? 然后带数进去...
回复 支持 反对

使用道具 举报

北美农民 发表于 2014-6-4 10:45:55 | 显示全部楼层
palantir题库居然换了?. 1point3acres.com/bbs
. 1point3acres.com/bbs
能给出原题描述么, 什么叫做不能计算。
回复 支持 反对

使用道具 举报

 楼主| wendychueng 发表于 2014-6-5 00:44:12 | 显示全部楼层
readman 发表于 2014-6-3 21:04
哦 不能比较.... 1point3acres.com/bbs
- = 能不能算个方程? 然后带数进去...

题目说.鐣欏璁哄潧-涓浜-涓夊垎鍦
Please pay attention that computing and comparing double precision can not get the accurate result. 从test case 也可以看出来,都是long long int, 如果相差很小,斜率的区别估计不知道到多少位后面去了
回复 支持 反对

使用道具 举报

 楼主| wendychueng 发表于 2014-6-5 00:45:20 | 显示全部楼层
北美农民 发表于 2014-6-3 21:45
palantir题库居然换了?

能给出原题描述么, 什么叫做不能计算。

palantir 以前喜欢考那个 rainfall 我觉得那个问题还蛮有意思的
回复 支持 反对

使用道具 举报

 楼主| wendychueng 发表于 2014-6-5 00:46:53 | 显示全部楼层
notbad 发表于 2014-6-3 20:34
假设这四个点分别是p1,p2,p3,p4。只需要判断p3,p4是否都在p1p2形成的直线就行了。判断p3是否在p1p2所有的直 ...

这个好,另外题目说了assume 没有重复的点
回复 支持 反对

使用道具 举报

 楼主| wendychueng 发表于 2014-6-5 00:49:19 | 显示全部楼层
notbad 发表于 2014-6-3 20:34
假设这四个点分别是p1,p2,p3,p4。只需要判断p3,p4是否都在p1p2形成的直线就行了。判断p3是否在p1p2所有的直 ...

有一个潜在问题是,两个long long int相乘,超范围了,你要用什么存?
回复 支持 反对

使用道具 举报

北美农民 发表于 2014-6-5 05:16:22 | 显示全部楼层
wendychueng 发表于 2014-6-4 11:45
palantir 以前喜欢考那个 rainfall 我觉得那个问题还蛮有意思的

啥叫不能计算啊, 浮点算斜率的话虽然是除法,除法能任意转化成乘法啊。
回复 支持 反对

使用道具 举报

readman 发表于 2014-6-5 08:49:24 | 显示全部楼层
wendychueng 发表于 2014-6-5 00:45
palantir 以前喜欢考那个 rainfall 我觉得那个问题还蛮有意思的

比如说
int e = 0.00001 /*精确到一万位后*/
slope 1 - slope 2 > e

这个也不行?? 这个是书上的答案..
回复 支持 反对

使用道具 举报

notbad 发表于 2014-6-5 09:13:59 | 显示全部楼层
wendychueng 发表于 2014-6-5 00:46 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
这个好,另外题目说了assume 没有重复的点
. more info on 1point3acres.com
奥。那可以使用python、java这种有BigInt的语言。。或者需要自己实现高精度了乘法了。。。
楼主,现在是面P家的intern 还是fulltime啊?明年毕业的可以面fulltime了?
回复 支持 反对

使用道具 举报

 楼主| wendychueng 发表于 2014-6-5 10:12:18 | 显示全部楼层
notbad 发表于 2014-6-4 20:13. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
奥。那可以使用python、java这种有BigInt的语言。。或者需要自己实现高精度了乘法了。。。
楼主,现在是 ...

额 full time 我今年暑假毕业,现在课都上完了在赶论文然后一边找工作。
回复 支持 反对

使用道具 举报

 楼主| wendychueng 发表于 2014-6-5 10:14:51 | 显示全部楼层
北美农民 发表于 2014-6-4 16:16
啥叫不能计算啊, 浮点算斜率的话虽然是除法,除法能任意转化成乘法啊。

不能 computing and comparing double precision,我理解就是只能用整型,算不算slope 不是关键
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-9 06:05

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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