Problem:
Given n points on a 2D plane, find the equation of the line with maximum number of collinear points. What is the time complexity of your algorithm?
Quant, Math & Computer Science Puzzles for Interview Preparation & Brain Teasing
A collection of ~225 Puzzles with Solutions (classified by difficulty and topic)
Source: Sent to me by Gaurav Sinha Problem: Siddhant writes a Maths test and correctly answers 5 out of 6 Arithmetic questions and 20...
1) Take any point x and find the slope from x to every other point - O(n)
ReplyDelete2) Find the number of points for each slope by hashing or building a binary search tree - O(nlogn)
3) Find the max number of point for any slope
4) Repeat this for every point and find the max among them
Total time complexity - O(n*n*logn)
a line is defined by the equation ax+b = y;
ReplyDeleteInitialize a hashmap with key (a,b) and an integer value;
for each edge of two points :
compute a,b and increment the integer value associated with (a,b) in the hashmap
O(n*n)
compute max of the values in the hashmap and return key associated
O(n*n)
Total time complexity O(n*n)
a line is defined by its equation ax+b = y;
ReplyDeleteInitialize a hashmap with key (a, b) and integer value
for each edge of two points, compute a and b,
increment the value associated with key (a,b)
O(n*n)
compute the max of values in the hashmap and return key associated
O(n*n)
Total time complexity : O(n*n)
Can we use something like this ?
ReplyDeleteSort the points based on x and y coordinates.
Then basically use DP approach to get the longest increasing sequence with the same slope