Trouver l'existence d'un nombre dans une liste triée en temps constant? (Question d'entrevue)

Question

Je suis étudiant pour les prochains entretiens et ont rencontré à cette question plusieurs fois (écrit textuellement)

De trouver ou de déterminer la non-existence d'un nombre dans une liste de N nombres, où les numéros de plage de plus de M, M >> N et N assez grand pour s'étendre sur plusieurs disques. Algorithme de battre O(log n); des points bonus pour la constante de temps de l'algorithme.

Tout d'abord, je ne suis pas sûr si c'est une question avec une réelle solution. Mes collègues et moi avons réfléchi sur ce problème pendant des semaines, et il semble mal formé (bien sûr, juste parce que nous ne pouvons pas penser à une solution ne signifie pas qu'il n'en est pas une). Quelques questions que j'aurais demandé à l'enquêteur sont les suivantes:

• Sont il répète dans la liste triée?
• Quel est le rapport du nombre de disques et N?

Une approche que j'en considération est à la recherche binaire min/max de chaque disque afin de déterminer le disque qui doit contenir ce nombre, si elle existe, puis une recherche binaire sur le disque lui-même. Bien sûr ce n'est qu'un ordre de grandeur de l'accélération si le nombre de disques est grand et vous avez également une liste triée des disques. Je pense que cela donnerait une sorte de O(log log n) fois.

Comme pour le M >> N indice, peut-être que si vous savez combien de numéros sont sur un disque et que la plage est, vous pouvez utiliser le casier principe de la règle certains cas, une partie du temps, mais je ne peux pas comprendre un ordre de grandeur de l'amélioration.

Aussi, les "points bonus pour la constante de temps de l'algorithme" me fait un peu suspect.

Des idées, des solutions, ou pertinents de l'histoire de ce problème?

Answer 1

Depuis que la question ne précise pas le format dans lequel les numéros sont stockées vous pouvez dire à l'intervieweur que vous allez supposer que les nombres sont stockés dans un sens physique. Par exemple, chaque numéro peut être écrit sur une carte et chaque carte est détenue par une seule personne.

N assez grand pour s'étendre sur plusieurs disques

Maintenant, si vous voulez trouver ou de déterminer la non-existence d'un numéro que vous pouvez il suffit de demander aux personnes si le numéro que vous cherchez est sur la carte, ils sont en attente.

Si personne ne répond dans les N secondes, puis le nombre n'est pas là. C'est en supposant que tout le monde peut vous entendre et de vous chaque personne est consciente de ce nombre qu'ils ont sur leur carte.

Je ne sais pas beaucoup au sujet de la physique (Vitesse du son, la friction de l'air, le temps pour chacune des personnes du cerveau à regarder leur carte, etc)

Answer 2

Assez étrange, la question est de déterminer la NON-EXISTENCE d'une valeur, pas l'existence.

Cela peut impliquer qu'ils se réfèrent à un filtre Bloom ( http://en.wikipedia.org/wiki/Bloom_filter ). Un filtre Bloom peut vous dire si un élément:

• n'existe pas
• ou existe peut-être

Answer 3

Par la lettre de la question, ils sont probablement à la recherche d'une interpolation de recherche, qui est dans la moyenne des cas O(log log n). Oui, c'est O(n) dans le pire des cas, mais peut être améliorée par la connaissance de la distribution ou de l'utilisation d'une interpolation-binaire de recherche.

Cela se joue dans le M >> N indice. La moyenne de l'analyse de cas de l'interpolation de recherche est assez complexe, donc je ne vais même pas tenter une modification en vertu de la M >> N. Mais conceptuelle, en vertu de la M >> N et en supposant une distribution uniforme, on peut supposer que la valeur sera délimitée par +/-1 de la recherche initiale position, produisant O(1).

Une mise en œuvre pratique pourrait faire la première interpolation une fois, et si la valeur de recherche n'est pas borné, de revenir à une recherche binaire.

Vous ne savez pas comment plusieurs disques pourrait être utilisé à son avantage dans cette approche, quoique...

Answer 4

Le premier regard

M >> N est pas un indice, je pense que, tout simplement, il décourage la création d'un bitmap qui irait directement à vous dire en O(1) si un nombre existe.

Je pense que sane hypothèse N étendant sur plusieurs disques durs, c'est que vous pouvez vous attendre que vous n'auriez pas de l'ordre de magnitutde plus de disques à votre disposition. Comme vous le feriez besoin de 2^M de l'espace de O(1) de la performance, et si N s'étend sur plusieurs disques, puis M s'étend sur >> plusieurs disques et 2^M s'étend sur >> les disques disponibles.

Aussi, il vous dit qu'approche pour stocker le manque de numéros ne serait pas efficace car ensuite, vous avez à stocker des nombres de X où

X = M - N => X ~ M (puisque M >> N)

qui est alors une pire des cas.

Donc, à première vue, il semble que vous pouvez prouver qu'il n'existe pas de meilleure réponse.

EDIT: J'ai encore debout dans le raisonnement ci-dessus, qui est aussi mieux encore prouvé par Moron de la réponse. Toutefois, la conclusion, d'après la Floraison, Filtre à partir de Patrick réponse, je crois que le journaliste pourrait avoir été à la recherche à ce sujet et d'autres les algorithmes probabilistes (qui doit avoir été indiqué dans la question de l'entrevue).