On m'a posé ces questions dans une interview. Considérez le scénario de cartes perforées, où chaque carte perforée a un motif de 64 bits. J'ai été suggéré chaque carte comme un Aussi, à considérer que j'ai une matrice qui contient déjà 1000 cartes. Je dois générer un nouvel élément chaque fois que différent des 1000 cartes précédentes. Les entiers (cartes AKA) dans le tableau ne sont pas nécessairement triés.
Encore plus, comment cela serait-il possible que la question était pour C ++, où est-ce que le int puisque chaque INT est une collection de bits.
64 bit int provient et comment puis-je générer cette nouvelle carte à partir du tableau où l'élément à générer est différent de tous les éléments déjà présents dans le tableau?
13 Réponses :
Voici un algorithme O (N) : aussi loin que je suis au courant, c'est la seule façon dont vous allez obtenir o (n) . Si vous souhaitez gérer ce cas de Edge (assez important), vous allez devoir faire une sorte de tri ou une recherche appropriée, ce qui vous mènera à o (n log n) . intT64_max < / code> est déjà dans la liste.
O (n ^ 2) pire des cas, assez lent en effet: |
Vous pouvez également garder une trace des valeurs max / min, alors vous savez certainement que si vous choisissez Sayez Max + 1, c'est nouveau, puis mettez à jour ceci sous max. Ce sera juste aussi lent de première fois, mais après son o (1), même s'il nécessite qu'il y ait suffisamment d'espace en haut et en bas de la gamme.
@Oli: vrai. Mais il mentionne qu'il s'agit de la question de l'entrevue, j'aimerais penser que chaque question d'entretien dit implicitement "à quel point la possible peut être la plus rapide ... [et comment?]"
@Oli: Je pensais sûrement à cela, mais je n'ai pas donné cette réponse depuis que plus de 1000 éléments de plus de 1000 éléments ne seraient sûrement pas une bonne réponse à attendre.
@Cipher: OK, voir la réponse mise à jour. Je l'ai pris de O (n ^ 2) à la garantie O (n). Évidemment, si vous devez générer plus d'un nouvel élément, il tombe ensuite à O (1). Mais en supposant qu'aucun état, O (n) est le meilleur que vous puissiez faire.
Cette [solution mise à jour] échouera si max == max_int_64 et min_int_64 est également dans la liste.
Il échouera également s'il sera utilisé plus d'une fois, vous devez l'ajouter à la liste sinon, il retournera la même valeur tout le temps.
@Chris: Cette exigence était de générer un nouvel élément. Ajout à la liste peut être réalisé de manière triviale comme suit: list_of_cards.append (generatenewvalue (list_of_cards)) .
@Oli: Si la fonction conserve une trace d'un maximum , et trouve la valeur maximale utilisée moins que maximum-1 , il n'échoue pas si max_int_64 est dans la liste. . C'est beaucoup plus compliqué, mais peut alors éventuellement rendre tous les chiffres.
Je pense que la voie à suivre est d'utiliser une sorte de hachage. Donc, vous stockez vos cartes dans certains godets basés sur des disons sur le mode Mod. Jusqu'à ce que vous créiez une sorte d'indexation, vous êtes bloqué avec une boucle sur toute la matrice.
Si vous avez un coup d'œil sur la mise en œuvre de HASHSET en Java, vous pourriez avoir un indice.
Et comment l'OP trouverait-il un élément non existant dans une table de hachage?
Vous générez un numéro, obtenez le résultat de la fonction de hachage et de déterminer si la carte est déjà là, vous devez rechercher un godet unique plutôt que pour toute une matrice
J'ai du mal à estimer l'heure prévue de cette opération, mais le pire des cas pour la recherche est déjà O (n) (lorsque tous les entiers arrivent à mapper sur la même valeur de hachage).
C'est la façon dont les fonctions de hasch fonctionnent, juste :) dans le pire cas, vous vous retrouvez avec O (n), mais cela ne sera pas typique si vos cartes sont des nombres aléatoires. Vous pouvez affirmer que dans le pire des cas, vous ne trouverez jamais une nouvelle carte car votre génératrice de numéro aléatoire reviendra toujours '5' et, comme il y a déjà "5", vous êtes bloqué. Notez que je suppose (comme mentionné dans ma réponse), il devrait choisir une nouvelle carte aléatoire qui n'est pas encore dans la liste - la tâche est donc vraiment: "J'ai un nombre aléatoire. Est-ce déjà dans mon ensemble?"
Cette approche va de l'attendant O (1) à l'O (n) et prend la mémoire theta (n) car la table grandit. Le mien passe du pire cas O (LG N) à l'attendu O (1), temps et mémoire. Vous pourriez être plus rapide dans certaines situations, cependant, il y a donc un compromis par application.
Vous pouvez construire un arbre binaire des éléments déjà existants et la traverser jusqu'à ce que vous trouviez un nœud dont la profondeur n'est pas 64 et qui comporte moins de deux nœuds d'enfants. Vous pouvez ensuite construire un nœud enfant "manquant" et avoir un nouvel élément. Le devrait être assez rapide, dans l'ordre de O (n) si je ne me trompe pas.
Construire un arbre binaire de N éléments prend le temps. En outre, un nœud ayant <2 nœuds d'enfants n'indique pas une lacune dans la gamme d'entiers.
Construire un arbre binaire équilibré n'est pas O (n).
Je voulais juste suggérer ça. Ce n'est pas parce que les chiffres ne sont pas triés quand il les obtient, cela ne signifie pas qu'il ne peut pas le trier lui-même.
Comment construisez-vous un nouveau nœud enfant, tout en garantissant qu'il est unique?
C'est un arbre binaire utilisant les bits de l'entier comme valeurs de nœud. Par conséquent, si nous trouvons un nœud A qui a une profondeur de dire 63 et un seul enfant (avec, sa valeur 0), nous pouvons créer le nouvel enfant en ajoutant une représentation de 1 à la représentation bit du chemin d'accès au nœud A. Si nous avions déjà rencontré le nombre généré de cette manière, la feuille serait déjà présente. Cela contredit l'hypothèse initiale selon laquelle la feuille n'est pas présente.
bool seen[1001] = { false };
for each element of the original array
if the element is in the range 0..1000
seen[element] = true
find the index for the first false value in seen
Ouais - c'est plus rapide que ma solution similaire, mais utilisait une gamme d'entiers. Vous pouvez modifier la plage lorsque la matrice booléenne est «usée» de sorte que plus de valeurs puissent être ajoutées. La réinitialisation de votre matrice booléenne sera plus rapide, (memset) que ma recharge de boucle avec des valeurs incrémentées. De plus, ma conception a, comme indiqué, une faille fatale dans celle que j'utilise la première valeur de la liste sous la forme d'un drapeau "invalide", il ne doit pas être inclus dans l'analyse invalidation. Néanmoins, nous avons tous deux frappé sur l'idée de commencer à partir de 0 et de travailler ..
Il y a 2 64 64 bits d'entiers, un nombre tellement
plus de 1000 que la solution la plus simple serait de générer un
nombre aléatoire 64 bits, puis vérifiez que ce n'est pas dans la table de
nombres déjà générés. (La probabilité qu'il soit soit
infinitésimal, mais vous pourriez aussi bien être sûr.)
Puisque la plupart des générateurs de nombres aléatoires ne génèrent pas de valeurs 64 bits, vous
sont laissés avec l'écriture de votre propre ou (beaucoup plus simple), combinant le
valeurs, par exemple en générant 8 octets aléatoires, et Quant à la vérification du fait que le nombre n'est pas déjà présent, memcpy dans un
uint64_t .
std :: trouve est
juste bien pour un ou deux nouveaux nombres; Si vous devez faire beaucoup de
Recherches, trier la table et utiliser une recherche binaire serait
digne d'intérêt. Ou une sorte de table de hachage.
Mais l'insertion d'un nouvel élément dans une table triée prend une heure (n) heure, comme std :: Trouver , vous êtes donc bloqué avec O (n) pour générer dans les deux cas.
@Larsmans mais O (n) avec un très petit facteur constant et une bonne localité battent souvent O (lg n) avec un gros facteur constant et une mauvaise localité.
@James 1000 n'est pas vraiment ce petit sur un grand nombre d'opérations. LG 1000 a 10 ans, vous devez donc avoir une assez grande constante avant que O (N) ne puisse rivaliser avec O (LG N)
@Quasivers vous rappelez-vous que le O (N) ne s'applique qu'à l'insertion, pas la recherche. Insertion dans une carte nécessite une allocation, ce qui peut faire une différence vraiment très grande en ce qui concerne le facteur constant. (Et bien sûr, si la performance devient vraiment un problème, des solutions significativement meilleures sont disponibles. Mais ils sont plus compliqués et donc plus sujets à l'erreur.)
@arne est presque là. Ce dont vous avez besoin est un auto-équilibrage arbre d'intervalle , qui peut être construit dans O ( n lg n < / em>) temps.
Prenez ensuite le nœud supérieur, qui stockera un intervalle [ i , j ]. Par les propriétés d'un arbre d'intervalle, les deux i -1 et j +1 sont des candidats valides pour une nouvelle clé, sauf si i = I.e.: init prend o ( n lg n ), génère des prises O (lg n ). Les deux sont les chiffres pires cas. La plus grande chose à propos de cette approche est que le noeud supérieur conserve "de la croissance" (stocker des intervalles plus importants) et la fusion avec son successeur ou son prédécesseur, de sorte que l'arbre rétrécisse en termes d'utilisation de la mémoire et éventuellement Temps par opération décrit à O (1). Vous ne perdrez pas non plus de chiffres. Vous pouvez donc continuer à générer jusqu'à ce que vous obtenez 2 ^ 64 d'entre eux. Uint64_min ou j = uint64_max . Si les deux sont vrais, vous avez enregistré 2 ^ 64 éléments et vous ne pouvez pas générer un nouvel élément. Stocker le nouvel élément qui prend O (lg n ) le pire temps.
Agréable! Cela devrait être bien plus rapide que mon arbre, en particulier lorsque le nombre d'éléments existants augmente. +1
Vous devriez être capable d'obtenir une meilleure performance à partir d'une STD triée :: deque des gammes au lieu d'un arbre. Légèrement plus compliqué, mais une meilleure localité (plus rapide), moins de mémoire (plus rapide), pas d'équilibrage (plus rapide) et de génération après cela est O (1). Mais le concept "gamme" est une idée géniale.
Je viens de réaliser que le concept de gamme le rend également trivial de retourner n'importe quel nombre inutilisé aléatoire , sans augmenter / diminuer comme d'autres. (Ils ne seraient pas distribués de manière uniforme, et cela augmenterait considérablement l'utilisation de la mémoire jusqu'à ce que vous ayez généré un grand nombre)
Vous avez oublié à propos de STD :: ON O (N) d'Insert, alors ce n'est pas ce que vous ne comprenez que, à moins que vous ne puissiez plus générer de chiffres au début et finissez comme tout le monde.
Vous pouvez créer un nouveau tableau avec les numéros qui ne sont pas dans le tableau d'origine, puis choisissez-en un à partir de ce nouveau tableau.
¿o (1)?
Oui, O (2 ^ 64) = O (1), dans un sens trivial.
Vous devez simplement créer le tableau 1 fois et utiliser autant de fois que nécessaire, si vous supprimez le numéro à chaque fois que vous en choisissez une. et il n'y a que 1000 cartes, grandes, oui, mais seulement 1000
J'ai oublié que, je pense que les 1000 cartes sont déjà déterminées. Sécher
Cet algorithme a Vous avez maintenant une liste représentant les chiffres qui ne sont pas utilisés. Vous pouvez simplement itération sur eux pour générer de nouveaux numéros. O (n lg n) Initialisation, O (1) requête et O (n) utilisation de la mémoire. Je suppose que vous avez un type d'entier que je me référerai comme int64 et qu'il peut représenter les entiers [0, intz3_max] . .
[u, v]
[1, premier numéro - 1]
[prev numéro + 1, numéro de courant - 1]
[Dernier numéro + 1, INT64_MAX]
«Trier les chiffres» signifie O (LG N) espace temporaire à la moitié du moins (ou O (N²)). Une liste liée des intervalles prend o (n) espace. Mais en effet, l'opération génératrice prendra O (1) heure.
@Larsmans Non, car n est fixé à 1000 ... mais j'ai dit O (n LG n) temps pour le tri. J'ai peut-être un double standard ... je vais le modifier.
Initialisation: Ne triez pas la liste. Créez un nouveau tableau 1000 contenant 0..999. Itérate la liste et, si un numéro est compris dans la plage 0..999, invalendez-le dans la nouvelle matrice en remplaçant la valeur dans la nouvelle matrice avec la valeur du premier élément de la liste.
Insertion: Utilisez un index d'incrémentation sur le nouveau tableau. Si la valeur de la nouvelle matrice à cet indice n'est pas la valeur du premier élément de la liste, ajoutez-la à la liste, sinon cochez la valeur de la position suivante dans la nouvelle matrice. Lorsque le nouveau tableau est utilisé, remplissez-le en utilisant 1000..1999 et invalidez les valeurs existantes comme ci-dessus. Oui, cela se boucle sur la liste, mais cela ne doit pas être fait pour chaque insertion.
proches de O (1) jusqu'à ce que la liste soit si grande qui l'itération occasionnelle pour l'invalidation du «nouveau» nouveau réseau devient significatif. Peut-être que vous pourriez atténuer cela en utilisant un nouveau tableau qui pousse, Maybee toujours la taille de la liste?
rgds, Martin
Mettez-les tous dans une table de hachage de taille> 1000 et trouvez la cellule vide (c'est le problème de stationnement). Générer une clé pour cela. Cela fonctionnera bien sûr mieux pour une taille de table plus grande. La table n'a besoin que de 1 bits entrées.
Edit: Ceci est le principe du pigeonhole.
Cela nécessite des "tables de modulo" (ou une autre fonction "semi-inversée") pour une fonction de hachage.
Oups, je vois que je viens de réinventer la méthode de Keith Thompson.
Il me manque peut-être quelque chose, mais la plupart des autres réponses me paraissent aussi compliquées.
Trier simplement le tableau d'origine, puis commencer à compter à partir de zéro: si le nombre actuel est dans la matrice, ignorez-le, sinon vous avez votre numéro suivant. Cet algorithme est O (n), où n est le nombre de nombres nouvellement générés: les deux trient et le saut des nombres existants sont des constantes. Voici un exemple:
trop compliqué? Peut-être. Plus rapide pour les premières cartes? Absolument.
@Mooing Duck: Certainement, mais alors pourquoi le code aux exigences qui ne sont pas là? La OP parle de "nouveau numéro à chaque fois ...", il n'y a pas d'exigence de performance explicite ni une indication du nombre de numéros extraits. En pratique, il suffit de comparer chaque numéro de 64 bits non signé avec tous les éléments de la matrice est susceptible d'être suffisamment rapide à la plupart des fins.
Je code à mon interprétation de ce qu'ils veulent plus que ce qu'ils disent, depuis ce qu'ils disent n'est jamais tout ce dont ils veulent. J'ai eu une mission de devoirs une fois où nous avons dû écrire une fonction renvoyée true si un paramètre de chaîne était supérieur à 5 caractères. Une réponse qui suit des spécifications: bool isgreatfive (const-char *) {retour vrai;}
Basé sur la solution ici: Question sur tableau et numéro
Comme il y a 1000 chiffres, si nous considérons leurs restes avec 1001, au moins un reste sera manquant. Nous pouvons choisir cela comme notre numéro manquant.
Nous maintenons donc une gamme de comptes: C [1001], qui maintiendra le nombre d'entiers avec le reste R (en divisant par 1001) en C [R].
Nous maintenons également un ensemble de nombres pour lequel c [j] est 0 (par exemple en utilisant une liste liée).
Lorsque nous déplacons la fenêtre, nous décompions le nombre du premier élément (disons le reste i), c'est-à-dire c [i]. Si c [i] devient zéro, nous ajoutons i à l'ensemble des chiffres. Nous mettons à jour le tableau C avec le nouveau numéro que nous ajoutons.
Si nous avons besoin d'un numéro, nous venons de choisir un élément aléatoire à partir de l'ensemble de J pour lequel c [j] est 0.
Ceci est O (1) pour de nouveaux numéros et O (n) initialement.
Ceci est similaire à d'autres solutions mais pas tout à fait.
Que diriez-vous de quelque chose de simple comme celui-ci:
1) partitionner le tableau en chiffres égaux et inférieurs à 1000 et au-dessus
2) Si tous les chiffres correspondent à la partition inférieure, choisissez 1001 (ou un nombre supérieur à 1000) et nous avons terminé.
3) sinon nous savons qu'il doit exister un nombre compris entre 1 et 1000 qui n'existe pas dans la partition inférieure.
4) Créez un réseau d'éléments de 1 000 éléments de bools, ou un champ de bit de 1000 éléments long, ou non et initialisez le tableau à tous les 0
5) Pour chaque entier dans la partition inférieure, utilisez sa valeur sous forme d'index dans la matrice / bitfield et définissez le bool correspondant sur true (c.-à-d.: faire une sorte de radix)
6) Survolez le tableau / bitfield et choisissez toute index de valeur non définie comme solution
Cela fonctionne dans O (n) temps, ou depuis que nous avons tout lié de 1000, techniquement, il est (1), mais O (n) temps et espace en général. Il y a trois passes sur les données, qui n'est pas nécessairement l'approche la plus élégante, mais la complexité reste O (n).
Peut-être que j'ai mal compris. Chaque numéro nouvellement généré soit différent de Tous les précédents, ou supprimez-vous le premier élément à chaque fois? Dans ce cas, une solution O (1000) = O (1) peut être formulée de manière triviale.
@Larsmans: L'entier nouvellement généré a été invité à être différent de tous les précédents.
Question connexe: trouver un entier non parmi quatre milliards de ceux-ci