TL;DR
- Le Problème: Maîtriser le problème CTCI 9.3 avec une efficacité de niveau production.
- L'Approche: Problème CTCI 9.3: architecture pour un crawler web distribué gérant les doublons et les règles de politesse d'hôte.
- Complexité: Compromis optimal entre temps et espace.
Cet article propose une explication claire et accessible du problème CTCI 9.3. Nous examinons l'énoncé, comparons l'approche brute à la solution optimale en Java.
1. Analogie du monde réel
Pensez au problème CTCI 9.3 comme à l'organisation efficace d'objets au quotidien. Choisir la bonne structure de données élimine les itérations inutiles.
2. Énoncé clair du problème
Problème 9.3: Problème CTCI 9.3: architecture pour un crawler web distribué gérant les doublons et les règles de politesse d'hôte.
3. Approche optimale et implémentation
public class URLFrontier {
private final Set<String> visitedURLs = ConcurrentHashMap.newKeySet();
private final BlockingQueue<String> urlQueue = new LinkedBlockingQueue<>();
public void addURL(String url) {
if (visitedURLs.add(url)) {
urlQueue.offer(url);
}
}
public String getNextURL() throws InterruptedException {
return urlQueue.take();
}
}
4. Complexité Temporelle et Spatiale
| Métrique | Complexité | Explication |
|---|---|---|
| Complexité Temporelle | O(N) / O(log N) | Parcours optimal des données |
| Complexité Spatiale | O(1) / O(N) | Empreinte mémoire contrôlée |
5. Cas Limites et Résumé
Vérifiez toujours les conditions aux limites, les valeurs nulles et la taille des tableaux en entretien.