给一堆points, 找到所有给定长度的正方形# JobHunting - 待字闺中
K*n
1 楼
输入是一组二维空间里面的点，由x,y值表示。
给定一个长度L，
要求返回所有由这些点形成的边长为L的正方形。
刚才电面一个小公司，没做出来，只想到了hash table。必挂了。
给定一个长度L，
要求返回所有由这些点形成的边长为L的正方形。
刚才电面一个小公司，没做出来，只想到了hash table。必挂了。
C*U
2 楼
我的想法 先把所有点 按照行分成group
然后每个group 取出两个点的列坐标hash
然后行和行之间check
【在 K*********n 的大作中提到】
: 输入是一组二维空间里面的点，由x,y值表示。
: 给定一个长度L，
: 要求返回所有由这些点形成的边长为L的正方形。
: 刚才电面一个小公司，没做出来，只想到了hash table。必挂了。
然后每个group 取出两个点的列坐标hash
然后行和行之间check
【在 K*********n 的大作中提到】
: 输入是一组二维空间里面的点，由x,y值表示。
: 给定一个长度L，
: 要求返回所有由这些点形成的边长为L的正方形。
: 刚才电面一个小公司，没做出来，只想到了hash table。必挂了。
K*n
3 楼
没说square的边是和坐标轴平行的，可以是斜着的。
说实话这个题我不能说多么难，但是25分钟让我搞定算法和code，我没这个能力，我觉
得电面这个有些过分，对我这个水平来说。
【在 C***U 的大作中提到】
: 我的想法 先把所有点 按照行分成group
: 然后每个group 取出两个点的列坐标hash
: 然后行和行之间check
说实话这个题我不能说多么难，但是25分钟让我搞定算法和code，我没这个能力，我觉
得电面这个有些过分，对我这个水平来说。
【在 C***U 的大作中提到】
: 我的想法 先把所有点 按照行分成group
: 然后每个group 取出两个点的列坐标hash
: 然后行和行之间check
C*U
4 楼
好吧 想简单了
【在 K*********n 的大作中提到】
: 没说square的边是和坐标轴平行的，可以是斜着的。
: 说实话这个题我不能说多么难，但是25分钟让我搞定算法和code，我没这个能力，我觉
: 得电面这个有些过分，对我这个水平来说。
【在 K*********n 的大作中提到】
: 没说square的边是和坐标轴平行的，可以是斜着的。
: 说实话这个题我不能说多么难，但是25分钟让我搞定算法和code，我没这个能力，我觉
: 得电面这个有些过分，对我这个水平来说。
K*n
5 楼
我现在很想骂娘，对这个题。
可能水平高的人会说，还是骂我自己水平差吧。但是确实是在我能力范围之外了。
【在 C***U 的大作中提到】
: 好吧 想简单了
可能水平高的人会说，还是骂我自己水平差吧。但是确实是在我能力范围之外了。
【在 C***U 的大作中提到】
: 好吧 想简单了
C*U
6 楼
题目看错了
原来是给定长度的正方形
【在 K*********n 的大作中提到】
: 输入是一组二维空间里面的点，由x,y值表示。
: 给定一个长度L，
: 要求返回所有由这些点形成的边长为L的正方形。
: 刚才电面一个小公司，没做出来，只想到了hash table。必挂了。
原来是给定长度的正方形
【在 K*********n 的大作中提到】
: 输入是一组二维空间里面的点，由x,y值表示。
: 给定一个长度L，
: 要求返回所有由这些点形成的边长为L的正方形。
: 刚才电面一个小公司，没做出来，只想到了hash table。必挂了。
K*n
7 楼
brute force至少O(n^4)，我当时也没办法了，我说我就brute force，他说不行，没技
术含量。
前面问题都问得很好，突然上来个这个，擦。
【在 C***U 的大作中提到】
: 题目看错了
: 原来是给定长度的正方形
术含量。
前面问题都问得很好，突然上来个这个，擦。
【在 C***U 的大作中提到】
: 题目看错了
: 原来是给定长度的正方形
K*n
8 楼
你说说怎么做
【在 C***U 的大作中提到】
: 题目看错了
: 原来是给定长度的正方形
【在 C***U 的大作中提到】
: 题目看错了
: 原来是给定长度的正方形
R*y
9 楼
为每一个点创立一个array，里面按顺序存放所有到这个点距离为L的点。
把每个array看成一个set，找出所有交集为2的set。
O(n^2 log n)
把每个array看成一个set，找出所有交集为2的set。
O(n^2 log n)
K*n
10 楼
第一步为n^2
第二步如何在log n内完成呢？
【在 R********y 的大作中提到】
: 为每一个点创立一个array，里面按顺序存放所有到这个点距离为L的点。
: 把每个array看成一个set，找出所有交集为2的set。
: O(n^2 log n)
第二步如何在log n内完成呢？
【在 R********y 的大作中提到】
: 为每一个点创立一个array，里面按顺序存放所有到这个点距离为L的点。
: 把每个array看成一个set，找出所有交集为2的set。
: O(n^2 log n)
D*d
11 楼
想到一个 O(n^3) 的解法：
1. sort on x axis -- O(nlg(n)) x1 <= .... <= xn
2. for each pair (n1,n4) check d(n1,n4) == sqrt(2)L,
if yes, check 2sum problem on x: s.t. x2+x3 = x1 + x4
if yes, check d(n2,n3) == sqrt(2)L,
if yes, output (x1,x2,x3,x4)
n^2 pairs * 2sum = O(n^3)
1. sort on x axis -- O(nlg(n)) x1 <= .... <= xn
2. for each pair (n1,n4) check d(n1,n4) == sqrt(2)L,
if yes, check 2sum problem on x: s.t. x2+x3 = x1 + x4
if yes, check d(n2,n3) == sqrt(2)L,
if yes, output (x1,x2,x3,x4)
n^2 pairs * 2sum = O(n^3)
R*y
12 楼
两步都是O(n^2 log n)，加法关系...
【在 K*********n 的大作中提到】
: 第一步为n^2
: 第二步如何在log n内完成呢？
【在 K*********n 的大作中提到】
: 第一步为n^2
: 第二步如何在log n内完成呢？
K*n
13 楼
好像差不多
【在 R********y 的大作中提到】
: 为每一个点创立一个array，里面按顺序存放所有到这个点距离为L的点。
: 把每个array看成一个set，找出所有交集为2的set。
: O(n^2 log n)
【在 R********y 的大作中提到】
: 为每一个点创立一个array，里面按顺序存放所有到这个点距离为L的点。
: 把每个array看成一个set，找出所有交集为2的set。
: O(n^2 log n)
K*n
14 楼
这个2sum用得挺好，貌似这样可以吧……
不过每一个pair可能能形成两个正方形，所以2sum最后一步，找到n2和n3后，不能quit
，可能还有一对儿n2和n3.
【在 D**********d 的大作中提到】
: 想到一个 O(n^3) 的解法：
: 1. sort on x axis -- O(nlg(n)) x1 <= .... <= xn
: 2. for each pair (n1,n4) check d(n1,n4) == sqrt(2)L,
: if yes, check 2sum problem on x: s.t. x2+x3 = x1 + x4
: if yes, check d(n2,n3) == sqrt(2)L,
: if yes, output (x1,x2,x3,x4)
: n^2 pairs * 2sum = O(n^3)
:
不过每一个pair可能能形成两个正方形，所以2sum最后一步，找到n2和n3后，不能quit
，可能还有一对儿n2和n3.
【在 D**********d 的大作中提到】
: 想到一个 O(n^3) 的解法：
: 1. sort on x axis -- O(nlg(n)) x1 <= .... <= xn
: 2. for each pair (n1,n4) check d(n1,n4) == sqrt(2)L,
: if yes, check 2sum problem on x: s.t. x2+x3 = x1 + x4
: if yes, check d(n2,n3) == sqrt(2)L,
: if yes, output (x1,x2,x3,x4)
: n^2 pairs * 2sum = O(n^3)
:
l*i
15 楼
这个凌行就不对把，四条边都是L长度不一定是正方形阿
【在 R********y 的大作中提到】
: 为每一个点创立一个array，里面按顺序存放所有到这个点距离为L的点。
: 把每个array看成一个set，找出所有交集为2的set。
: O(n^2 log n)
【在 R********y 的大作中提到】
: 为每一个点创立一个array，里面按顺序存放所有到这个点距离为L的点。
: 把每个array看成一个set，找出所有交集为2的set。
: O(n^2 log n)
K*n
16 楼
是啊……
所以我现在还在郁闷，不到半小时让写个这个。
【在 l***i 的大作中提到】
: 这个凌行就不对把，四条边都是L长度不一定是正方形阿
所以我现在还在郁闷，不到半小时让写个这个。
【在 l***i 的大作中提到】
: 这个凌行就不对把，四条边都是L长度不一定是正方形阿
R*y
17 楼
找出四个点之后，随便检查某一个角是不是直角，只要const time啊，又不影响总体复
杂度。
开始写的时候这些部分都用函数好了，框架写完了，再慢慢implement这些函数。
【在 l***i 的大作中提到】
: 这个凌行就不对把，四条边都是L长度不一定是正方形阿
杂度。
开始写的时候这些部分都用函数好了，框架写完了，再慢慢implement这些函数。
【在 l***i 的大作中提到】
: 这个凌行就不对把，四条边都是L长度不一定是正方形阿
f*e
18 楼
check斜率乘积=-1。
【在 R********y 的大作中提到】
: 找出四个点之后，随便检查某一个角是不是直角，只要const time啊，又不影响总体复
: 杂度。
: 开始写的时候这些部分都用函数好了，框架写完了，再慢慢implement这些函数。
【在 R********y 的大作中提到】
: 找出四个点之后，随便检查某一个角是不是直角，只要const time啊，又不影响总体复
: 杂度。
: 开始写的时候这些部分都用函数好了，框架写完了，再慢慢implement这些函数。
K*n
19 楼
那这个不如检查对角线对着的点的距离是不是根号2*L。
检查直角原理没什么难的，写起来又要费一番功夫。
【在 R********y 的大作中提到】
: 找出四个点之后，随便检查某一个角是不是直角，只要const time啊，又不影响总体复
: 杂度。
: 开始写的时候这些部分都用函数好了，框架写完了，再慢慢implement这些函数。
检查直角原理没什么难的，写起来又要费一番功夫。
【在 R********y 的大作中提到】
: 找出四个点之后，随便检查某一个角是不是直角，只要const time啊，又不影响总体复
: 杂度。
: 开始写的时候这些部分都用函数好了，框架写完了，再慢慢implement这些函数。
d*g
20 楼
是蛮恐怖。。。
【在 K*********n 的大作中提到】
: 是啊……
: 所以我现在还在郁闷，不到半小时让写个这个。
h*n
21 楼
可以O(n^2)
【在 K*********n 的大作中提到】
: 输入是一组二维空间里面的点，由x,y值表示。
: 给定一个长度L，
: 要求返回所有由这些点形成的边长为L的正方形。
: 刚才电面一个小公司，没做出来，只想到了hash table。必挂了。
【在 K*********n 的大作中提到】
: 输入是一组二维空间里面的点，由x,y值表示。
: 给定一个长度L，
: 要求返回所有由这些点形成的边长为L的正方形。
: 刚才电面一个小公司，没做出来，只想到了hash table。必挂了。
p*2
22 楼
新人轻拍，可以这样不
先建立一个hashmap，判断点存在于出入中不，这样是n
for每对A，B如果距离为sqrt(2)L，这样是n^2
算出对应另外构成正方形的2点的坐标（已知对角线可以唯一确定一个正方形？这样
能求出另外2点），然后再丢到hashmap看存在不，都存在就输出
for loop里面是常数，所以是n+n^2
求大牛指教
先建立一个hashmap，判断点存在于出入中不，这样是n
for每对A，B如果距离为sqrt(2)L，这样是n^2
算出对应另外构成正方形的2点的坐标（已知对角线可以唯一确定一个正方形？这样
能求出另外2点），然后再丢到hashmap看存在不，都存在就输出
for loop里面是常数，所以是n+n^2
求大牛指教
A*u
23 楼
变态啊
【在 K*********n 的大作中提到】
: 输入是一组二维空间里面的点，由x,y值表示。
: 给定一个长度L，
: 要求返回所有由这些点形成的边长为L的正方形。
: 刚才电面一个小公司，没做出来，只想到了hash table。必挂了。
【在 K*********n 的大作中提到】
: 输入是一组二维空间里面的点，由x,y值表示。
: 给定一个长度L，
: 要求返回所有由这些点形成的边长为L的正方形。
: 刚才电面一个小公司，没做出来，只想到了hash table。必挂了。
j*y
24 楼
这不就是O(n^2)么，不需要排序啊
【在 R********y 的大作中提到】
: 为每一个点创立一个array，里面按顺序存放所有到这个点距离为L的点。
: 把每个array看成一个set，找出所有交集为2的set。
: O(n^2 log n)
【在 R********y 的大作中提到】
: 为每一个点创立一个array，里面按顺序存放所有到这个点距离为L的点。
: 把每个array看成一个set，找出所有交集为2的set。
: O(n^2 log n)
T*a
25 楼
这是哪家呀？够变态的。
【在 K*********n 的大作中提到】
: 输入是一组二维空间里面的点，由x,y值表示。
: 给定一个长度L，
: 要求返回所有由这些点形成的边长为L的正方形。
: 刚才电面一个小公司，没做出来，只想到了hash table。必挂了。
【在 K*********n 的大作中提到】
: 输入是一组二维空间里面的点，由x,y值表示。
: 给定一个长度L，
: 要求返回所有由这些点形成的边长为L的正方形。
: 刚才电面一个小公司，没做出来，只想到了hash table。必挂了。
K*n
26 楼
求教
【在 h****n 的大作中提到】
: 可以O(n^2)
【在 h****n 的大作中提到】
: 可以O(n^2)
K*n
27 楼
问题是，怎么算春另外构成正方形的2点的坐标？你得在所有点里面找对不对？那又暴力
了。
【在 p********2 的大作中提到】
: 新人轻拍，可以这样不
: 先建立一个hashmap，判断点存在于出入中不，这样是n
: for每对A，B如果距离为sqrt(2)L，这样是n^2
: 算出对应另外构成正方形的2点的坐标（已知对角线可以唯一确定一个正方形？这样
: 能求出另外2点），然后再丢到hashmap看存在不，都存在就输出
: for loop里面是常数，所以是n+n^2
: 求大牛指教
了。
【在 p********2 的大作中提到】
: 新人轻拍，可以这样不
: 先建立一个hashmap，判断点存在于出入中不，这样是n
: for每对A，B如果距离为sqrt(2)L，这样是n^2
: 算出对应另外构成正方形的2点的坐标（已知对角线可以唯一确定一个正方形？这样
: 能求出另外2点），然后再丢到hashmap看存在不，都存在就输出
: for loop里面是常数，所以是n+n^2
: 求大牛指教
D*d
28 楼
想到一个 O(n^2 lg(n) ) 的解法：
1. sort on x axis, for the same x, sort on y both ascend-- O(nlg(n))
2. for each pair (n1,n4) check d(n1,n4) == sqrt(2) L
if yes, solve a linear equation, get the axis of other two nodes (n2,n3)
of the sqare with (n1,n4) as diagonal nodes
check the existences of (n2,n3) in sorted list
n^2 * lg(n) = O(n^2lg(n))
1. sort on x axis, for the same x, sort on y both ascend-- O(nlg(n))
2. for each pair (n1,n4) check d(n1,n4) == sqrt(2) L
if yes, solve a linear equation, get the axis of other two nodes (n2,n3)
of the sqare with (n1,n4) as diagonal nodes
check the existences of (n2,n3) in sorted list
n^2 * lg(n) = O(n^2lg(n))
K*n
29 楼
其实我发这个题上来就看看大家的评论，这个题作为一个25分钟的电面题是否过分。有
助于我对面试难度和我的水平的评判。看到这里，我等低水平没追求的（有个offer就行
）也就大致心安一些了，看来是挺过分……
就怕这种题算很一般般的面试题，那我真要全聚德了。
【在 A**u 的大作中提到】
: 变态啊
助于我对面试难度和我的水平的评判。看到这里，我等低水平没追求的（有个offer就行
）也就大致心安一些了，看来是挺过分……
就怕这种题算很一般般的面试题，那我真要全聚德了。
【在 A**u 的大作中提到】
: 变态啊
K*n
30 楼
要排序，否则第二部怎么能在n^2 log n完成
【在 j******y 的大作中提到】
: 这不就是O(n^2)么，不需要排序啊
【在 j******y 的大作中提到】
: 这不就是O(n^2)么，不需要排序啊
K*n
31 楼
OkCupid，不提也罢……他家的主页实在是…………
【在 T******a 的大作中提到】
: 这是哪家呀？够变态的。
【在 T******a 的大作中提到】
: 这是哪家呀？够变态的。
j*y
32 楼
不是n^2就可以了么，不用排序，随便给每个点一个index就够了吧
【在 K*********n 的大作中提到】
: 要排序，否则第二部怎么能在n^2 log n完成
【在 K*********n 的大作中提到】
: 要排序，否则第二部怎么能在n^2 log n完成
l*i
33 楼
我直觉这个地方要用到很多的graph theory
【在 K*********n 的大作中提到】
: OkCupid，不提也罢……他家的主页实在是…………
【在 K*********n 的大作中提到】
: OkCupid，不提也罢……他家的主页实在是…………
p*2
34 楼
不需要去点里面找，对每2点，距离是根号2L了，可以唯一确定一个边长L正方
形吧，用数学公式直接算另外的2个点，是常数时间，然后算出的这对应2个点丢到
hashmap里面
去看存在不，都存在就输出
大牛指正
暴力
【在 K*********n 的大作中提到】
: 问题是，怎么算春另外构成正方形的2点的坐标？你得在所有点里面找对不对？那又暴力
: 了。
形吧，用数学公式直接算另外的2个点，是常数时间，然后算出的这对应2个点丢到
hashmap里面
去看存在不，都存在就输出
大牛指正
暴力
【在 K*********n 的大作中提到】
: 问题是，怎么算春另外构成正方形的2点的坐标？你得在所有点里面找对不对？那又暴力
: 了。
K*n
35 楼
nice，this is part of THE solution
【在 p********2 的大作中提到】
: 不需要去点里面找，对每2点，距离是根号2L了，可以唯一确定一个边长L正方
: 形吧，用数学公式直接算另外的2个点，是常数时间，然后算出的这对应2个点丢到
: hashmap里面
: 去看存在不，都存在就输出
: 大牛指正
:
: 暴力
【在 p********2 的大作中提到】
: 不需要去点里面找，对每2点，距离是根号2L了，可以唯一确定一个边长L正方
: 形吧，用数学公式直接算另外的2个点，是常数时间，然后算出的这对应2个点丢到
: hashmap里面
: 去看存在不，都存在就输出
: 大牛指正
:
: 暴力
c*t
36 楼
brute force 可以是N^2吧。
把所有点放入hashtable做key
对每一个点p1，遍历其他点找距离为L的点p2, 这时候p3,p4可以计算出，到hashtable
里找有没有。
面试官是不是a3啊，这么狠？
【在 K*********n 的大作中提到】
: brute force至少O(n^4)，我当时也没办法了，我说我就brute force，他说不行，没技
: 术含量。
: 前面问题都问得很好，突然上来个这个，擦。
把所有点放入hashtable做key
对每一个点p1，遍历其他点找距离为L的点p2, 这时候p3,p4可以计算出，到hashtable
里找有没有。
面试官是不是a3啊，这么狠？
【在 K*********n 的大作中提到】
: brute force至少O(n^4)，我当时也没办法了，我说我就brute force，他说不行，没技
: 术含量。
: 前面问题都问得很好，突然上来个这个，擦。
c*t
37 楼
嗯，看来前面同学已经给出这样的解法了。说出解法还好，如果还要求写出codes,那真
是变态。还有要是点很多，hashmap用不了就更惨了。
hashtable
【在 c********t 的大作中提到】
: brute force 可以是N^2吧。
: 把所有点放入hashtable做key
: 对每一个点p1，遍历其他点找距离为L的点p2, 这时候p3,p4可以计算出，到hashtable
: 里找有没有。
: 面试官是不是a3啊，这么狠？
是变态。还有要是点很多，hashmap用不了就更惨了。
hashtable
【在 c********t 的大作中提到】
: brute force 可以是N^2吧。
: 把所有点放入hashtable做key
: 对每一个点p1，遍历其他点找距离为L的点p2, 这时候p3,p4可以计算出，到hashtable
: 里找有没有。
: 面试官是不是a3啊，这么狠？
K*n
38 楼
白哥哥。前面的开放性问题一个比一个答得让我觉得舒坦，他feedback也很好，突然说
，还有25分钟，写个代码……
hashtable
【在 c********t 的大作中提到】
: brute force 可以是N^2吧。
: 把所有点放入hashtable做key
: 对每一个点p1，遍历其他点找距离为L的点p2, 这时候p3,p4可以计算出，到hashtable
: 里找有没有。
: 面试官是不是a3啊，这么狠？
，还有25分钟，写个代码……
hashtable
【在 c********t 的大作中提到】
: brute force 可以是N^2吧。
: 把所有点放入hashtable做key
: 对每一个点p1，遍历其他点找距离为L的点p2, 这时候p3,p4可以计算出，到hashtable
: 里找有没有。
: 面试官是不是a3啊，这么狠？
g*e
39 楼
这些点是正方形的角吗？还是边上的点也可以？
K*n
40 楼
当然是角
【在 g*********e 的大作中提到】
: 这些点是正方形的角吗？还是边上的点也可以？
【在 g*********e 的大作中提到】
: 这些点是正方形的角吗？还是边上的点也可以？
l*b
41 楼
啊，想到这个发现已经被写了。。。
【在 p********2 的大作中提到】
: 不需要去点里面找，对每2点，距离是根号2L了，可以唯一确定一个边长L正方
: 形吧，用数学公式直接算另外的2个点，是常数时间，然后算出的这对应2个点丢到
: hashmap里面
: 去看存在不，都存在就输出
: 大牛指正
:
: 暴力
【在 p********2 的大作中提到】
: 不需要去点里面找，对每2点，距离是根号2L了，可以唯一确定一个边长L正方
: 形吧，用数学公式直接算另外的2个点，是常数时间，然后算出的这对应2个点丢到
: hashmap里面
: 去看存在不，都存在就输出
: 大牛指正
:
: 暴力
R*g
42 楼
for（ 遍历一堆点中 4点（a, b,c, d )组合 ）
｛
计算 ab，ac, ad, bc,bd, cd 6条边的长度，
if （ 4条边 ＝＝ L ）&&（ 剩余2条边 相等）
pickup（ a, b, c ,d ).
｝
当然在 程序和效率 上还可以优化一下。
重点是 通过边长判断，你要是搞 角度 斜率就 out 了
｛
计算 ab，ac, ad, bc,bd, cd 6条边的长度，
if （ 4条边 ＝＝ L ）&&（ 剩余2条边 相等）
pickup（ a, b, c ,d ).
｝
当然在 程序和效率 上还可以优化一下。
重点是 通过边长判断，你要是搞 角度 斜率就 out 了
g*e
43 楼
把所有的点存入hashtable1
把所有点pair 存入 hashtable2
result
for each 点pair in hash2
check whether the other 2 points are in hash1 (有两种可能）
if(found such other-2-points x, y）
result.uniqueAppend(a,b,x,y);
endfor
O(n^2)
把所有点pair 存入 hashtable2
result
for each 点pair in hash2
check whether the other 2 points are in hash1 (有两种可能）
if(found such other-2-points x, y）
result.uniqueAppend(a,b,x,y);
endfor
O(n^2)
相关阅读
SEVIS和学校的毕业时间不一致有问题吗？悲催的g onsite有关CS课程选择，请大牛帮忙看一下BNon-PP升级PPWhat's mean of "Your Case Status:Post Decision Activity"??求BB referH1B or 工作选择， 新手求见意uscis.gov 见鬼去吧！ Opt Extension: Card production. H1B Approved..Non-PP Adv CSC ApprovedPP的是不是应该在1号前有结果？sf downtown中型startup招人H1B没抽中，求建议Google SET/TE职位内部推荐Google hiring manager的电话大概会聊些啥？SF还是NYC？Offer选择 真诚求建议electrical engineer position @OhioH1B没抽中，OPT延期可以回国么J2没wavier能转成F1吗RQ/RP 内牛满面 另外换工作的问题