专栏名称: 九章算法
专业的北美IT求职经验分享、技术交流社区，帮助你找到好的IT工作。由硅谷顶尖IT企业工程师维护。提供专业的算法培训/面试咨询，官网 www.jiuzhang.com
目录
相关文章推荐
新机器视觉  ·  定位算法—MCL蒙特卡洛滤波 ·  昨天  
算法与数据结构  ·  今年这情况......真心奉劝大家还是多留一 ... ·  3 天前  
算法与数据结构  ·  程序员又又又要失业了？有反转！Google ... ·  2 天前  
算法爱好者  ·  趣图：现在是你的问题了 ┓( ´∀` )┏ ·  3 天前  
算法爱好者  ·  本科经典算法Dijkstra，被证明是普遍最 ... ·  5 天前  
51好读  ›  专栏  ›  九章算法

Facebook面试题 | 有效正方形

九章算法  · 公众号  · 算法  · 2017-11-01 07:42

正文


作者 | 吕助教

编辑 | Cecily

专栏 | 九章算法


题目描述


给定二维平面内的四个点，判断这四个点是否能组成正方形。坐标(x,y)为整数。

输入的整数范围为 [-10000, 10000]。


样例


输入:

p1=[0,0],p2=[1,1],p3=[1,0],p4=[0,1]

输出:

Ture


说明:

[0,0],[1,1],[0,1],[1,0]四个点能够组成正方形。


解题思路分析


题目要求我们判断四个点能否组成正方形，那么正方形有哪些特征呢。我们容易想到，正方形四条边长度都相等，并且两条对角线长度也相等，所以，我们只要求出这四个点两两之间的距离，进行从小到大排序之后，如果这四个点能构成正方形，那么前面四个数就是四条边长的长度，后面两个数为两条对角线的长度，因此我们只需要判断前四个数以及后两个数它们是否相等即可。


这题为避免四个点重叠，因此我们还需要判断一下对角线长度是否大于边长即可。


参考程序


http://www.jiuzhang.com/solution/valid-square/

       

面试官角度分析


本题较为简单，解法多样，只要能根据正方形特征判断出是否为正方形，即可获得hire评价


lintcode相关问题


http://www.lintcode.com/zh-cn/problem/max-points-on-a-line/


 
更多精彩内容

  • 回复“简历”，查看简历撰写指南，获取“简历模板”

  • 回复“冷冻期”，查看北美各大IT企业冷冻期信息和注意事项

  • 回复“Career”, 查看Caireer Fair 攻略 check list

  • 回复“薪资”，查看北美各大IT企业New Grades Engineer 薪资水平；

  • 回复“项目”，查看7-14天可以搞定的小项目推荐

  • 回复“评分”，查看系统设计评分指南

  • 回复“behavior”，查看behavior interview指南

  • 回复“晋升”，查看Engineer晋升机制 


九章算法 | 帮助更多中国人找到好工作


《Big Data 项目实战班》

《九章算法班》

《面向对象专题》

《Android 项目实战班》

《动态规划专题班》


正在报名中！

报名登陆官网 www.jiuzhang.com

或点击文末“阅读原文”


推荐文章
新机器视觉  ·  定位算法—MCL蒙特卡洛滤波
昨天
算法与数据结构  ·  今年这情况......真心奉劝大家还是多留一手准备吧
3 天前
算法与数据结构  ·  程序员又又又要失业了？有反转！Google CEO称1/4的代码是AI写的！谷歌员工在线打脸：数据明显掺水，工程都是我们做的
2 天前
算法爱好者  ·  趣图：现在是你的问题了 ┓( ´∀` )┏
3 天前
算法爱好者  ·  本科经典算法Dijkstra，被证明是普遍最优了：最坏情况性能也最优！
5 天前
商界  ·  摩拜用户退押金频出问题，10亿资金池若断裂会否成为下一个跑路P2P?
7 年前
普象工业设计小站  ·  【建筑】嫌城里房价太高，买个集装箱住到乡下去
7 年前
济宁广电  ·  一秒入夏！济宁本周最高气温33°，更让你意想不到是.....
7 年前
少女兔  ·  全国招聘|蛙哥邀你一起干票大的！
7 年前
新加坡眼  ·  曾有8000多名越南人在10天里涌进新加坡？！
7 年前
Sov5搜索   ·   小百科   ·   移动版
51好读 - 好文章就要读起来!