Google Interview Question Applications Developers
Country: India
Interview Type: In-Person
Hi Miguel,
The problem here is how would you find which hotels to process? are you going to process all known hotels in the city? This number would be quite large.
The processing of all the hotels will have to be done, no doubt about that but that will be a pre processing step and this step wont be done when searching for a nearest hotel.
For processing of the hotels, we can use 2d tree algorithm which uses BST for storing hotel locations in a binary search tree format and for searching of the nearest hotels, we can use 2d orthogonal range search on the 2d BST.
The question states "You are given information about hotels in a country/city. X and Y coordinates of each hotel are known. ", so that's not an issue.
Going for trees only make sense if we have multiple queries (as the algorithm is much more complex). The question didn't mention multiple queries.
There are 2 steps for finding nearest neighbor (nearest hotel) question.
Step1: Preprocessing of all the hotels in the city / country.
This will be done using 2d tree approach as following. Data structure will be a binary search tree.
We start with say downtown hotel. That becomes a root of the BST. Now all the hotels in 2 dimensional co-ordinate system to the left of the imaginary vertical line going from the hotel at the root are saved in the left half of the BST and all the hotels to the right of the root are saved in the right half of the BST.
|
| ---------------Hotel D -----------
-----Hotel E--------- |
Hotel A
|
-------Hotel B -------|
| |
Hotel C |
| |
| |
| |
A
/ \
B D
/ \
C E
Now for Hotel B, which is to the left of A, we save this hotel to the left of A and draw an imaginary horizontal line in the plan with hotel B on the line. For any hotel below Hotel B will be to the left of B and to the left of A in the BST.
For any hotel to the right of A will be to the right of the root in the BST. something like below.
Time taken: To construct the BST will be O (N)
Searching:
Now for Searching nearest neighbors for a given point in the co-ordinate system we perform following steps.
We keep hotel distance min Heap. (min priority Queue)
If the search point is to the left of root hotel, we first go to the left of the root hotel and search for all the hotels to the left of A which could be nearer to the search point.
Then we check if the origin point is above hotel B or below it. Based on that we either go to the left or the right of B and keep their distances (straight line from the hotel to search point) in the min heap.
Time taken: Since its a simple BST search, Typical Case: O(log N) and worst case will be O(N)
You're mixing 2d-trees and BST. We would need 2d-trees for a 2 dimensional space. The best time complexity to build a 2d-tree is O(n log n) as shown on Wikipedia.
I believe you didn't include the heap operations time complexity in your overall query complexity. Your doing multiple heap operations per query, so it will not be just O(log N) on average.
Not sure what datastructure we could use, so I just made one up. A hotel directory containing list of all hotels and also map of type of hotel, example all Holiday Inn locations.
I could have used priority queue as well, especially if we are to limit the number of nearest hotels to be displayed.
I have a hotel object, which can store all the information pertaining to a hotel. The directory list is initially sorted based on distance from origin (0,0).
For every user query, the distances of all hotels are updated and sorted. Again with PQ, that would be done as the updates are happening. For specific hotel query, I would do the same thing to the list stored against the hotel name and not all the hotels.
package com.google.practice;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
//To store hotel information
class Hotel implements Comparable<Hotel>{
private String name=null;
private int x;
private int y;
private double distance;
public Hotel(String name,int x,int y){
this.name = name;
this.x = x;
this.y = y;
this.computeDistance(0,0);
Origin.getInstance().hotels.add(this);
}
@Override
public int compareTo(Hotel h) {
// TODO Auto-generated method stub
return Double.compare(this.distance, h.distance);
}
//intial distance from [0,0]
protected void computeDistance(int x,int y){
if(this.x==x){
this.distance = Math.abs(this.y-y);
}else if (this.y==y){
this.distance = Math.abs(this.x-x);
}else {
int a = Math.abs(this.x-x);
int b = Math.abs(this.y-y);
this.distance = Math.sqrt(a*a+b*b);
}
}
public String toString(){
return this.name+" at a distance of "+this.distance;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
}
class Origin{
private int x=0,y=0;
private static Origin _org = new Origin();
protected List<Hotel> hotels = new ArrayList<Hotel>();
private Origin(){};
//recalculate distance from user co-ordinates
public List<Hotel> updateOrigin(int x,int y,HotelDirectory d){
this.x = x;
this.y = y;
for(Hotel h : hotels){
h.computeDistance(this.x,this.y);
}
Collections.sort(d.hotelDirectory);
return d.hotelDirectory;
}
//recalculate distance from user co-ordinates for specific hotel
public List<Hotel> updateOrigin(int x,int y,HotelDirectory d,String name){
this.x = x;
this.y = y;
List<Hotel> tmp = d.hotelDirectoryByHotel.get(name);
for(Hotel h : tmp){
h.computeDistance(this.x,this.y);
}
Collections.sort(tmp);
d.hotelDirectoryByHotel.put(name, tmp);
return tmp;
}
public static Origin getInstance(){
return _org;
}
}
class HotelDirectory{
private static HotelDirectory _hDir = new HotelDirectory();
public List<Hotel> hotelDirectory = new ArrayList<Hotel>();
public Map<String,List<Hotel>> hotelDirectoryByHotel = new HashMap<String,List<Hotel>>();
private HotelDirectory(){};
public void addHotel(String name, int x,int y){
Hotel h = new Hotel(name,x,y);
this.addHotel(h);
}
public void addHotel(Hotel h){
this.hotelDirectory.add(h);
updateHotelWise(h);
}
private void updateHotelWise(Hotel h){
List<Hotel> tmp;
if(hotelDirectoryByHotel.containsKey(h.getName())){
tmp = hotelDirectoryByHotel.get(h.getName());
}else{
tmp = new ArrayList<Hotel>();
}
tmp.add(h);
hotelDirectoryByHotel.put(h.getName(), tmp);
}
public void removeHotel(Hotel h){
this.hotelDirectory.remove(h);
}
public static HotelDirectory getInstance(){
return _hDir;
}
}
public class HotelFinder {
public static HotelDirectory directory;
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
buildHotelDirectory();
System.out.println(directory.hotelDirectory);
System.out.println(Origin.getInstance().updateOrigin(3, 1,directory));
System.out.println(Origin.getInstance().updateOrigin(2, 7,directory));
System.out.println(Origin.getInstance().updateOrigin(10, -1,directory));
System.out.println(Origin.getInstance().updateOrigin(-5, 10,directory));
System.out.println(Origin.getInstance().updateOrigin(-5, 10,directory,"Maharaja Inn"));
System.out.println(Origin.getInstance().updateOrigin(3, 10,directory,"Maharaja Inn"));
}
public static void buildHotelDirectory(){
directory = HotelDirectory.getInstance();
directory.addHotel("Holiday Inn", 1, 1);
directory.addHotel("Quality Inn", 2, 3);
directory.addHotel("Astre Inn", 1, 4);
directory.addHotel("Dalia Inn", 3, 3);
directory.addHotel("Maharaja Inn", 4, 4);
directory.addHotel("Hampton Inn", 2, 5);
directory.addHotel("Maharaja Inn", 5, 5);
Collections.sort(directory.hotelDirectory);
}
}
Another better idea I have is
1. consider the origin to be any corner point enclosing a country. So all the hotels in the country will lie in one quadrant.
2. Compute initial distance of all hotels from this origin, store in a list and sort.
3. for every user query, we can also accept max radius. compute user distance from origin. Now, subtract radius value from user distance and do a binary search on list for this value. Once you find a value, copy that and all subsequent hotel values until user distance plus radius.
4. Now you have list of all nearest hotels. Compute the distance of these hotels from user, store it a PQ or list, sort if you use list and display.
Will post the solution by tomorrow.
Here is a little better version. looks a little scary but logic is trivial. using distance and slope of each hotel to match with user location +/- radius. updating only a subset of original directory. Although my subsequent sorts are on subset, I still do that one time sort on complete hotel list after pre-processing. Hence O(n log n).
package com.google.practice;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
//To store hotel information
class Hotel implements Comparable<Hotel>{
private String name=null;
private int x;
private int y;
private double distance;
private double slope = 999;
public Hotel(String name,int x,int y){
this.name = name;
this.x = x;
this.y = y;
this.computeDistance(0,0);
Origin.getInstance().hotels.add(this);
}
@Override
public int compareTo(Hotel h) {
// TODO Auto-generated method stub
return Double.compare(this.distance, h.distance);
}
//intial distance from [0,0]
protected void computeDistance(int x,int y){
if(this.x==x){
this.distance = Math.abs(this.y-y);
}else if (this.y==y){
this.distance = Math.abs(this.x-x);
if(x==0 && y==0)
this.slope=0;
}else {
int a = Math.abs(this.x-x);
int b = Math.abs(this.y-y);
this.distance = Math.sqrt(a*a+b*b);
if(x==0 && y==0)
this.slope = (this.y-y)/(this.x-x);
}
}
public String toString(){
return this.name+" at a distance of "+this.distance;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public double getDistance() {
return distance;
}
public void setDistance(double distance) {
this.distance = distance;
}
public double getSlope() {
return slope;
}
public void setSlope(double slope) {
this.slope = slope;
}
public int getX() {
return x;
}
public void setX(int x) {
this.x = x;
}
public int getY() {
return y;
}
public void setY(int y) {
this.y = y;
}
}
class Origin{
private int x=0,y=0;
private static Origin _org = new Origin();
protected List<Hotel> hotels = new ArrayList<Hotel>();
private Origin(){};
//recalculate distance from user co-ordinates
public List<Hotel> updateOrigin(int x,int y,HotelDirectory d){
this.x = x;
this.y = y;
for(Hotel h : hotels){
h.computeDistance(this.x,this.y);
}
Collections.sort(d.hotelDirectory);
return d.hotelDirectory;
}
//recalculate distance from user co-ordinates for specific hotel
public List<Hotel> updateOrigin(int x,int y,HotelDirectory d,String name){
this.x = x;
this.y = y;
List<Hotel> tmp = d.hotelDirectoryByHotel.get(name);
for(Hotel h : tmp){
h.computeDistance(this.x,this.y);
}
Collections.sort(tmp);
d.hotelDirectoryByHotel.put(name, tmp);
return tmp;
}
public static Origin getInstance(){
return _org;
}
}
class HotelDirectory{
private static HotelDirectory _hDir = new HotelDirectory();
public List<Hotel> hotelDirectory = new ArrayList<Hotel>();
public Map<String,List<Hotel>> hotelDirectoryByHotel = new HashMap<String,List<Hotel>>();
private HotelDirectory(){};
public void addHotel(String name, int x,int y){
Hotel h = new Hotel(name,x,y);
this.addHotel(h);
}
public void addHotel(Hotel h){
this.hotelDirectory.add(h);
updateHotelWise(h);
}
private void updateHotelWise(Hotel h){
List<Hotel> tmp;
if(hotelDirectoryByHotel.containsKey(h.getName())){
tmp = hotelDirectoryByHotel.get(h.getName());
}else{
tmp = new ArrayList<Hotel>();
}
tmp.add(h);
hotelDirectoryByHotel.put(h.getName(), tmp);
}
public void removeHotel(Hotel h){
this.hotelDirectory.remove(h);
}
public static HotelDirectory getInstance(){
return _hDir;
}
public List<Hotel> getNearestHotels(int x, int y, int radius){
List<Hotel> nearestHotels;
double userDistance;
double maxDistance,minDistance,maxSlope,minSlope;
if(x==0){
userDistance = y;
}else if (y==0){
userDistance = x;
}else {
userDistance = Math.sqrt(x*x+y*y);
}
minDistance = userDistance - radius;
maxDistance = userDistance + radius;
if(y==0)
maxSlope = 999;
else
maxSlope = y/(x-radius);
if(x==0)
minSlope = 0;
else
minSlope = y/(x+radius);
nearestHotels = findHotels(minDistance,maxDistance,minSlope,maxSlope);
if(nearestHotels==null){
System.out.println("You are in no man's land");
return null;
}else{
List<Hotel> tmp = new ArrayList<Hotel>();
for(Hotel h:nearestHotels){
Hotel hTmp = new Hotel(h.getName(),h.getX(),h.getY());
hTmp.computeDistance(x, y);
tmp.add(hTmp);
}
Collections.sort(tmp);
return tmp;
}
}
public List<Hotel> findHotels(double minDistance,double maxDistance,double minSlope,double maxSlope){
List<Hotel> hotelsDistance = new ArrayList<Hotel>();
List<Hotel> hotelsSlope = new ArrayList<Hotel>();
boolean isLow=false,isHigh=false;
if(Double.compare(minDistance, hotelDirectory.get((hotelDirectory.size()-1)/2).getDistance())==1)
isHigh = true;
else
isLow = true;
int pos = binarySearch(0,hotelDirectory.size()-1,minDistance,isLow,isHigh,0);
if(pos==0){
for(Hotel h : hotelDirectory){
if(Double.compare(h.getDistance(), maxDistance)==1)
break;
if(Double.compare(h.getSlope(), minSlope)==1 && Double.compare(h.getSlope(), maxSlope)==-1){
hotelsSlope.add(h);
}
hotelsDistance.add(h);
}
if(!hotelsSlope.isEmpty())
return hotelsSlope;
if(hotelsSlope.isEmpty() && !hotelsDistance.isEmpty())
return hotelsDistance;
else if(hotelsSlope.isEmpty() && hotelsDistance.isEmpty())
return hotelDirectory.subList(0, hotelDirectory.size()/4);
}else if(pos==hotelDirectory.size()-1){
return hotelDirectory.subList((hotelDirectory.size()*3)/4, hotelDirectory.size()-1);
}else{
int l=pos-1,r=pos+1;
if(Double.compare(hotelDirectory.get(pos).getSlope(), minSlope)==1 && Double.compare(hotelDirectory.get(pos).getSlope(), maxSlope)==-1)
hotelsSlope.add(hotelDirectory.get(pos));
hotelsDistance.add(hotelDirectory.get(pos));
while((l>(int)minDistance || r<(int)maxDistance)){
if(l>(int)minDistance && l>=0){
if(Double.compare(hotelDirectory.get(l).getSlope(), minSlope)==1 && Double.compare(hotelDirectory.get(l).getSlope(), maxSlope)==-1)
hotelsSlope.add(hotelDirectory.get(l));
hotelsDistance.add(hotelDirectory.get(l));
l--;
}else{
l=-1;
}
if(r<(int)maxDistance && r<=hotelDirectory.size()-1){
if(Double.compare(hotelDirectory.get(r).getSlope(), minSlope)==1 && Double.compare(hotelDirectory.get(r).getSlope(), maxSlope)==-1)
hotelsSlope.add(hotelDirectory.get(r));
hotelsDistance.add(hotelDirectory.get(r));
r++;
}else{
r=-1;
}
if(l==-1 && r==-1)
break;
}
if(!hotelsSlope.isEmpty())
return hotelsSlope;
else
return hotelsDistance;
}
return null;
}
public int binarySearch(int low, int high,double minDistance,boolean isLow,boolean isHigh,int last_pos){
int mid = (low+high)/2;
if(low>high)
return last_pos;
if((int)minDistance==(int)hotelDirectory.get(mid).getDistance())
return mid;
last_pos = mid;
if(isLow && (int)minDistance>(int)hotelDirectory.get(mid).getDistance())
return last_pos;
if(isHigh && (int)minDistance<(int)hotelDirectory.get(mid).getDistance())
return last_pos;
if((int)minDistance>(int)hotelDirectory.get(mid).getDistance())
binarySearch(mid+1,high,minDistance,isLow,isHigh,last_pos);
else
binarySearch(low,mid-1,minDistance,isLow,isHigh,last_pos);
return last_pos;
}
}
public class HotelFinder {
public static HotelDirectory directory;
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
buildHotelDirectory();
System.out.println(directory.hotelDirectory);
System.out.println(directory.getNearestHotels(3, 10, 0));
System.out.println(directory.getNearestHotels(10, 10, 5));
System.out.println(directory.getNearestHotels(6, 6, 5));
System.out.println(directory.getNearestHotels(1, 1, 5));
}
public static void buildHotelDirectory(){
directory = HotelDirectory.getInstance();
directory.addHotel("Holiday Inn", 1, 1);
directory.addHotel("Quality Inn", 2, 3);
directory.addHotel("Astre Inn", 1, 4);
directory.addHotel("Dalia Inn", 3, 3);
directory.addHotel("Maharaja Inn", 4, 4);
directory.addHotel("Hampton Inn", 2, 5);
directory.addHotel("Maharaja Inn", 5, 5);
Collections.sort(directory.hotelDirectory);
}
}
result for 4 queries
1. [Hampton Inn at a distance of 5.0990195135927845, Maharaja Inn at a distance of 5.385164807134504, Maharaja Inn at a distance of 6.082762530298219, Dalia Inn at a distance of 7.0]
2. [Maharaja Inn at a distance of 7.0710678118654755, Maharaja Inn at a distance of 8.48528137423857, Dalia Inn at a distance of 9.899494936611665]
3. [Maharaja Inn at a distance of 1.4142135623730951, Maharaja Inn at a distance of 2.8284271247461903, Hampton Inn at a distance of 4.123105625617661, Dalia Inn at a distance of 4.242640687119285]
4. [Holiday Inn at a distance of 0.0, Quality Inn at a distance of 2.23606797749979, Dalia Inn at a distance of 2.8284271247461903, Astre Inn at a distance of 3.0, Hampton Inn at a distance of 4.123105625617661, Maharaja Inn at a distance of 4.242640687119285]
I am not sure if I am correct. My algorithm is that first, calculation all the distance between the hotels and the user's point, it takes O(n). Then use the quick sort to make the list, it takes O(log n) in general case, but it takes O(n^2) in the worst case. So the total time complexity in general should be O(n+log n).
Simple enough, but let's consider your analysis a bit more. Say we use L1 norm to approximate distance (manhattan distance), then you are correct with O(n) distance calculations (this is already an improvement over squaring/square root). Then sorting (merge sort) takes O(n*log(n)). O(n) + O(n*logn) is still O(n*logn).
Data preparation:
Create a map of all hotels with the X cordinate. Lets call it Xmap
Let person be at (x1,y1)
Let the x range be Xr and y range be Yr.. This defines a block area around the person.
Find all the hotels with x coordinate in the range x1 - Xr to x1 + Xr. using Xmap.
In the resulting set of hotels pick the ones within the range y1 -Yr and y1 +Yr.
Not a typical answer, but I just want to share how easy the problem can be resolved with database. We haven't seen much database solutions on this site. Here the data structure is a table Hotel ans @X0, @Y0 are the coordinates of the user and @Top is the number of nearest cities to return.
In Transact-SQL
CREATE TABLE Hotel(Name varchar(50), X Double, Y Double)
;With A(Name, X, Y, Distance2) AS
(
SELECT Name, X, Y, (X-@X0)*(X-@X0)+(Y-@Y0)*(Y-@Y0)
FROM Hotel
)
SELECT Top @Top Name
FROM A
ORDER BY Distance2 DESC
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
long long distance(pair<int, int> a) {
long long first = a.first;
long long second = a.second;
return first * first + second * second;
}
bool comp(pair<int, int> a, pair<int, int>b) {
long long da = distance(a);
long long db = distance(b);
return da < db;
}
vector<pair<int, int> >nearest_hotels (vector<pair<int, int> > hotels, pair<int, int> user) {
for (int i = 0; i < hotels.size(); i++) {
hotels[i].first -= user.first;
hotels[i].second -= user.second;
}
sort(hotels.begin(), hotels.end(), comp);
return hotels;
}
Say we want the K nearest hotels.
- Miguel Oliveira June 19, 2014a) K is rather small (e.g. K <= 30). Process each hotel, 1-by-1. Use a max-heap to keep the K nearest hotels seen so far. If an hotel is closer than the Kth in the heap, remove it and add the closer one. Time complexity will be O(N log K) with extra O(K) for the heap.
b) K is large and we can use additional O(N) memory. Calculate the distance of each hotel to point (x, y). Use the median-of-medians algorithm to select the Kth smallest distance. After using this algorithm, the K-1 closest hotels are to the left of the Kth one, in no particular order. This algorithm takes O(N) time and memory (see wikipedia /wiki/Median_of_medians).