Facebook Interview Question Software Engineer / Developers

  • facebook-interview-questions
    0
    of 0 votes
    3
    Answers

    It's A Small World
    As a popular engineer, you know many people in your home city. While traveling around town, visiting your friends, you realize it would be really handy to have a program that tells you which of your friends are closest based upon which friend you are currently visiting.

    Being an engineer who is interested in writing software that is useful to everyone, you decide to write a general solution to your quandary. Each of your friends lives at a unique latitude and longitude. For the purposes of this program, the world is flat, and the latitude and longitude are for all intents and purposes Cartesian coordinates on a flat plane. For example, in our flat world, lat 45, long -179 is not as close to lat 45, long 179 when compared to lat 45, long 170.

    Write a program that takes a single argument on the command line. This argument must be a file name which contains the input data. Your program should output the nearest three other friends for each friend in the list. You are virtually a celebrity and your friend list can be astoundingly huge. Your program must exhibit better than quadratic asymptotic growth in runtime as a function of the size of your friend list, and be robust and resource efficient.



    Input specifications
    The input file consists of multiple lines, all of which follow the same format. Each line has three values separated by an amount of white space. The first value is the unique id number of that friend, expressed as an integer. The second value is the latitude of that friend, expressed as a rational number. The third and last value is the longitude of that friend, expressed as a rational number. Every friend lives at a unique combination of latitude and longitude (e.g. no two friends will ever share the exact same values). Each line ends with a single new line, except for the last line of the file, which may or may not have a terminating new line.

    Example input file:
    1 0.0 0.0
    2 10.1 -10.1
    3 -12.2 12.2
    4 38.3 38.3
    5 79.99 179.99 You are guaranteed that your program will run against an input file that is well formed, and has at least four lines. You are also guaranteed that your list of friends have unique distances between one another; no two distinct pairs of friends will have the same distance between them.



    Output specifications
    In the order presented in the input file, output the nearest three friends for each friend. Each line of output should start with the integer id of the friend followed by a single space character, and then the list of three nearest other friend ids followed by a single new line. Even the last line of the output should terminate in a new line. This list should be comma-delimited, with no spaces. The list must be in order of proximity, with the closest of the three being first, and the farthest of the three being last.

    Example output:
    1 2,3,4
    2 1,3,4
    3 1,2,4
    4 1,2,3
    5 4,3,1

    - daxingqiao on June 29, 2011 Report Duplicate | Flag
    Facebook Software Engineer / Developer



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 on 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 on 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 on September 28, 2011 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book walking you through 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