## Facebook Interview Question for Web Developers

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
19
of 21 vote

You can do it in O(n), but you have to avoid heaps.
First build an array with the distances to the origin and the corresponding point. O(n)
Then find the Kth largest distance using the Selection algorithm. O(n)
The K-1 smallest distances are to the left of the Kth distance, in no particular order.

So the total is O(n).

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

Best solution so far. Order statistics are the way to go to make this problem run in O(n).

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

Wont finding the kth largest using selection sort be O(k*n)?

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

Does the selection algorithm guarantee O(n) finding the kth largest?

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

Well, depends on k. Using heaps is O(n log k), which is O(n) if k is constant.

But, even if k is not a constant, it might still perform better than a deterministic selection algorithm, practically speaking, as the deterministic selection algorithm has big hidden constants.

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

Yes, the selection algorithm guarantees O(n) regardless of K and it is not considering K as a constant.

you can look it up on the Introduction to Algorithms book or wikipedia en.wikipedia.org/wiki/Selection_algorithm

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

nice

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

Just like quick sort worst case for quick select is O(n^2)

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

for quick select yes. but there is a O(n) worst case selection algorithm. you may check the link i gave above or this one en.wikipedia.org/wiki/Median_of_medians

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

Though the 'selection algorithm' wiki page states "There are O(n) (worst-case linear time) selection algorithms", it doesn't give any examples of such.
One example it provides is the 'quick select', which is O(n^2) (worse case) - bad.

I couldn't find those linear time selection algorithms :(

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

@kilaka, you didn't read the posts. The selection algorithm page has a link to a deterministic O(n) algorithm called "median of medians". In my latest reply, I posted the link - en.wikipedia.org/wiki/Median_of_medians

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

Step 1) Replace every point in the array with a tuple of

``(Point, distance_to_origin)``

Step 2) Quickselect the kth largest element by using the

``distance_to_origin``

parameter of each tuple element in the array. Return this index (call it K). This process partitions the array like the inner loop of Quicksort - all larger elements to the right, smaller elements to the left.
Step 3) Return elements from index 0 to index K.

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

Not elegant, but it works. (Java) Could probably make the code more elegant with more time.

``````//test the code
public static void main(String[] args) {
Vect2[] points = {new Vect2(1, 1),new Vect2(2, 2),new Vect2(3, 2),new Vect2(0, 1),new Vect2(1, 0)};
Vect2[] points2 = getKclosest(points, 3);
for (int i = 0; i < points2.length; i++) {
System.out.println("point: "+points2[i]);
}
}

public static Vect2[] getKclosest(Vect2[] points, int k) {
//ArrayList<VectData> list = new ArrayList<VectData>(points.length);
VectData[] list = new VectData[points.length];

for (int i = 0, len = points.length; i < len; i++) {
list[i]= new VectData(points[i]);}

Arrays.sort(list);

Vect2[] points2 = new Vect2[k];
for (int i = 0; i < k; i++) {
points2[i] = list[i].getVect();
}
return points2;
}

public static class VectData implements Comparable<VectData>{
private Vect2 vect;
private float dist2;//distance squared

public float getDist2() {
return dist2;}

public Vect2 getVect(){
return vect;}

public VectData (Vect2 vect) {
this.vect = vect;
dist2 = dist2FromZero(vect);
}

public float dist2FromZero(Vect2 vect) {//we only need the squared-distance.  Less calc.
return vect.x*vect.x+vect.y*vect.y;
}

@Override
public int compareTo(VectData o) {
return (o.getDist2() < this.getDist2())?1:-1;
}
}

public static  class Vect2 {
public float x;
public float y;
public Vect2(float x,float y){
this.x=x; this.y=y;}

@Override public String toString() {
return "["+x+","+y+"]";
}

}``````

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

Any explanation for the -1? I'm always looking to improve my code.

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

Any explanation for the code? I am always looking to improve my -1.

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

Ignore this solution, I just posted a much better solution below which is many times faster and uses a fraction of the memory.

(10-mill points, 15 k-points, 125ms on an old laptop)

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

@JonG, too late I already upvoted this one hehe :P

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

First idea could be: calculate all the distances in an array, sort the array,
then get the k smallest values from there. This would work fine, but as the
fastest sorting algorigthms are O(nlog(n)), there is a faster, O(n) solution.

While iterating over the array you fill a max-heap of length k with new values.

The exact implementation of the heap was not asked.

In PHP:

