How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Microsoft.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Microsoft during technical interviews.

Find maximum collinear points | Microsoft Coding Question

Quick Overview

This question evaluates understanding of planar geometry and algorithmic reasoning for identifying collinearity, including handling duplicate points and edge cases in integer coordinates.

Find maximum collinear points

Company: Microsoft

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Given a list of 2D points with integer coordinates, return the **maximum number of points that lie on the same straight line**. ### Input - `points`: a list of `n` points, where each point is `[x, y]`. ### Output - An integer: the maximum count of points that are collinear. ### Constraints - `1 <= n <= 2000` - Coordinates are integers in a reasonable range (e.g., `[-10^4, 10^4]`). - Duplicate points may exist. ### Notes - Lines can be vertical, horizontal, or any slope. - The result should count all points on the best line, including duplicates.

Quick Answer: This question evaluates understanding of planar geometry and algorithmic reasoning for identifying collinearity, including handling duplicate points and edge cases in integer coordinates.

Given a list of 2D points with integer coordinates, return the maximum number of points that lie on the same straight line. Points may be duplicated, and each duplicate counts as a separate point. Lines can be vertical, horizontal, or have any slope.

Constraints

1 <= len(points) <= 2000
-10^4 <= x_i, y_i <= 10^4
Duplicate points may exist and must be counted in the result

Examples

Input: ([[1,1],[2,2],[3,3]],)

Expected Output: 3

Explanation: All three points lie on the line y = x.

Input: ([[1,1],[1,1],[2,2],[3,3]],)

Expected Output: 4

Explanation: The duplicate point [1,1] counts separately, and all four points lie on the same line.

Input: ([[2,3],[2,4],[2,5],[0,0]],)

Expected Output: 3

Explanation: The points [2,3], [2,4], and [2,5] lie on the vertical line x = 2.

Input: ([],)

Expected Output: 0

Explanation: There are no points, so the answer is 0.

Input: ([[0,0],[0,0],[0,0]],)

Expected Output: 3

Explanation: All three points are duplicates of the same location, so they all count on the same line.

Input: ([[0,0],[1,1],[1,-1],[2,2],[3,3],[2,-2]],)

Expected Output: 4

Explanation: The points [0,0], [1,1], [2,2], and [3,3] are collinear on y = x.

Hints

Try fixing one point as an anchor and grouping all other points by the line they form with that anchor.
Avoid floating-point slopes. Store each slope as a reduced `(dy, dx)` pair using `gcd`, and use a consistent sign convention. Count duplicate points separately.

Last updated: Jun 5, 2026

Loading coding console...