回复: 26
跳转到指定楼层
上一主题 下一主题
收起左侧

palantir 共线问题

全局:

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

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
palantir point test 4点共线问题 题目说了一句不能用计算和比较浮点数斜率!!!
想到 就是转化到比较整型的向量
转化到 x1 == x2  , check y1 ? y2
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies
eetcode上的max num in a line 都是用double slope做的oj也全过了

上一篇:LSI on-site面经
下一篇:和三哥约好电话面试,到时间了,电话没来...
推荐
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为原点的。
回复

使用道具 举报

推荐
ohmystill 2014-6-3 00:59:17 | 只看该作者
全局:
ohmystill 发表于 2014-6-3 00:56
四点共线 是couresera 的 算法课的课后题啊 我给你找找

用浮点做的
转化成 整形向量可以啊
用一个类来存值 里面自动实例化的时候 就把公约数约掉
就一个 分母 和 一个 分子了
复写 equals();
回复

使用道具 举报

推荐
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), (考虑绝对值的情况,可以两边同时平方)这个本质是比较斜率,只不过不用在计算斜率了。
回复

使用道具 举报

🔗
 楼主| 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:36:38 | 只看该作者
全局:
应该是"点积",不是叉积。
回复

使用道具 举报

🔗
readman 2014-6-4 09:57:11 | 只看该作者
全局:
wendychueng 发表于 2014-6-3 03:58
你意思是还是算slope, 不过存成分数的形式,然后比较整型向量?但是加上求最大公约数这个performance就很 ...

cracking the coding interview 原题.
page 272

回复

使用道具 举报

🔗
readman 2014-6-4 10:04:39 | 只看该作者
全局:
哦 不能比较...
- = 能不能算个方程? 然后带数进去...
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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