On m'a posé cette question dans une interview aujourd'hui. J'ai essayé une solution mais j'aimerais savoir s'il y a une meilleure façon de résoudre ce problème:
question : J'ai une arracheListe dire de 500 000 éléments de sorte que la valeur de chaque élément du tableau est la même que l'index. Pour ex: list.get.get (0) = 0; list.get (1) = 1 ... etc. Mais un seul élément est hors de synchronisation avec cette commande [i.e list.get (i)! = I]. Comment trouvez-vous cet élément?
Y a-t-il un moyen de résoudre ce problème sans itération de la liste? Ou une meilleure façon?
6 Réponses :
Dans le pire des cas, vous devez examiner chaque élément, vous ne pouvez donc pas améliorer la complexité du temps Dans cet esprit, le meilleur algorithme consiste à numériser la liste des matrices du début à la fin. De cette façon, vous utilisez au mieux la bande passante mémoire disponible.
Ce n'est pas tout à fait clair pour moi comment ou pourquoi le filetage est entré dans l'image. Il semble hors de propos. Cela faisait-il partie de la question? O (n) .
La question est assez terne de cette façon, même si je suis d'accord avec votre opinion.
@aix Non, c'était ma réponse à l'intervieweur. Je pensais que l'utilisation d'une gamme d'épissures et une manipulation de l'itération du tableau serait réellement meilleure mais j'ai réalisé plus tard que O (n) ne peut être amélioré même avec plusieurs threads. En fait, les threads n'introduiront que plus de complexité.
Bien que vous puissiez venir au problème des deux extrémités de la liste dans la même boucle.
@NICKHOLT: Eh bien, il y a un nombre de façons dont on pourrait essayer de se dérouler partiellement de cette boucle. Cela nécessiterait du profilage de pouvoir dire quelque chose de significatif sur les implications de la performance (et bien sûr, il ne changera pas le O (n) ).
Yup, l'ajout de fils n'aidera pas si l'E / S de la mémoire est le goulot d'étranglement. La plupart des processeurs ont une interface à la mémoire externe afin que plus de threads sur plusieurs noyaux ne puissent pas aider.
Vous ne pouvez pas faire mieux que Et deuxièmement, je pense que c'est une mauvaise idée de parler de threads et de multiples multiples dans ces problèmes. Ils ne sont pas intéressants du tout. À la fin, vous avez un runtime de O (peu importe) où votre constante est supprimée de toute façon.
Peut-être que l'intervieweur signifiait une matrice triée avec des éléments de 0 à N-1 avec index 0 à N-1. Puis déplacez un élément à une autre position. Mais cela signifie que tous les éléments restants ont des index différents! Dans ce scénario, vous pouvez améliorer votre recherche avec une recherche binaire:
Ensuite, vous pouvez obtenir l'élément dans O (n) .
O (journal n) . Commencez au milieu et vérifiez si l'index est égal à l'élément. S'il est égal, faites la même chose avec la partie supérieure de la moitié, sinon utilisez l'autre partie.
Je suis d'accord. Et 500 000 n'étaient même pas beaucoup pour un seul fil à itérer de nos jours
Votre O (log n) algorithme semble échouer sur la liste 1, 0, 2, 3, 4, 5 . Au lieu de bouger, avez-vous voulu dire enlever? Alors ça marche.
@billy, je pense que ce qu'il veut dire, c'est que si la règle générale est F (n + 1) = F (n) +1 (sauf si cible particulière), une recherche binaire est idéale ici.
@billy: Pourquoi échoue-t-il sur cette liste? Je trouverai l'élément 0 dans O (journal n) .. Dans ce cas, chaque élément a un index différent. Nous recherchons donc index 0 ...
@ degedl0r J'ai déplacé l'élément 1 à l'élément 0, mais les index de tout le reste n'étaient pas touchés. Par conséquent, lorsque vous regardez le point médian, vous verrez qu'il n'a pas changé et regarde dans la moitié supérieure.
@JingTengXue Je conviens que votre version de la règle fonctionne. Cependant, j'étais remarquable que "déplacer un élément à une position différente" n'entraîne pas une liste de la liste de la liste.
Suite à la réponse de @ Aix, que diriez-vous de faire 2 chèques par boucle:
for (int i = 0; i < list.size / 2; i++)
{
if (i != list.get(i))
{
return i;
}
else if (list.size - i != list.get(list.size - i)
{
return list.size - i;
}
}
Mon point de vue est que, en l'absence de points de repère de performance, la boucle déroulante se dérouler est mieux à gauche au compilateur JIT.
@aix ouais, je serais d'accord, purement en termes de lisibilité, je voudrais éviter de faire quelque chose comme ça.
1. iterate through the list 2. check for the condition in the elements 3. when that only element found break out the loop... I Don't think Thread Enters the Arena...
La réponse est: une itération. Votre mention de la concurrence de la cause est une chose qu'ils pêchent.
En fait, depuis Java 8, la solution indiquée parallèle ou non est simple. Je pense que le plus aurait apporté:
ArrayList<Integer> s = new ArrayList<Integer>();
for (int i=0; i<500000; i++) {
s.add(i);
}
s.set(13, 500002);
for (int j=0; j<s.size(); j++) {
if (j != s.get(j)) {
System.out.println(j + " " + s.get(j));
}
}
Avec aucune indication sur l'endroit où ce nombre pourrait figurer dans la liste, la question est une sorte de ennuyeuse.
Je pense que vous devez expliquer ce que "un seul élément est hors de synchronisation" signifie vraiment. Cela n'a pas de sens. Voir ma réponse ci-dessous. Je pense que si vous déplacez un élément, tous les éléments restants seront hors de synchronisation, non?
@ died0r l'élément n'est pas enlevé. L'intervieweur a demandé comment identifier l'élément dont la valeur n'est pas la même que l'index.
Je pense qu'il n'est pas sur le point de trouver un moyen d'accéder à des zones simultanément différentes ... il s'agit davantage de réduire l'accès des données ...