On m'a demandé la question suivante dans l'interview récemment:
Supposons que vous ayez, suivez la grille sur le système de coordonnées cartésiennes (quadrant I). p>
o - x - x - x - o
| | | | |
x - x - x - o - x
| | | | |
x - o - o - x - x
where, o => person at intersection and x => no person at intersection
class Point {
int x;
int y;
boolean hasPerson;
}
Point findNearestPointWhereAllPeopleCanMeet(Point[] people) {
}
3 Réponses :
Avant d'aller étudier les arbres K-D, ce sont des pensées qui me sont venues à mon esprit:
E.g. Point donné (0,0):
La max_distance pour (0,0) est 6. Compte tenu de votre entrée, le plus bas max_distance doit être 3 et il existe de nombreux points avec cette valeur similaire (2,1) par exemple.
Il devrait y avoir des moyens de rendre cet algorithme plus efficace. Peut-être avec des arbres KD: P ou avec d'autres modifications telles que la vérification du nombre total de personnes, leur emplacement / distance relative, la valeur max_distance à toute itération, etc. / p>
Si le problème appelle à la minimisation du Distance Manhattan (c'est-à-dire que les gens ne font que marcher parallèlement à Les axes), alors le problème est alors assez trivial. Tout d'abord, sélectionner la coordonnée x et la coordonnée y sont des problèmes indépendants.
Puis, pour chaque coordonnée, trouvez simplement la valeur médiane de la position des personnes le long de cet axe. Pour de nombreuses configurations de personnes, il peut y avoir plus d'un point qui minimise la somme des distances de marche de toutes les personnes. (Considérez simplement 2 personnes séparées par plus de 2 blocs de x et dans la même coordonnée y; toute intersection entre les deux nécessitera la même marche totale par les deux personnes.)
Si le problème appelle à la minimisation de la distance euclidienne, l'objectif est de trouver la médiane de L1 à 2 variable. C'est un problème standard, mais c'est loin d'être trivial. (Voir ici , par exemple.) Il y a un réponse unique. Étant donné que c'était une question d'entrevue, je soupçonne que cela ne s'applique pas.
Cela vous donnera probablement plus d'une réponse approximative que la bonne réponse. Mais peut-être que vous pouvez essayer une sorte de clustering (voir le traitement des images médicales)
Et si vous projetez tous les points sur l'axe Y: puis projet sur l'axe x : légende: 3 * signifie 3 personnes à cette coordonnée sur l'axe trouvent maintenant la médiane utilise également les poids (poids @Location = comment Beaucoup de gens à cet endroit sur l'axe) Si vous trouvez la médiane pour les deux axes, vous pourriez prendre les points de réunion comme (Medianx, Mediany). Vous pouvez obtenir le bon niveau plus proche Point Si lorsque vous calculez la médiane sur un axe, vous veillez également à minimiser la distance en calculant la médiane de l'autre axe. Ce dernier cas est plus difficile.
Si "point le plus proche de tout point donné" signifie une somme minimale de distances, puis regardez en.wikipedia.org/ wiki / géométric_median