K*********n
发帖数: 2852 | 1 输入是一组二维空间里面的点，由x,y值表示。
给定一个长度L，
要求返回所有由这些点形成的边长为L的正方形。
刚才电面一个小公司，没做出来，只想到了hash table。必挂了。 |
C***U
发帖数: 2406 | 2 我的想法 先把所有点 按照行分成group
然后每个group 取出两个点的列坐标hash
然后行和行之间check
【在 K*********n 的大作中提到】
: 输入是一组二维空间里面的点，由x,y值表示。
: 给定一个长度L，
: 要求返回所有由这些点形成的边长为L的正方形。
: 刚才电面一个小公司，没做出来，只想到了hash table。必挂了。
|
K*********n
发帖数: 2852 | 3 没说square的边是和坐标轴平行的，可以是斜着的。
说实话这个题我不能说多么难，但是25分钟让我搞定算法和code，我没这个能力，我觉
得电面这个有些过分，对我这个水平来说。
【在 C***U 的大作中提到】
: 我的想法 先把所有点 按照行分成group
: 然后每个group 取出两个点的列坐标hash
: 然后行和行之间check
|
C***U
发帖数: 2406 | 4 好吧 想简单了
【在 K*********n 的大作中提到】
: 没说square的边是和坐标轴平行的，可以是斜着的。
: 说实话这个题我不能说多么难，但是25分钟让我搞定算法和code，我没这个能力，我觉
: 得电面这个有些过分，对我这个水平来说。
|
K*********n
发帖数: 2852 | 5 我现在很想骂娘，对这个题。
可能水平高的人会说，还是骂我自己水平差吧。但是确实是在我能力范围之外了。
【在 C***U 的大作中提到】
: 好吧 想简单了
|
C***U
发帖数: 2406 | 6 题目看错了
原来是给定长度的正方形
【在 K*********n 的大作中提到】
: 输入是一组二维空间里面的点，由x,y值表示。
: 给定一个长度L，
: 要求返回所有由这些点形成的边长为L的正方形。
: 刚才电面一个小公司，没做出来，只想到了hash table。必挂了。
|
K*********n
发帖数: 2852 | 7 brute force至少O(n^4)，我当时也没办法了，我说我就brute force，他说不行，没技
术含量。
前面问题都问得很好，突然上来个这个，擦。
【在 C***U 的大作中提到】
: 题目看错了
: 原来是给定长度的正方形
|
K*********n
发帖数: 2852 | 8 你说说怎么做
【在 C***U 的大作中提到】
: 题目看错了
: 原来是给定长度的正方形
|
R********y
发帖数: 88 | 9 为每一个点创立一个array，里面按顺序存放所有到这个点距离为L的点。
把每个array看成一个set，找出所有交集为2的set。
O(n^2 log n) |
K*********n
发帖数: 2852 | 10 第一步为n^2
第二步如何在log n内完成呢？
【在 R********y 的大作中提到】
: 为每一个点创立一个array，里面按顺序存放所有到这个点距离为L的点。
: 把每个array看成一个set，找出所有交集为2的set。
: O(n^2 log n)
|
|
|
D**********d
发帖数: 849 | 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)
|
R********y
发帖数: 88 | 12 两步都是O(n^2 log n)，加法关系...
【在 K*********n 的大作中提到】
: 第一步为n^2
: 第二步如何在log n内完成呢？
|
K*********n
发帖数: 2852 | 13 好像差不多
【在 R********y 的大作中提到】
: 为每一个点创立一个array，里面按顺序存放所有到这个点距离为L的点。
: 把每个array看成一个set，找出所有交集为2的set。
: O(n^2 log n)
|
K*********n
发帖数: 2852 | 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)
:
|
l***i
发帖数: 1309 | 15 这个凌行就不对把，四条边都是L长度不一定是正方形阿
【在 R********y 的大作中提到】
: 为每一个点创立一个array，里面按顺序存放所有到这个点距离为L的点。
: 把每个array看成一个set，找出所有交集为2的set。
: O(n^2 log n)
|
K*********n
发帖数: 2852 | 16 是啊……
所以我现在还在郁闷，不到半小时让写个这个。
【在 l***i 的大作中提到】
: 这个凌行就不对把，四条边都是L长度不一定是正方形阿
|
R********y
发帖数: 88 | 17 找出四个点之后，随便检查某一个角是不是直角，只要const time啊，又不影响总体复
杂度。
开始写的时候这些部分都用函数好了，框架写完了，再慢慢implement这些函数。
【在 l***i 的大作中提到】
: 这个凌行就不对把，四条边都是L长度不一定是正方形阿
|
f*****e
发帖数: 2992 | 18 check斜率乘积=-1。
【在 R********y 的大作中提到】
: 找出四个点之后，随便检查某一个角是不是直角，只要const time啊，又不影响总体复
: 杂度。
: 开始写的时候这些部分都用函数好了，框架写完了，再慢慢implement这些函数。
|
K*********n
发帖数: 2852 | 19 那这个不如检查对角线对着的点的距离是不是根号2*L。
检查直角原理没什么难的，写起来又要费一番功夫。
【在 R********y 的大作中提到】
: 找出四个点之后，随便检查某一个角是不是直角，只要const time啊，又不影响总体复
: 杂度。
: 开始写的时候这些部分都用函数好了，框架写完了，再慢慢implement这些函数。
|
d*********g
发帖数: 154 | 20
是蛮恐怖。。。
【在 K*********n 的大作中提到】
: 是啊……
: 所以我现在还在郁闷，不到半小时让写个这个。
|
|
|
h****n
发帖数: 2094 | 21 可以O(n^2)
【在 K*********n 的大作中提到】
: 输入是一组二维空间里面的点，由x,y值表示。
: 给定一个长度L，
: 要求返回所有由这些点形成的边长为L的正方形。
: 刚才电面一个小公司，没做出来，只想到了hash table。必挂了。
|
p********2
发帖数: 123 | 22 新人轻拍，可以这样不
先建立一个hashmap，判断点存在于出入中不，这样是n
for每对A，B如果距离为sqrt(2)L，这样是n^2
算出对应另外构成正方形的2点的坐标（已知对角线可以唯一确定一个正方形？这样
能求出另外2点），然后再丢到hashmap看存在不，都存在就输出
for loop里面是常数，所以是n+n^2
求大牛指教 |
A**u
发帖数: 2458 | 23 变态啊
【在 K*********n 的大作中提到】
: 输入是一组二维空间里面的点，由x,y值表示。
: 给定一个长度L，
: 要求返回所有由这些点形成的边长为L的正方形。
: 刚才电面一个小公司，没做出来，只想到了hash table。必挂了。
|
j******y
发帖数: 2578 | 24 这不就是O(n^2)么，不需要排序啊
【在 R********y 的大作中提到】
: 为每一个点创立一个array，里面按顺序存放所有到这个点距离为L的点。
: 把每个array看成一个set，找出所有交集为2的set。
: O(n^2 log n)
|
T******a
发帖数: 169 | 25 这是哪家呀？够变态的。
【在 K*********n 的大作中提到】
: 输入是一组二维空间里面的点，由x,y值表示。
: 给定一个长度L，
: 要求返回所有由这些点形成的边长为L的正方形。
: 刚才电面一个小公司，没做出来，只想到了hash table。必挂了。
|
K*********n
发帖数: 2852 | 26 求教
【在 h****n 的大作中提到】
: 可以O(n^2)
|
K*********n
发帖数: 2852 | 27 问题是，怎么算春另外构成正方形的2点的坐标？你得在所有点里面找对不对？那又暴力
了。
【在 p********2 的大作中提到】
: 新人轻拍，可以这样不
: 先建立一个hashmap，判断点存在于出入中不，这样是n
: for每对A，B如果距离为sqrt(2)L，这样是n^2
: 算出对应另外构成正方形的2点的坐标（已知对角线可以唯一确定一个正方形？这样
: 能求出另外2点），然后再丢到hashmap看存在不，都存在就输出
: for loop里面是常数，所以是n+n^2
: 求大牛指教
|
D**********d
发帖数: 849 | 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)) |
K*********n
发帖数: 2852 | 29 其实我发这个题上来就看看大家的评论，这个题作为一个25分钟的电面题是否过分。有
助于我对面试难度和我的水平的评判。看到这里，我等低水平没追求的（有个offer就行
）也就大致心安一些了，看来是挺过分……
就怕这种题算很一般般的面试题，那我真要全聚德了。
【在 A**u 的大作中提到】
: 变态啊
|
K*********n
发帖数: 2852 | 30 要排序，否则第二部怎么能在n^2 log n完成
【在 j******y 的大作中提到】
: 这不就是O(n^2)么，不需要排序啊
|
|
|
K*********n
发帖数: 2852 | 31 OkCupid，不提也罢……他家的主页实在是…………
【在 T******a 的大作中提到】
: 这是哪家呀？够变态的。
|
j******y
发帖数: 2578 | 32 不是n^2就可以了么，不用排序，随便给每个点一个index就够了吧
【在 K*********n 的大作中提到】
: 要排序，否则第二部怎么能在n^2 log n完成
|
l***i
发帖数: 1309 | 33 我直觉这个地方要用到很多的graph theory
【在 K*********n 的大作中提到】
: OkCupid，不提也罢……他家的主页实在是…………
|
p********2
发帖数: 123 | 34 不需要去点里面找，对每2点，距离是根号2L了，可以唯一确定一个边长L正方
形吧，用数学公式直接算另外的2个点，是常数时间，然后算出的这对应2个点丢到
hashmap里面
去看存在不，都存在就输出
大牛指正
暴力
【在 K*********n 的大作中提到】
: 问题是，怎么算春另外构成正方形的2点的坐标？你得在所有点里面找对不对？那又暴力
: 了。
|
K*********n
发帖数: 2852 | 35 nice，this is part of THE solution
【在 p********2 的大作中提到】
: 不需要去点里面找，对每2点，距离是根号2L了，可以唯一确定一个边长L正方
: 形吧，用数学公式直接算另外的2个点，是常数时间，然后算出的这对应2个点丢到
: hashmap里面
: 去看存在不，都存在就输出
: 大牛指正
:
: 暴力
|
c********t
发帖数: 5706 | 36 brute force 可以是N^2吧。
把所有点放入hashtable做key
对每一个点p1，遍历其他点找距离为L的点p2, 这时候p3,p4可以计算出，到hashtable
里找有没有。
面试官是不是a3啊，这么狠？
【在 K*********n 的大作中提到】
: brute force至少O(n^4)，我当时也没办法了，我说我就brute force，他说不行，没技
: 术含量。
: 前面问题都问得很好，突然上来个这个，擦。
|
c********t
发帖数: 5706 | 37 嗯，看来前面同学已经给出这样的解法了。说出解法还好，如果还要求写出codes,那真
是变态。还有要是点很多，hashmap用不了就更惨了。
hashtable
【在 c********t 的大作中提到】
: brute force 可以是N^2吧。
: 把所有点放入hashtable做key
: 对每一个点p1，遍历其他点找距离为L的点p2, 这时候p3,p4可以计算出，到hashtable
: 里找有没有。
: 面试官是不是a3啊，这么狠？
|
K*********n
发帖数: 2852 | 38 白哥哥。前面的开放性问题一个比一个答得让我觉得舒坦，他feedback也很好，突然说
，还有25分钟，写个代码……
hashtable
【在 c********t 的大作中提到】
: brute force 可以是N^2吧。
: 把所有点放入hashtable做key
: 对每一个点p1，遍历其他点找距离为L的点p2, 这时候p3,p4可以计算出，到hashtable
: 里找有没有。
: 面试官是不是a3啊，这么狠？
|
g*********e
发帖数: 14401 | |
K*********n
发帖数: 2852 | 40 当然是角
【在 g*********e 的大作中提到】
: 这些点是正方形的角吗？还是边上的点也可以？
|
|
|
l*******b
发帖数: 2586 | 41 啊，想到这个发现已经被写了。。。
【在 p********2 的大作中提到】
: 不需要去点里面找，对每2点，距离是根号2L了，可以唯一确定一个边长L正方
: 形吧，用数学公式直接算另外的2个点，是常数时间，然后算出的这对应2个点丢到
: hashmap里面
: 去看存在不，都存在就输出
: 大牛指正
:
: 暴力
|
R****g
发帖数: 16 | 42 for（ 遍历一堆点中 4点（a, b,c, d )组合 ）
｛
计算 ab，ac, ad, bc,bd, cd 6条边的长度，
if （ 4条边 ＝＝ L ）&&（ 剩余2条边 相等）
pickup（ a, b, c ,d ).
｝
当然在 程序和效率 上还可以优化一下。
重点是 通过边长判断，你要是搞 角度 斜率就 out 了 |
g*********e
发帖数: 14401 | 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) |
