hi folks
https://www.teamblind.com/post/Very-Tough-Google-Interview---Heartbroken-B772z3Vq
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
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.