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;
	readPoints(argv[1], 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;
}

- dongre.avinash August 03, 2011 | Flag Reply
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

- :P September 28, 2011 | Flag Reply
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).

- tezkrishna September 28, 2011 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More