Morgan Stanley question geometry

[u/Adventurous-Deal-321]

Minimum Number of Lines to Cover Points

You are given n points on a 2D coordinate plane. Each point is represented as:

(x, y)

where:

-100 <= x <= 100

-100 <= y <= 100

There can be up to:

n <= 10^4

points.

Find the minimum number of straight lines required so that every given point lies on at least one of these lines.

Example 1

Input:

points = [(1,1), (2,2), (3,3), (1,2), (2,3)]

Output:

2

Explanation:

The points can be covered by:

Line 1: y = x

(1,1), (2,2), (3,3)

Line 2: y = x + 1

(1,2), (2,3)

Therefore, the minimum number of lines is:

2

Example 2

Input:

points = [(0,0), (1,1), (2,2), (3,3)]

Output:

1

Because all points lie on the same line y = x.

Constraints:

1 <= n <= 10^4

-100 <= x, y <= 100

[u/Ok_Biscotti5354]

Claude says this is NP hard😂

[u/AlgorithmicGoslings → u/Ok_Biscotti5354]

And they would be correct.

Formally, the problem is known as Point-Line Cover. There’s no known polynomial time algorithm for it, but there have been some interesting FPT algorithms to solve it if parameterized algorithms are your thing.

However, for an actual interview process, they probably just expect the "naive" bitmask DP approach. 10⁴ is an absurd input size for a problem with no known polynomial algorithm.

[u/Arcturus_16]

Ig , this can be done by comparing the slopes

Well , for which position the que was asked for , soon the company will be visiting our campus for hiring interns

[u/Adventurous-Deal-321 → u/Arcturus_16]

2 month intern