random interviews: k closest neighbors

发表于 | 分类于

Given a set of points in a cartesian plane, and a start point , find the k closest points to the starting point.

Points = [(1,2),(2,3),(4,6),(7,9)]
Start Point = (2,2)

Find 2 closest points to start point
这题要考虑的corner case比较多，也是这题的难点。
corner case有：
empty string
string with space
string with positive or negative sign
string with non-digit numbers
overflow integer
对于overflow的处理有两种情况。一个是当前的total乘以10之后超过Integer.MAX_VALUE，由于不能直接比total * 10 > Integer.MAX_VALUE, 我们可以换一种比法。
用Integer.MAX_VALUE / 10 < total 表示判断标准。
但是这又有一种情况就是Integer.MAX_VALUE / 10 是整数除法，可能会有遗漏的情况是最后一位不同。
那么就需要排除Integer.MAX_VALUE / 10 == total && Integer.MAX_VALUE % 10 < digit 的情况。

解法1：Priority Queue, O(NlogK)

最容易想的就是用一个size为k的heap来存储每一个点。如果还没存满k个就直接存入。
如果存满了每当下一个点到p的距离比top的小的时候在把top弹出。
Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public List<Point> closestNeighbors(Point[] points, Point center) {
	Comparator<Point> comparator = new Comparator<Point>() {
		public int compare(Point left, Point right) {
			return distance(right, center) - distance(left, center);
		}
	};
	PriorityQueue<Point> queue = new PriorityQueue<Point>(comparator);
	for (Point p : points) {
		if (queue.size() < k) {
			queue.offer(p);
		} else {
			if (distance(p, center) < queue.peek()) {
				queue.poll();
				queue.offer(p);
			}
		}
	}
	List<Point> res = new ArrayList<Point>();
	while (!queue.isEmpty()) {
		res.offer(queue.poll());
	}
	return res;
}
private int distance(Point a, Point b) {
	return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

解法2： Quick Select, O(N)

一般面试给出上面的解法就可以了。如果面试官喜欢刁难的话可能是需要这个解法。
思路和find median有点类似，就是先用quick select找出到center距离为第k大的point.然后再扫描一遍数组得到所有小于那个距离的点即可。
code有空的时候再来补上吧。。
Java

lang: java
1