``````<?php
class PointMaxHeap {
// Creates the class and limits it to a certain size
function __construct(\$size);
// Adds a new value in the heap and removes the max value if new size
// is bigger than the size it was initialized with
// Returns the max current value
function getMax();
// Returns the current size of the heap
function getSize();
// Returns all current points
function getPoints();
}

class Point {
public \$x;
public \$y;

// Returns the Euclidian distance to origin
function getDistanceFromOrigin() {
return sqrt(\$this->x * \$this->x + \$this->y * \$this->y);
}
}

function getKClosest(\$points, \$k) {
\$heap = new PointMaxHeap(\$k);

foreach (\$poitns as \$point) {
\$d = \$point->getDistanceFromOrigin();

// If the heap isn't full yet, we just directly add the value
// If the heap is full, but this point is closer to origin than
// one of the points currently in the heap, we add the value
if (\$heap->getSize() < \$k || \$heap->getMax() > \$d) {
}
}

return \$heap->getPoints();
}``````

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

this is not O(n). each heap operation costs O(log k). Hence the runtime is O(n log k)

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

If I'm not wrong, this should be O(n + k log k). Anyways, nice solution.

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

sorry, yes the running time should be O(n log k)

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

Exactly, I think this is a nice solution and I thought the same initially but it is not O(n) as Miguel pointed out. Although instead of a binary heap, one could use a Fibonacci heap for amortized constant time. Don't know if that would be an acceptable solution though...

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

we still need to delete the maximum when we find a lower value and deletions run in O(log n) even with a Fibonacci heap

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

@Alistair: You cannot have O(1) amortized, as that would allow you to sort in O(n) time!

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

``````int i =0;
HashMap map;
while(i<k){
maxHeap.insert( xi^2 +yi^2 );
map.put(xi^2 +yi^2, i);
i++;
}
while(i<n){
a =  xi^2 +yi^2 ;
if( a< maxElemetOfHeap){
maxHeaaap.remove(maxElemetOfHeap);
map.remove(maxElemetOfHeap);
maxHeap.insert(a)
map.put(a,i);
}
}

iterate map``````

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

O(n) time and space

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

read the other posts. heap operations will make the solution O(n log k)

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

Actually his code should be worst case N*lgN.

+1 for using distance^2 instead of distance (no sqrt used, cool)

Also, if you have all N elements up front, you shouldn't do N heap inserts, but rather you should use a slick O(N) build heap algo. (heapify from lowest internal nodes up to roof).

The building of heap alone you are using is O(N*lgN) worst case. Then add the removes, which are worst case O(k*lgN) and you get a total runtime of O(NlgN). So you are better off actually just doing heapsort on the array (same runtime, but the internal constants will be smaller).

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

Yeah, nvm.

I think it's O(infinite)
How does the second loop break?

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

@URIK LAGNES
sorry forgot to add i++ at last of while loop,

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

My thoughts:

1) Never use distance, but rather use the square on distance.
We don't want to get caught up in the ugliness of sqrt.

2) We can do this in place (and in most apps. this should be allowed because the set of points is just a "bag" of points):

3) Modify QuickSelect or MedianOfMedians to use a distance^2 comparison function "on the fly" on the original array itself.
This gets the k closest points into the first k elements of _original_ array of points.

Should be O(n)

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

Am I crazy but can't we do a BFS search on the 2D plane with a K count. Once K has hit its value we just return a list of found points? Here is the code:

``````static boolean inbounds(int[][] plane, int x, int y) {
if (x >= 0 && y >= 0 &&
x < plane[0].length && y < plane.length) {
return true;
}
return false;
}

static int[][] closestk(int[][] plane, int k) {
Queue<int[]> q = new ArrayDeque<int[]>();
int[][] found = new int[k][2];
int n=0;
int x=0;
int y=0;
while (!q.isEmpty()) {
int[] tup = q.remove();
int tmpx = tup[0];
int tmpy = tup[1];
int e = plane[tmpy][tmpx];
if (e == 1) {
found[n++] = tup;
} if (n == k) {
return found;
}
// NOTE: The order of the following 3
// if statements are crutial. The diagnol
// square is the "farthest" from our current point
if (inbounds(plane, x+1, y)) {
}
if (inbounds(plane, x, y+1)) {
}
if (inbounds(plane, x+1, y+1)) {
}
x++;
y++;
}
return found;
}``````

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

we're given a list of points (x, y). your code does not make any sense..

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

``````from random import random as rand

