Microsoft Interview Question
Country: India
HashTable would be nice. Since you might want to update the distances every few minutes. You could just maintain a hashtable for the friends that are sufficiently close to the user ( say < 20 miles ). Update the hashtable if needed with new friends and existing friends distances.
A better idea would be to use a min heap, with the distance being saved along with the friend id in each node of the heap. That way, you would only have to check for the friends with minimum distance every few seconds, and update the rest in a longer duration.
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){
}
}
HashTable would be nice. Since you might want to update the distances every few minutes. You could just maintain a hashtable for the friends that are sufficiently close to the user ( say < 20 miles ). Update the hashtable if needed with new friends and existing friends distances.
- Rushabh October 18, 2014A better idea would be to use a min heap, with the distance being saved along with the friend id in each node of the heap. That way, you would only have to check for the friends with minimum distance every few seconds, and update the rest in a longer duration.