Google Interview Question Software Engineer / Developers
Country: United States
Interview Type: In-Person
public class StraightLineWithMaxPoints {
private static interface Graph {
boolean isPointPresent(long x, long y);
long getLength();
long getWidth();
}
private static class ArrayGraph implements Graph {
private final int[][] a;
private final boolean mustTranspose;
/**
* @param a Assumed to be a fully-populated 2-D (0,1) array.
*/
private ArrayGraph(int[][] a) {
this.a = a;
mustTranspose = a.length > a[0].length;
}
@Override
public boolean isPointPresent(long x, long y) {
return mustTranspose?a[(int)y][(int)x]>0:a[(int)x][(int)y]>0;
}
@Override
public long getLength() {
return mustTranspose?a.length:a[0].length;
}
@Override
public long getWidth() {
return mustTranspose?a[0].length:a.length;
}
}
private static class Pair<T> {
T x;
T y;
Pair() {}
Pair(T x, T y) {
this.x = x;
this.y = y;
}
public String toString() {
return "(" + x + "," + y + ")";
}
}
private static class Result {
Pair<Pair<Long>> line;
long pointCount;
public String toString() {
return line + "[" + pointCount + "]";
}
}
public static void main(String[] args) {
ArrayGraph ag1 = new ArrayGraph(new int[][] { new int[] {0, 1, 0}, new int[] {0, 1, 0} });
ArrayGraph ag2 = new ArrayGraph(new int[][] { new int[] {0, 1, 0}, new int[] {0, 0, 1} });
ArrayGraph ag3 = new ArrayGraph(new int[][] { new int[] {0, 1, 0}, new int[] {1, 0, 0} });
ArrayGraph ag4 = new ArrayGraph(new int[][] { new int[] {0, 1, 0}, new int[] {1, 0, 0}, new int[] {0, 0, 0} });
ArrayGraph ag5 = new ArrayGraph(new int[][] { new int[] {0, 0, 1, 0}, new int[] {0, 0, 0, 1}, new int[] {0, 0, 0, 0} });
ArrayGraph ag6 = new ArrayGraph(new int[][] { new int[] {0, 1, 0, 0}, new int[] {0, 0, 1, 0}, new int[] {0, 0, 0, 1} });
ArrayGraph ag01 = new ArrayGraph(new int[][] { new int[] {1, 0, 0}, new int[] {0, 0, 0} });
ArrayGraph ag02 = new ArrayGraph(new int[][] { new int[] {0, 0, 0}, new int[] {1, 0, 0} });
ArrayGraph ag03 = new ArrayGraph(new int[][] { new int[] {0, 0, 0}, new int[] {0, 0, 1} });
ArrayGraph ag04 = new ArrayGraph(new int[][] { new int[] {0, 0, 1}, new int[] {0, 0, 0} });
System.out.println(findLine(ag1));
System.out.println(findLine(ag2));
System.out.println(findLine(ag3));
System.out.println(findLine(ag4));
System.out.println(findLine(ag5));
System.out.println(findLine(ag6));
System.out.println();
System.out.println(findLine(ag01));
System.out.println(findLine(ag02));
System.out.println(findLine(ag03));
System.out.println(findLine(ag04));
}
private static Result findLine(Graph g) {
Result result = new Result();
result.line = new Pair<Pair<Long>>();
final long width = g.getWidth();
final long length = g.getLength();
// horizontal scans --
straightScan(width, length, g, false, result);
if (result.pointCount >= width) return result;
// otherwise
straightScan(length, width, g, true, result);
if (result.pointCount == width) return result;
diagonalScan(width, length, g, true, result);
if (result.pointCount == width) return result;
// otherwise
diagonalScan(width, length, g, false, result);
return result;
}
private static void straightScan(long width, long length, Graph g, boolean transpose, Result result) {
for (long i = 0; i < width; i++) {
if (result.pointCount >= length) break;
// otherwise
long pointCount = 0L;
for (long j = 0; j < length; j++) if (transpose?g.isPointPresent(j, i):g.isPointPresent(i, j)) pointCount++;
if (pointCount > result.pointCount) {
result.line.x = transpose?new Pair<Long>(0L, i):new Pair<Long>(i, 0L);
result.line.y = transpose?new Pair<Long>(length-1, i):new Pair<Long>(i, length-1);
result.pointCount = pointCount;
}
}
}
private static void diagonalScan(long width, long length, Graph g, boolean pointDown, Result result) {
for (long i = 0; i <= length-width; i++) {
long pointCount = 0L;
if (result.pointCount >= width) break;
// otherwise
if (pointDown) {
for (long j = 0; j < width; j++) if (g.isPointPresent(j, i+j)) pointCount++;
}
else {
for (long j = width-1; j >= 0; j--) if (g.isPointPresent(j, i+(width-1-j))) pointCount++;
}
if (pointCount > result.pointCount) {
result.line.x = pointDown?new Pair<Long>(0L, i):new Pair<Long>(width-1, i);
result.line.y = pointDown?new Pair<Long>(width-1, i+width-1):new Pair<Long>(0L, i+width-1);
result.pointCount = pointCount;
}
}
if (pointDown) {
for (long k = 1; k < width; k++) {
long pointCount = 0L;
if (result.pointCount >= width-k) break;
// otherwise
for (long i = 0, j = k; i < width - k; i++, j++) {
if (g.isPointPresent(j, i)) pointCount++;
}
if (pointCount > result.pointCount) {
result.line.x = new Pair<Long>(k, 0L);
result.line.y = new Pair<Long>(width-1, width-k-1);
result.pointCount = pointCount;
}
}
}
else {
for (long k = width-2; k >= 0; k--) {
long pointCount = 0L;
if (result.pointCount >= k+1) break;
// otherwise
for (long i = 0, j = k; i <= k; i++, j--) {
if (g.isPointPresent(j, i)) pointCount++;
}
if (pointCount > result.pointCount) {
result.line.x = new Pair<Long>(k, 0L);
result.line.y = new Pair<Long>(0L, k);
result.pointCount = pointCount;
}
}
}
for (long k = length-width+1; k < length; k++) {
long pointCount = 0L;
if (result.pointCount >= length-k) break;
// otherwise
if (pointDown) {
for (long i = k, j = 0; i < length; i++, j++) {
if (g.isPointPresent(j, i)) pointCount++;
}
}
else {
for (long i = k, j = width-1; i < length; i++, j--) {
if (g.isPointPresent(j, i)) pointCount++;
}
}
if (pointCount > result.pointCount) {
result.line.x = pointDown?new Pair<Long>(0L, k):new Pair<Long>(width-1, k);
result.line.y = pointDown?new Pair<Long>(length-1-k, length-1):new Pair<Long>(width-1-(length-1-k), length-1);
result.pointCount = pointCount;
}
}
}
}
class p
{
public int x;
public int y;
}
class Program
{
static List<p> points =
new List<p> { new p { x = 5, y = 5 }, new p { x = 2, y = 2 }, new p { x = 3, y = 3 }, new p { x = 1, y = 1 }, new p { x = 3, y = 4 } };
static int FindNumberOfPoints(int i, int j)
{
int N = 0;
for (int k = 0; k < points.Count; ++k)
{
if (k == i) continue;
if (k == j) continue;
double deltaX1 = points[i].x - points[k].x;
double deltaX2 = points[j].x - points[k].x;
double deltaY1 = points[i].y - points[k].y;
double deltaY2 = points[j].y - points[k].y;
if (Math.Abs(deltaX1 / deltaY1 - deltaX2 / deltaY2) < 0.0001) ++N;
}
return N;
}
static void Main()
{
//all combinations
int candidate1 = 0;
int candidate2 = 1;
int N = 0;
for (int i=0; i<points.Count; ++i)
{
for (int j=i+1; j<points.Count; ++j)
{
int n = FindNumberOfPoints(i, j);
if (n > N)
{
N = n;
candidate1 = i;
candidate2 = j;
}
}
}
Console.WriteLine("Points {0} and {1} make line with {2} other points on it.", candidate1, candidate2, N);
}
}
Just curious, does having intercept will help anything. Suppose lets take the maximum line passes through the ith point (where is 'i' is the left most point in the array through which line passes)
1. If you calculate the slope from this point, why do you need to calculate intercept ? (There cannot be two parallel lines passing through the same point).
2. Do you need to compare it with the slopes of the other left starting points ?(can't we clear the maps)
3. What happens if a same point is repeated in the array ?
My points except the last one may not affect the correctness and complexity of the problem.
Using DP
import math
def find_max_fit(points):
#Using DP
database = [['x']*5 for count in range(len(points))]
#print database
count = 0
for i in range(len(points)):
slope_count = {}
for j in range(len(points)):
if i!=j and database[i][j]=='x' and database[j][i]=='x':
#print(str(i)+','+str(j))
database[i][j] = slope(points[i],points[j])
database[j][i] = database[i][j]
#print(str(database[j][i]))
if database[i][j] in slope_count.keys():
slope_count[database[i][j]] = slope_count[database[i][j]] + 1
else:
slope_count[database[i][j]] = 2
if i!=j:
local_count = max(slope_count.values())
if local_count>count:
count = local_count
#print database
return count
def slope(x,y):
if float(y[0]-x[0]) == 0:
return 90.0
else:
return math.degrees(math.atan2((float(y[1]-x[1])),(float(y[0]-x[0]))))
points = [[5,5], [2,2], [3,3], [3,4], [1,1]]
print(find_max_fit(points))
Algorithm that works in O(n^2) time and takes O(n^2) space. Please let me know if something is wrong.
1. Make a hashmap that maps string to a set of points.
2. Loop n^2 pairs of points.
a. Get the line equation y = mx + c, which is constructed with 2 points.
b. Add "m, c" as key and the points as values into the hashmap.
2. Count the max number of points found across different "m, c" s.
A solution in Javascript
'use strict';
/*
This is a O(n^2) time solution and O(n) in memory.
The algorithm is:
1. consider each point as the origin.
2. calculate the slope (y/x) of every point relative to this temporal origin
3. count the amount of times the most common slope repeats
4. return the highest count
*/
class Point{
constructor(x,y){
this.x = x;
this.y = y;
}
}
function slope(origin, point){
return (point.y - origin.y)/(point.x - origin.x); //Can be a float, +-Infinity, or NaN(when origin = point)
}
function maxNumberOfPointsInARect(points){
var result = 0;
points.map(origin=>{
var maxCount = 0; // max count for that particular origin
var counts = {}; // hash to count slopes repetitions more efficiently
var slopes = points.map(p=>slope(origin, p)); //slopes of all points relative to alternative origin point.
slopes.map(slope=>{ // counting number of repetitions for each slope
if (counts[slope])
counts[slope]++;
else
counts[slope] = 1;
maxCount = Math.max(maxCount, counts[slope]);
});
maxCount += counts[NaN]; // counting for the repetitions of the origin (at least one will be NaN because we are comparing origin against itself)
result = Math.max(result, maxCount);
});
return result;
}
//testing
var testPoints = [[1,2], [1,2], [1,2], [2,3], [2,3], [3,4], [3,4], [4,5], [4,5], [0,1], [0,1], [-1,0], [-1,0], [5,1]];
var r = maxNumberOfPointsInARect(testPoints.map(p=>new Point(...p))); // spread operator
console.log(r);
Find the algorithm below
1. Take a point as origin
2. Find the linear equation(ax+by-c=0) with reference to all the points.
3. Add the equation as string and set of two points to a Map
4. Every time you add a equation check it if exists in the map already, so that add the new points to the existing set.
5. Find out the set which is having more points and return.
Leave the comments if something wrong.
- srterpe December 05, 2016var input = [[5,5], [2,2], [3,3], [3,4], [1,1]] function addUnique () { var args = [].slice.call(arguments) var A = args.shift() for (var i = 0; i < args.length; ++i) { var found = false for (var j = 0; j < A.length; ++j) { if (A[j] === args[i]) { found = true break } } if (!found) { A.push(args[i]) } } } function slope (point1, point2) { return (point2[1] - point1[1])/(point2[0] - point1[0]) } function intercept (point, m) { var y = point[1] var x = point[0] // y = mx + b // y - mx = b // b = y -mx return y - m * x } function find (points) { var map = {} for (var i = 0; i < points.length; ++i) { var point = points[i] for (var j = i + 1; j < points.length; ++j) { var m = slope (point, points[j]) var b = intercept(point, m) var equation = 'y=' + m + 'x+' + b map[equation] = map[equation] || [] addUnique(map[equation], point, points[j]) } } var longest = '' for (var key in map) { if (({}).hasOwnProperty.call(map, key)) { longest = longest || key if (map[key].length > map[longest].length) { longest = key } } } return [longest, map[longest].length, map[longest]] } console.log(find(input))