近期论坛无法登录的解决方案


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 1119|回复: 25
收起左侧

palantir 共线问题

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

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

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

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

x
palantir point test 4点共线问题 题目说了一句不能用计算和比较浮点数斜率!!!
想到 就是转化到比较整型的向量 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
转化到 x1 == x2  , check y1 ? y2
or       y1 == y2, check x1 ? x2
思路: 4点共线-->两个3点共线的判断 -->3个点, 分别求出第1个和后面2个的gradient, 用向量表示如下
2,4
1999, 4000
接下来比较这2组向量是否相同
转化成 2000, 4000 and 1999, 4000
2000 != 1999 不共线
. 鍥磋鎴戜滑@1point 3 acres
大家说说有什么好方法啊
leetcode上的max num in a line 都是用double slope做的oj也全过了
kongweihan 发表于 2015-1-17 11:37:42 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
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 | 显示全部楼层
关注一亩三分地微博:
Warald
ohmystill 发表于 2014-6-3 00:56
四点共线 是couresera 的 算法课的课后题啊 我给你找找

用浮点做的.鏈枃鍘熷垱鑷1point3acres璁哄潧
转化成 整形向量可以啊
用一个类来存值 里面自动实例化的时候 就把公约数约掉. 鍥磋鎴戜滑@1point 3 acres
就一个 分母 和 一个 分子了
复写 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
你意思是还是算slope, 不过存成分数的形式,然后比较整型向量?但是加上求最大公约数这个performance就很 ...

cracking the coding interview 原题.
page 272. from: 1point3acres.com/bbs

回复 支持 反对

使用道具 举报

readman 发表于 2014-6-4 10:04:39 | 显示全部楼层
哦 不能比较...
- = 能不能算个方程? 然后带数进去...
回复 支持 反对

使用道具 举报

北美农民 发表于 2014-6-4 10:45:55 | 显示全部楼层
palantir题库居然换了?

能给出原题描述么, 什么叫做不能计算。
回复 支持 反对

使用道具 举报

 楼主| wendychueng 发表于 2014-6-5 00:44:12 | 显示全部楼层
readman 发表于 2014-6-3 21:04
哦 不能比较...
- = 能不能算个方程? 然后带数进去...
. 1point 3acres 璁哄潧
题目说
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. 鍥磋鎴戜滑@1point 3 acres
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. more info on 1point3acres.com
palantir 以前喜欢考那个 rainfall 我觉得那个问题还蛮有意思的

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

使用道具 举报

readman 发表于 2014-6-5 08:49:24 | 显示全部楼层
wendychueng 发表于 2014-6-5 00:45
palantir 以前喜欢考那个 rainfall 我觉得那个问题还蛮有意思的
. 鍥磋鎴戜滑@1point 3 acres
比如说
int e = 0.00001 /*精确到一万位后*/
slope 1 - slope 2 > e. From 1point 3acres bbs

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

使用道具 举报

notbad 发表于 2014-6-5 09:13:59 | 显示全部楼层
wendychueng 发表于 2014-6-5 00:46. 1point3acres.com/bbs
这个好,另外题目说了assume 没有重复的点

奥。那可以使用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 不是关键
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-6-23 21:58

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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