## Google Interview Question for Software Engineer / Developers

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````var input = [[5,5], [2,2], [3,3], [3,4], [1,1]]

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 - point1)/(point2 - point1)
}
function intercept (point, m) {
var y = point
var x = point

// 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] || []
}
}
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))``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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.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.length;
}

@Override
public long getWidth() {
return mustTranspose?a.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;
}
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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-x) == 0:
return 90.0
else:
return math.degrees(math.atan2((float(y-x)),(float(y-x))))

points = [[5,5], [2,2], [3,3], [3,4], [1,1]]
print(find_max_fit(points))``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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.

Comment hidden because of low score. Click to expand.
0

The problem with your approach is that it assumes that whichever point is taken as the origin is always included on the straight line that fits the maximum number of points; which may not be the case.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.