def knth(sample, n):
pivot = sample[0]
below = [s for s in sample if s < pivot]
above = [s for s in sample if s > pivot]
i, j = len(below), len(sample)-len(above)
if n < i:      return knth(below, n)
elif n >= j:   return knth(above, n-j)
else:          return pivot

def kmindist(sample, n):
distsquared = [x**2+y**2 for x,y in sample]
last_element = knth(distsquared, n)
return [d for d in distsquared if d < last_element]

def main():
# Tester
sample = [(rand(),rand()) for i in range(20)]
print sample
print kmindist(sample, 5)

if __name__ == "__main__":
main()``````

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

But Like to know, when there are utility methods to sort still Interview expect to write a fresh sort?
Running code sample below with Two possible ways to solve this:

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.Random;
import java.util.TreeMap;

public class PuzzleRunner {

public static void main(String[] args) {
try {
Plane2D plane2d = new PuzzleRunner().new Plane2D(10,5);
plane2d.fillRandomPoints(10);
plane2d.showGenetatedPoints();
System.out.println("Result by n log(n) performance" + plane2d.getClosedPoint());
System.out.println("guaranteed log(n) time cost" +plane2d.getClosedPoint2());

} catch (Exception e) {
System.out.println(e.getMessage());
}

}

protected class Plane2D {

private int length;
private int breath;
private ArrayList<Point> points;

Plane2D(int length, int breath) throws Exception{
if(length <= 0 || breath <= 0){
throw new Exception("Size is less then zeros not allowed in this version");
}
this.length = length;
this.breath = breath;

}

public void fillRandomPoints(int numberOfPoints){
points = new ArrayList<Point>(numberOfPoints);
Random randomX = new Random();
Random randomY = new Random();
for (int i = 0; i < numberOfPoints; i++) {
}

}

public Point getClosedPoint(){
/**
* The sorting algorithm is a modified merge sort
* This algorithm offers guaranteed n log(n) performance
*/
Collections.sort(points);
return points.get(0);
}

public Point getClosedPoint2(){

//This implementation provides guaranteed log(n) time cost for the containsKey
TreeMap<Double, Point> treeMap = new TreeMap<Double, Point>();
for (Point point : points) {
treeMap.put(point.getDistanceOfPointsFromOrigin(), point);
}
return treeMap.get(treeMap.firstKey());
}

public void showGenetatedPoints(){

for (Iterator<Point> iterator = points.iterator(); iterator.hasNext();) {
Point point = (Point) iterator.next();
System.out.println(point);

}
}

}

protected class Point implements Comparable<Point> {

private double x;
private double y;
private double distanceOfPointsFromOrigin;

Point(double x, double y){
this.x = x;
this.y = y;
this.distanceOfPointsFromOrigin = Math.sqrt(getX()*getX() + getY()*getY());
}

public double getX() {
return x;
}

public double getY() {
return y;
}

@Override
public int compareTo(Point o) {
if(this.distanceOfPointsFromOrigin < o.getDistanceOfPointsFromOrigin()){
return -1;
}else if (this.distanceOfPointsFromOrigin > o.getDistanceOfPointsFromOrigin()){
return 1;
}else{
return 0;
}
}

@Override
public String toString() {
return "Point [x=" + x + ", y=" + y + "]";
}

public double getDistanceOfPointsFromOrigin() {
return distanceOfPointsFromOrigin;
}

}

}

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

//Java
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

class Point{
private float x;
private float y;
private Float distFrmOrig;

Point(float xaxis, float yaxis){
x=xaxis;
y=yaxis;
distFrmOrig=(x*x)+(y*y);
}
public float getX() {
return x;
}
public void setX(float x) {
this.x = x;
}
public float getY() {
return y;
}
public void setY(Float y) {
this.y = y;
}
public Float getDistFrmOrig() {
return distFrmOrig;
}
public void setDistFrmOrig(Float distFrmOrig) {
this.distFrmOrig = distFrmOrig;
}

}

public class KPointAlgo {

public static void main(String[] args){

List<Point>pointList=new ArrayList<Point>();

//Let K =5
int k=5;
List<Point> KpointList= getKpointClosetoOrigin(pointList,k);
if(KpointList!=null){
for(Point point:KpointList){
System.out.println("X axis: " + point.getX()+" Y axis: "+ point.getY()+" and distance from origin is "+ point.getDistFrmOrig());
}
}

}

private static List<Point> getKpointClosetoOrigin(List<Point> pointList,
int k) {
if(pointList!=null && pointList.size()>0){
Collections.sort(pointList,new Comparator<Point>(){
@Override
public int compare(Point o1, Point o2) {
return o1.getDistFrmOrig().compareTo(o2.getDistFrmOrig());
}
});
return pointList.subList(0,k);
}

return null;
}

}

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

