## Facebook Interview Question for Software Engineer / Developers

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

``````#include <stdio.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
#include <limits>
struct Point {
double pt[2];
int id;
double distance;
};
typedef std::vector<Point> PointList;
typedef PointList::iterator PointListItr;
struct compareX {
bool operator ()(const Point& left, const Point& right) const {
return left.pt[0] < right.pt[0];
}
};
struct compareY {
bool operator ()(const Point& left, const Point& right) const {
return left.pt[1] < right.pt[1];
}
};
struct compareD {
bool operator ()(const Point& left, const Point& right) const {
return left.distance < right.distance;
}
};
struct kdNode {
Point point;
kdNode *left;
kdNode *right;

kdNode(PointListItr begin,
PointListItr end,int depth);
};
kdNode::kdNode( PointListItr begin,
PointListItr end,int depth = 0) {
left = right = 0;
if (begin == end) {
return ;
}
if( end - begin == 1) {
point = *begin;
return;
}
if(depth & 1)
std::sort( begin, end, compareY());
else
std::sort( begin, end, compareX());
PointList::size_type median = (end - begin) / 2;
point = *(begin + median );
if ( begin != ( begin + median ))
left  = new kdNode(begin , begin + median , depth + 1);
if ( (begin + median + 1 ) != end )
right = new kdNode(begin + median + 1, end, depth + 1);
}
void readPoints(const char* fileName, PointList& points) {
std::ifstream input(fileName);
if ( input.peek() != EOF ) {
while(!input.eof()) {
int id = 0;
double x_cord, y_cord;
input >> id >> x_cord >> y_cord;
Point t ;
t.pt[0] = x_cord;
t.pt[1] = y_cord;
t.id    = id;
points.push_back(t);
}
input.close();
}
}
double dist(Point &p1, Point &p2) {
double a = p1.pt[0] - p2.pt[0];
double b = p1.pt[1] - p2.pt[1];
return (a * a) + (b * b);
}
Point nearest(kdNode *node, Point &point, Point &min, int depth = 0) {
if ( node ) {
int axis = depth % 2;
double d = point.pt[axis] - min.pt[axis];
kdNode *near = d <= 0 ? node->left  : node->right;
kdNode *far  = d <= 0 ? node->right : node->left;
min = nearest(near, point, min, depth + 1);
if ((d * d) < dist(point, min)){
min = nearest(far, point, min, depth + 1);
}
if (dist(point,node->point) < dist(point, min)) {
min = node->point;
}
}
return min;
}
void nearest_k(kdNode *node, Point &point,
PointList &min,
double k_dist = std::numeric_limits<double>::max(),
int depth = 0) {
if ( node ) {
int axis = depth % 2;
double d = point.pt[axis] - node->point.pt[axis];
kdNode *near = d <= 0 ? node->left  : node->right;
kdNode *far  = d <= 0 ? node->right : node->left;
nearest_k(near, point, min, k_dist, depth+1);
if ( (d * d ) < k_dist ) {
nearest_k(far, point, min, k_dist, depth+1);
}
d = dist(point, node->point);
if ( d < k_dist) {
node->point.distance = d;
min.push_back(node->point);
}
std::sort(min.begin(), min.end(), compareD());
if ( min.size() > 3 ) {
for ( int i = 0; i < min.size() - 3; i++) {
min.erase(min.begin() + i );
}
}
k_dist = min[0].distance;
}
return;
}
void printLevelWise(kdNode *root) {
std::queue<kdNode*> Q;
Q.push(root);
while ( !Q.empty()) {
root = Q.front();
if( root->left) {
Q.push(root->left);
}
if ( root->right) {
Q.push(root->right);
}
Q.pop();
}
}
void printPoint(Point p) {
std::cout << "( " << p.pt[0] << "," << p.pt[1] << " )" << std::endl;
}
int main(int argc, char** argv ) {
if ( argc <= 1 ) {
return 0;
}
PointList locations;
if ( locations.size() == 0 )
return 0;

kdNode *pKdTree = new kdNode(locations.begin(), locations.end(),0);
printLevelWise(pKdTree);
Point t;
t.pt[0] = 6;
t.pt[1] = 5;
Point root =  pKdTree->point;
Point p = nearest(pKdTree, t, root, 0);

PointList result;
for ( PointListItr itr = locations.begin(); itr != locations.end(); ++itr) {
nearest_k( pKdTree, *itr, result);
std::cout << (*itr).id << " " << result[0].id << "," << result[1].id << "," << result[2].id << std::endl;
}
delete pKdTree;
return 0;
}``````

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

Hey buddy your program is giving wrong output for the sample program
2 4,5,0
1 0,5,0
3 0,5,0
4 0,5,0
5 5,0,2
0 0,2,2
which is not matching the sample output

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

How about sorting the file based on longitude/latitude. Then print 2 closest of nth id as i-1, i+1 and max(i-2,i+2).
Quicksort should be nlog(n) and printing will be O(n).

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.