Implement uniform sampling in squares

Q: Implement uniform sampling in squares

This question evaluates a candidate's competency in probabilistic sampling, computational geometry, API and data-structure design, and numerical robustness for unbiased random point generation over geometric regions.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Implement a class Square representing an axis-aligned square on the 2D plane that supports sampling a uniformly random point inside the square. Then extend your design to handle an array of N non-overlapping squares and support picking a uniformly random point from the union of all squares (i.e., each point’s probability is proportional to its square’s area). Specify the APIs you would expose, the data structures used (e.g., prefix sums over areas), the algorithm for sampling, time/space complexity, and how you would avoid bias from floating-point precision.

Implement uniform sampling in squares

Overview

Comments (0)