Updated solution.

This one is designed for practical use. In a typical scenario, I would expect to be given a very large number of points (i.e. 10,000,000) to search through & only a small number of k-points (i.e. 15 or less) that need to be returned.

Storing 10-million pointers and their distance values, or 'cheating' by having a point class that stores it's distance from (0,0) (what?!) would be extremely inefficient. Instead, we just store the k-closest points so far, and their distances.

As far as calculations, we save by using distance-squared and storing those distances.

For fun, I ran a test on my old laptop with 10-million random points and 15-closest, and the results returned in 125ms.

``````// test the code
public static void main(String[] args) {
Vect2[] points = randPts(25, 10f);
Vect2[] points2 = vectDistSorter(5, new Vect2(0, 0), points);
System.out.println("Starting Points");  //print results
for (Vect2 point : points) {
System.out.println("point: " + point);}
System.out.println("===============");
System.out.println("Results");
for (Vect2 point : points2) {
System.out.println("point: " + point);}
}

//generate test points
public static Vect2[] randPts(int total, float scalar) {
Vect2[] points = new Vect2[total];
for (int i = 0; i < total; i++) {
points[i] = new Vect2((float) Math.random() * scalar,
(float) Math.random() * scalar);
}
return points;
}

/**
* Returns the closest K-points to the targetPt, from points array. Uses
* O(k) memory and worst case is O(points*k). This solution is ideal for a
* large number of points (i.e. 10000000) and a small number of k-closest
* (i.e. 10).
*/
public static Vect2[] vectDistSorter(int kClosest, Vect2 targetPt,Vect2[] points) {
VectSortData vData = new VectSortData();
vData.vect = new Vect2[kClosest];
vData.dist2 = new float[kClosest];
vData.totalPts = kClosest;
vData.targetPt = targetPt;

if (kClosest >= points.length) {
return points;
}// done early, that was easy!

for (int i = 0; i < kClosest; i++) {// add first k points
vData.vect[i] = points[i];
vData.dist2[i] = vData.dist2FromPt(points[i]);
}

vData.selectNextMax();

float curDist;
for (int i = kClosest, len = points.length; i < len; i++) {// if closer,
// replace
// farthest
// point
curDist = vData.dist2FromPt(points[i]);
if (curDist < vData.curMaxDist) {
vData.vect[vData.curMaxIndex] = points[i];// replace max pt
vData.dist2[vData.curMaxIndex] = curDist;// replace distance
vData.selectNextMax();// selext new farthest point
}
}

return vData.vect;
}

// helper class that stores temporary closest-point data & does a couple opperations
static class VectSortData {
Vect2 vect[];// stores points
float dist2[];// stores distance-squared
Vect2 targetPt;// oritionating point
int totalPts;// number of closest points
float curMaxDist = 0;// distance of farthest point in our current list
int curMaxIndex = 0;// cursor of current max. Saves searches

float xDist;// less garbage collection
float yDist;// less garbage collection

// we only need the squared-distance.
float dist2FromPt(Vect2 vect) {
xDist = (vect.x - targetPt.x);
yDist = (vect.y - targetPt.y);
return xDist * xDist + yDist * yDist;
}

//searches for the next max-distance point & stores the distance and index
void selectNextMax() {
curMaxDist = 0;
for (int i = 0; i < totalPts; i++) {
if (dist2[i] > curMaxDist) {
curMaxDist = dist2[i];
curMaxIndex = i;
}
}
}
}

// We need a points class to contain the points.
public static class Vect2 {
public float x;
public float y;

public Vect2(float x, float y) {
this.x = x;
this.y = y;
}

@Override public String toString() {return "[" + x + "," + y + "]";}
}``````

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

like was mentioned before, you can use a heap to make it O(n log k) with only extra O(k) memory as well.

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

Thanks, I'll look into how heaps are implemented in java. It looks like the place to start is "java.util.PriorityQueue"

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

Use the array based implementation of the heap. That will be crazy fast.

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

Could you give an example? I could probably 'invent' something, but I'm not familiar with the default/standardway (and i'm always interested in learning)

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

@JonG
collabedit.com/4k9d4

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

collabedit.com/fqaax <= I meant this.

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

@JonG
collabedit.com/4k9d4

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

collabedit.com/fqaax <= I meant this.

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

