Approximate Pi from Random Points
Company: Toma
Role: Frontend Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
You are given an array `pts` of points in the unit square. Each point is represented as an array of two numbers `[x, y]`, where `0 <= x <= 1` and `0 <= y <= 1`.
A point lies inside the quarter circle of radius `1` if `x*x + y*y <= 1`.
Write a function `approx(pts)` that returns an approximation of `pi` using the fraction of points that fall inside the quarter circle.
Assume:
- `pts` is never `null`
- `pts` contains at least one point
- every point has exactly two numeric coordinates
Example function signature:
```javascript
function approx(pts) {
return 0;
}
```
Quick Answer: This question evaluates a candidate's understanding of Monte Carlo estimation, basic Euclidean geometry, probability, and numerical reasoning when using random sampling to approximate mathematical constants.
You are given an array `pts` of points in the unit square `[0, 1] x [0, 1]`. Each point is represented as `[x, y]`. A point lies inside the quarter circle of radius `1` centered at the origin if `x*x + y*y <= 1`.
Use the fraction of points that fall inside the quarter circle to approximate `pi`. Since the area of the quarter circle is `pi / 4` and the area of the unit square is `1`, the approximation is:
`pi ≈ 4 * (number of points inside the quarter circle) / (total number of points)`
Write a function that returns this approximation as a floating-point number.
Constraints
- `1 <= len(pts) <= 100000`
- Each point has exactly two numeric coordinates
- `0 <= x <= 1` and `0 <= y <= 1` for every point
Examples
Input: [[1, 0]]
Expected Output: 4.0
Explanation: The single point lies exactly on the circle boundary, so it counts as inside. Approximation = 4 * 1 / 1 = 4.0.
Input: [[1, 0], [0, 1], [1, 1], [0.5, 0.5]]
Expected Output: 3.0
Explanation: Three points are inside or on the boundary: [1,0], [0,1], and [0.5,0.5]. One point, [1,1], is outside. Approximation = 4 * 3 / 4 = 3.0.
Hints
- First count how many points satisfy `x*x + y*y <= 1`.
- The ratio `inside / total` estimates the area of the quarter circle, which is `pi / 4`.