## Zillow Interview Question for Software Engineers

Country: United States
Interview Type: In-Person

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

We can keep a max heap of size k where we check each incoming element vs the top and if it's smaller we replace it. After we've gone through the list of N points we pop our heap into a list and reverse that list. Running time O(N*log(K)) extra space O(K).

``````List<Point> findClosestToOrigin(List<Point> points, int numToFind) {
PriorityQueue<Point> closestPoints = new PriorityQueue<>(Collections.reverseOrder());
for (Point point : points) {
if (closestPoints.size() < numToFind) {
} else if (point.compareTo(closestPoints.peek()) < 0) {
closestPoints.poll();
}
}
List<Point> closeList = new ArrayList<>();
while (!closestPoints.isEmpty()) {
}
Collections.reverse(closeList);
return closeList;
}

class Point implements Comparable {
double x, y;

double distanceFromOrigin() {
return Math.sqrt(Math.pow(x, 2) + Math.pow(y, 2));
}

@Override
public int compareTo(Object other) {
if (!(other instanceof Point)) {
throw new IllegalArgumentException("Points can only be compared with other points.");
}
double diff = (distanceFromOrigin() - ((Point) other).distanceFromOrigin());
if (diff == 0) {
return 0;
} else {
return diff > 0 ? 1 : -1;
}
}
}``````

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

Running time should be O(nlogk) as O(nlogk) + O(n) ~ O(nlogk) of the above code

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

Yep, I had edited it but CC takes a couple of hours to post edits haha. Thanks though!

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

1) it is finding the k-thary element and return it and all that are smaller
2) A modified quick-sort partition method will do it in O(n)
3) I did it in place of the original array/vector for simplicity

``````#include <iostream>
#include <vector>

using namespace std;

struct Point
{
int x; int y;
Point(int ax, int ay) : x(ax), y(ay) {}
int get_DistSq() { return x*x + y*y; }
};
ostream& operator << (ostream& os, Point& p) { return os << "{" << p.x << "," << p.y << "("  << p.get_DistSq() << ")" << "}"; }

// quick-sorts partition function, returns k
// partitions array [s..e] into [s..k][k+1..e] where every element in [s..k] < than every element in [k+1..e]
int Partition(int s, int e, vector<Point>& pts)
{
int p = (s + e) / 2; // pick pivot element, improvement: randomize or at least check overflow
swap(pts[p], pts[e]); // swap pivot with end element

int i = s-1; // all in [s..i] <= p < all in [i+1..j]
int pv = pts[e].get_DistSq();
for (int j = s; j < e; ++j)
{
if (pts[j].get_DistSq() <= pv)
{
i++;
swap(pts[i], pts[j]);
}
}

swap(pts[i+1], pts[e]);
return i+1;
}

// changes the vector to contain the k-smallest elements at position 0..k
// smallest in this contect is the distance of the points to {0,0}
void Find(vector<Point>& pts, int k)
{
int s = 0;
int e = pts.size()-1;
int m = 0;
do
{
m = Partition(s, e, pts);
if (m < k) s = m + 1; // on the left of m are not enough elements
if (m > k) e = m - 1; // on the left of m are too many elements
} while (m != k);
}

int main()
{
int k = 2;
auto pts = vector<Point>{ Point(1,2), Point(2,2), Point(5,3), Point(4,2), Point(3,2), Point(2,0), Point(1,1), Point(2,1), Point(9,9) };

cout << "all points:" << endl;
for (int i = 0; i < pts.size(); i++) cout << pts[i] << " ";

Find(pts, k);

cout << endl << endl << k << " smallest point(s):" << endl;
for (int i = 0; i < k; i++) cout << pts[i] << " ";

getchar();
}``````

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

``````#run time O(nlogn), space O(1)
def closest_point(origin, points, k):

def compare(p1, p2):
return ((p1 - origin)**2 + (p1 - origin)**2) - ((p2 - origin)**2 + (p2 - origin)**2)

def compare1(p1, p2):
return (p1**2 + p1**2) - (p2**2 + p2**2)

points = sorted(points, cmp=compare1)
return points[:k]

points = [(0, 0), (1, 1), (1, 0), (2, 1), (2, 2), (1, 2), (0, 1)]
print closest_point((0, 0), points, 3)``````

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

Two methods are shown here to find:
1. To do the quick sort comparator, based on the distance to origin.
2. To use the heap of size K.

``````#run time O(nlogn), space O(1)
import heapq

def closest_point(origin, points, k):

def compare(p1, p2):
return ((p1 - origin)**2 + (p1 - origin)**2) - ((p2 - origin)**2 + (p2 - origin)**2)

def compare1(p1, p2):
return (p1**2 + p1**2) - (p2**2 + p2**2)

points = sorted(points, cmp=compare1)
return points[:k]

points = [(0, 0), (1, 1), (1, 0), (2, 1), (2, 2), (1, 2), (0, 1)]
print closest_point((0, 0), points, 3)

#time: nlogk; space O(k)
def closest_point_heap(origin, points, k):
hp = []

for i in xrange(len(points)):
x, y = points[i]
dis = -(x**2 + y**2)

if len(hp) < k:
heapq.heappush(hp, (dis, x, y))
else:
mxdis, xx, yy = heapq.heappop(hp)
if mxdis < dis:
heapq.heappush(hp, (dis, x, y))
else:
heapq.heappush(hp, (mxdis, xx, yy))

for p in hp:
print p, p

closest_point_heap((0, 0), points, 4)``````

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.