// k-closest-points-to-origin.cpp : Defines the entry point for the console application.
//

#include<iostream>
#include<algorithm>
using namespace std;
struct point{
int x,y;
};
point p[10];

int Dist(int i)
{
return p[i].x*p[i].x + p[i].y*p[i].y;
}

int partition(int low, int high,int mid)
{
int lookat=low;
int midr = Dist(mid);
while(lookat<=high)
{
int loDtr = Dist(lookat);
if(loDtr < midr)
{
swap(p[lookat],p[low]);
lookat++;low++;
}
if(loDtr > midr)
{
swap(p[lookat],p[high]);
high--;
}
else
lookat++;
}
return low;
}

void quickSelect(int k, int low, int high)
{
int mid = (low+high)/2;
int index = partition(low,high,mid);
int len = index-low+1;
if(k == len)
return;
else if (k < len)
quickSelect(k,low,index-1);
else
quickSelect(k-len,index+1,high);

}
int main()
{
for(int i=0;i<10;i++)
{
p[i].x = rand()%10;
p[i].y = rand()%10;
}

for(int i=0;i<10;i++)
{
cout<<p[i].x<<" "<<p[i].y<<endl;
}
cout<<endl;
quickSelect(5,0,9);

for(int i=0;i<10;i++)
{
cout<<p[i].x<<" "<<p[i].y<<endl;
}
getchar();
}

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

3 step operation: (1) calculate distances for all Points; (2) sort; (3) select K points closest to origin

``````public void FindClosestKPoints() {
int nPoints = Math.max(1,(int) (Math.random()*100) );
int k = Math.max(1, (int) (Math.random()*nPoints) );
int[] distances = new int[nPoints], sortedList = new int[nPoints];
Point[] pointsList2 = new Point[nPoints];

for (int i=0; i<nPoints; i++) {  // Populate arrays
pointsList2[i] = new Point((int) (Math.random()*100), (int) (Math.random()*100));
sortedList[i] = distances[i] = distance(pointsList2[i]);
}  //ENDFOR

Arrays.sort(sortedList);  //Sort distance values
System.out.println(String.format("----closest %s of %s Points. (dividing line=%s)-----", k, nPoints, sortedList[k-1]));
System.out.println(String.format("Point  |  Coordinates  |  Distance", k, nPoints));
for (int i=0; i<nPoints; i++) {  //Identify K points closest to origin
if (distances[i] <= sortedList[k-1]) {
System.out.println(String.format("  %s    |  (%s, %s)      |   %s", i, pointsList2[i].x, pointsList2[i].y, distances[i]));
}
}
}

private int distance(Point thisPoint) {
return thisPoint.x*thisPoint.x + thisPoint.y*thisPoint.y;
}``````

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

``````ArrayList<Double> kNearestPts(Coordinates[] C, int k){
double[] A = new double[C.length];
for(int i = 0; i<C.length; i++){
A[i] = Math.sqrt(C[i].x*C[i].x + C[i].y*C[i].y);
}
return selectTopK(A, k);
}

