Microsoft Interview Question
Country: India
Person
{
string id;
Location location;
string phoneNumber;
List<Person> friends;
}
public void sendmessage(List<Person> groupofperson)
{
foreach(Person person in groupofperson)
{
foreach(Person friend in person.friends)
{
if(getDistance(person.location, friend.location)<=givenDistance)
{
sendMessage(person);
sendMessage(friend);
}
}
}
}
To get an efficient distance function, one might divide the world to hexagons of 1 mile side.
SetLocation of person p will assign it to a hexagon s.
now to find all the people with maximum 2 miles radius you need to check your hexagon for people and the hexagons surrounding you (6 of them) and thats it.
The use of hexagon and not square is because hexagons can wrap around a globe while squares not (think about a soccer ball)
Simple Observer pattern Design
1. There are two types of classes - Person class and Friend Class.
2. Person Class should be notified only when the nearness of friend is updated. Person class should notify of its location changes to friend. Person Class should implement LocationObservable Interface and NearnessObserver Interface
3. Friend Class should be notified only when the location of the person is updated. Friend class should notify of its nearness location based on the location changes he receives from the Person.
4. Following is a simple method stub , not complete solution just class diagram :
public interface LocationObservable {
addFriend(LocationObserver locationObserver);
removeFriend(LocationObserver locationObserver);
notifyLocationChangeToAll();
notifyLocationChangeToObserver(LocationObserver locationObserver);
}
public interface LocationObserver{
getLocationUpdates();
}
public interface NearnessObersvable{
addNearnessNotification(Nearness Observer nearnessObserver);
removeNearnessNotification(NearnessObserver nearnessObserver);
notifyNearnessChange(Nearness Observer);
notifyNearnessChangeToAll();
}
public interface NearnessOberserver{
getNearNessUpdates();
}
public class Friend implements LocationObserver,NearnessObservable{
private List<NearnessObserver> persons;
addNearnessNotification(Nearness Observer nearnessObserver){
}
removeNearnessNotification(NearnessObserver nearnessObserver){
}
notifyNearnessChange(Nearness Observer){
}
notifyNearnessChangeToAll(){
}
getLocationUpdates(){
}
}
public class Person implements NearnessOberserver, LocationObservable{
private List<LocationObserver> friends;
getNearNessUpdates(){
}
addFriend(LocationObserver locationObserver){
}
removeFriend(LocationObserver locationObserver){
}
notifyLocationChangeToAll(){
}
notifyLocationChangeToObserver(LocationObserver locationObserver){
}
}
for design, we may implement Publisher subscriber (Same type -- but difference instance subscription)..
In this way you don't have to maintain a list (due to subscription...).
- Anonymous23 July 03, 2014Note: this code does not reflect the logic of location, so you may have other logic for that...
the point here is the design on how to notify others when one state change... Also on the above code, others are notified PublishNewLocation is called, however, you can implement or add a property where when this property value changed or set, then PublishNewLocation is called...
Hope this helps...