bilew89378's blog

By bilew89378, history, 6 weeks ago, In English

hi folks

someone posted a question that got me curious if this is solvable, none of blind lurkers have been able to solve this. asking for algo experts to chip in from cf community

Question: "given 100K points within coordinate system, find the coordinates of smallest square that contains cluster of at least 15% of all points"

It seems Petr was interviewer for this candidate as only he can solve this in < 45 minute

  • Vote: I like it
  • +13
  • Vote: I do not like it

6 weeks ago, # |
Rev. 3   Vote: I like it +6 Vote: I do not like it

I think this can be solved using binary search on the size of square. When the size of square is fixed, you can iterate on the $$$x$$$ coordinate, rejecting points with $$$x-k$$$ coordinates. Maintain the $$$y$$$ coordinates in a set and just just check how many points are in the set with y-coordinate less than or equal to current y-coordinate (by Fenwick tree/ ordered-set). Time complexity will be $$$O(nlog(n)log(c)$$$, where $$$c$$$ is the maximum coordinate.