ArrayList<Double> selectTopK(ArrayList<Double> A, int k){
if(A.size() < 26){
return selectBruteForce(A, k);
}
int m = (A.size()-1)/5 + 1;
double[] M = new double[m];
for(int i = 0; i<m; i++){
M[i] = medianBruteForce(A, 5*i, 5*i + 4);
}
ArrayList<Double> mom = selectTopK(M, m/2);
int r = partition(A, mom.get(mom.size()-1));
if(k < r+1){
return selectTopK(new ArrayList<Double>(A.subList(0, r)), k);
}
if(k > r+1) {
return selectTopK(new ArrayList<Double>(A.subList(r+1, A.size()), k-r-1);
}
return new ArrayList<Double>(A.subList(0, r+1));
}

ArrayList<Double> selectBruteForce(double[] A, k){
ArrayList<Double> ret = new ArrayList<Double>();
while(k > 0){
int min = Double.MAX_VALUE;
for(int i = 0; i<A.size(); i++){
if(A.get(i) < min){
min = A.get(i);
}
}
A.remove(min);
}
return ret;
}

double medianBruteForce(ArrayList<Double> A, int start, int end){
ArrayList<Double> temp = new ArrayList<Double>();
for(int i = start; i<= end; i++){
}
for(int i = 1; i<temp.size(); i++){
for(int j = 0; j<temp.size()-i-1; j++){
if(temp.get(i) > temp.get(j)){
double t = temp.get(i);
temp.set(i, temp.get(j));
temp.set(j, t);
}
}
}
return temp.get((0+temp.size())/2);
}
int partition(ArrayList<Double>A, double pivot){
int r = 0;
int c = 0;
while(c < A.size()){
if(A.get(c) < pivot) {
double t = A.get(r);
A.set(r, A.get(c));
A.set(c, t);
r ++;
}
c++;
}
return r;
}``````

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

One idea about the solution: 1. Calculate the distances of all points, they will get stored in an array. 2. The question can be attributed to the question to find the smallest k items in an array. To solve this question, we can use several ways, including sorting and find the kth, quicksort like way to partition the array to parts, that all based on the items are not that big enough, they can be loaded into memory.
The following part is sample code to find the Kth number:

``````public class FindKth {
public static int findKth(int[] a, int l, int r, int k) {
int n = partition(l, r);
int i = n - l + 1;
if(i > k) {
return findKth(a, l, n - 1, k);
} else if(i < k) {
return findKth(a, n + 1, r, k - i);
} else
return n;
}

public static int partition(int[] a, int l, int r) {
int value = a[r];
int j = l - 1;
for(int i = l; i < r; i++) {
if(a[i] < value) {
j++;
swap(a, i, j);
}
}
swap(a, j + 1, r);

return j + 1;
}

public static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}``````

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

Use TreeMap to put the points, compared by their distance from origin. Then iterate over the first k.
Complexity: O(nlogn) - n because running over all the elements and logn because the depth of the tree logn.

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

Here my C++ solution:

``````typedef struct pos {
int x;
int y;

pos(int x_, int y_): x(x_), y(y_) {}
}pos;

typedef struct dist_ind {
float dist;
int index;
dist_ind(float dist_, int index_): dist(dist_), index(index_) {}
}dist_ind;

typedef struct comparison {
bool operator()(const dist_ind &lhs, const dist_ind &rhs) const {
return lhs.dist < rhs.dist;
}
}comparison;

vector<pos> find_k_closest_points(vector<pos> &vec, int k) {
priority_queue<dist_ind, vector<dist_ind>, comparison> q;
vector<pos> out;

for(int i = 0; i < vec.size(); i++) {
float dist = sqrt(pow(vec[i].x, 2) + pow(vec[i].y, 2));

if(q.size() >= k) {
if(dist < q.top().dist) {
q.pop();
q.push(dist_ind(dist, i));
}
}
else {
q.push(dist_ind(dist, i));
}
}

while(!q.empty()) {
out.push_back(vec[q.top().index]);
q.pop();
}

return out;
}

int main() {

vector<pos> vec = {{2,2}, {6,6}, {4,4}, {5,5}, {3,3}, {9,9}, {7,7}, {8,8}, {10,10}};
vec = find_k_closest_points(vec, 2);

for_each(vec.begin(), vec.end(), [](pos &p) { cout << p.x << ", " << p.y << endl;});

return 0;
}``````

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

Did a solution in golang see comment for explanation:

``````package main

import (
"fmt"
"math"
)

func main() {
arr := []Point{Point{X: 3, Y: 40}, Point{X: 19, Y: 4}, Point{X: 7, Y: 4}, Point{X: 1, Y: 4}, Point{X: 17, Y: 4}, Point{X: 11, Y: 4}}
fmt.Println(Closest(arr, 2))
}

type Point struct {
X int
Y int
}

func (point Point) distance() float64 {
a := math.Pow(float64(point.X), 2)
b := math.Pow(float64(point.Y), 2)
return math.Sqrt(a + b)
}

func Closest(points []Point, k int) []Point {
position := selection(points, k)

//return slice of k closest points
return points[0:position]
}

//Quick Selection algorithm
//Basically what amounts to a partial insertion sort
//Customized for Point struct
//Return position kth Point
func selection(arr []Point, k int) int {
to := len(arr) - 1
for from := 0; from < to; {
write := to

write = write - 1
} else {
}
}

}

} else {
}
}
return k
}

func swap(arr []Point, i int, j int) {
temp := arr[i]
arr[i] = arr[j]
arr[j] = temp
}``````

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

Given k = 2 and initial points array:

``````var k = 2,
arr = [{x:1,y:2}, {x:2, y:0}, {x:4, y:0}, {x:1, y:2}],
length = arr.length,
result = [];

for(i = 0; i< length; i+=1){
}

arr.sort(function(a, b) {
});

for(i = 0; i< k; i+=1){
result.push(arr[i]);
}``````

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.