PureBasic

Forums PureBasic
Nous sommes le Dim 08/Déc/2019 1:45

Heures au format UTC + 1 heure




Poster un nouveau sujet Répondre au sujet  [ 98 messages ]  Aller à la page Précédente  1, 2, 3, 4, 5, 6, 7  Suivante
Auteur Message
 Sujet du message: Re: Entretiens d'embauche chez Google
MessagePosté: Ven 06/Avr/2018 10:36 
Hors ligne
Avatar de l’utilisateur

Inscription: Mar 31/Mai/2016 9:06
Messages: 2111
MLD a écrit:
Heu, tu ne tricherait pas un tantinet? Car il me semble que la fonction "findstring" comporte en interne une boucle :?: :wink: :lol:


le code de Torp aussi alors... il reprends exactement mon principe
mais en utilisant une list en lieu et place de ma String .... et en utilisant Foreach-Next


quoiqu'il en soit a partir du moment ou tu as des données dans un tableau, une liste ou des data
et que tu dois faire une comparaison , tu es obligatoirement obligé de faire 2 boucles !!

une pour égrener les élément de ton tableau pour la comparaison
et une autre pour vérifier si ta comparaison se vérifie

la seule exception possible a mon avis c'est l'emploi de la récursivité !

ou donc, la meme procedure d'appel de façon recursive pour a la fois egréner l'element a observer
et verifier le resultat avec les autres elements du tableau ....

il n'y a pas a tortiller ... je ne suis pas ferru de Math
mais je ne pense pas qu'il existe une formule magique qui puisse eviter les 2 boucles dans l'absolu

je dis dans l'absolu , car meme en recursif, il s'agit bien de 2 boucles , meme si c'est la meme qui est utilisée
elle l'est au minimum 2 fois ... :)

_________________
Image
Image
Site: http://michel.dobro.free.fr/
Devise :"dis moi ce dont tu as besoin, je t'expliquerai comment t'en passer"


Dernière édition par Zorro le Ven 06/Avr/2018 10:59, édité 2 fois.

Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Entretiens d'embauche chez Google
MessagePosté: Ven 06/Avr/2018 10:53 
Hors ligne
Avatar de l’utilisateur

Inscription: Lun 22/Nov/2004 13:05
Messages: 353
Effectivement j'ai aussi 2 boucles... "Au compte est Bon" je dirais : Pas mieux !


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Entretiens d'embauche chez Google
MessagePosté: Ven 06/Avr/2018 11:15 
Hors ligne
Avatar de l’utilisateur

Inscription: Mar 31/Mai/2016 9:06
Messages: 2111
autre variante , SANS les 2 boucles !! :)

mais avec un tableau de data aléatoire, contrairement a mon exemple precedent
ou TOUT les chiffres entre 0 et X etaient present de façon mélangés
la on peut avoir plusieur fois les meme chiffres dans le tableau ....

lancer le code plusieurs fois , car le fait aléatoire peut sortir des resultats differents ;)

Code:
;***********************************************
;Titre  :*bidouille
;Auteur  : Zorro
;Date  :06/04/2018
;Heure  :09:51:20
;Version Purebasic :  PureBasic 5.62 (Windows - x86)
;Version de l'editeur :EPB V2.68
; Libairies necessaire : Aucune
;***********************************************

;soit un tableau rempli de nombres positifs non triés,
debut:
dim tab(1000)
for i=1 to ArraySize(tab())
      Tab(i)=random(999,1)     
Next i


Somme_a_trouver=8

;trouver la paire qui correspond à une somme donnée en O(n)...
; on recherche

For x=1 to ArraySize(tab())  ;  <<<<<<<<<<<<<<<<<  une seule boucle !!
      A=Tab(x)
      If A<Somme_a_trouver ; on trouve un candidat potentiel
            If Flag=0
                  Flag=1 ; on active le flag
                  mem_A=A ; on memorise le canditdat
            Else
                  if abs(Somme_a_trouver-mem_A)=A ; on cherche le complement de notre candidat  , s'il correspond on affiche !
                        Debug " la paire : "+"["+str(A)+";"+str(mem_A)+"]"+" forme la somme a trouver ="+str(Somme_a_trouver)
                        Flag=0 ; on remet le flag a zero , pour voir s'il y en a d'autre avant la fin du scan du tableau
                        Flag2=1
                  Endif
            Endif   
      Endif
Next x

If Flag2=0
Debug "pas trouvé de candidat dans le tableau je relance le prg "
goto debut
Endif


_________________
Image
Image
Site: http://michel.dobro.free.fr/
Devise :"dis moi ce dont tu as besoin, je t'expliquerai comment t'en passer"


Dernière édition par Zorro le Ven 06/Avr/2018 11:28, édité 1 fois.

Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Entretiens d'embauche chez Google
MessagePosté: Ven 06/Avr/2018 11:28 
Hors ligne
Avatar de l’utilisateur

Inscription: Lun 22/Nov/2004 13:05
Messages: 353
Bravo je pense que t'as décroché le super pompon ! :D


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Entretiens d'embauche chez Google
MessagePosté: Ven 06/Avr/2018 12:52 
Hors ligne

Inscription: Jeu 05/Fév/2009 17:58
Messages: 934
@ Zorro
On verra ce que propose Fig :?:
Mais pour moi goto est une sorte de spaghetti qui fait une boucle :lol: Ce qui est dailleur admis en assembleur (Jump) :wink:
Je pense comme toi qu'il faut absolument deux boucles, mais va savoir :!: :lol:
Je ne suis pas sur que notre demande d'embauche chez Gogol soit valide :roll: :mrgreen:
@ Torp pour ton embauche tu as eu un piston :wink: :mrgreen:


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Entretiens d'embauche chez Google
MessagePosté: Ven 06/Avr/2018 13:22 
Hors ligne
Avatar de l’utilisateur

Inscription: Mar 31/Mai/2016 9:06
Messages: 2111
MLD a écrit:
@ Zorro
On verra ce que propose Fig :?:
Mais pour moi goto est une sorte de spaghetti qui fait une boucle :lol:

oui tu as raison , mais dans mon code le goto ne sert qu'a relancer automatiquement le prg
si aucune paire n'est trouvé dans le tableau :)
je l'ai ajouté pour ne pas avoir a recompiler si choux blanc ...


MLD a écrit:
Je ne suis pas sur que notre demande d'embauche chez Gogol soit valide :roll: :mrgreen:


quoiqu'il en soit chez Google comme ailleurs, il y a des cracks , et aussi des quiches.... :roll:
donc au final, on s'en fout hein ? :lol:

_________________
Image
Image
Site: http://michel.dobro.free.fr/
Devise :"dis moi ce dont tu as besoin, je t'expliquerai comment t'en passer"


Dernière édition par Zorro le Ven 06/Avr/2018 13:30, édité 1 fois.

Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Entretiens d'embauche chez Google
MessagePosté: Ven 06/Avr/2018 13:30 
Hors ligne

Inscription: Jeu 05/Fév/2009 17:58
Messages: 934
@Zorro
HI!HI! :lol: :lol:
Tous ceci fait quand même avancé le chmimilibilic. :lol:
et permet au programmeurs débutant de voir qu'un problème donné a XX solutions :wink:


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Entretiens d'embauche chez Google
MessagePosté: Ven 06/Avr/2018 15:19 
Hors ligne
Avatar de l’utilisateur

Inscription: Jeu 14/Oct/2004 19:48
Messages: 1121
A tous, la solution implique une seule boucle, on passe en revu chaque élément une seule et unique fois.
Findstring, comme il a été dit plus haut, cache une boucle. Ce n'est donc pas une solution attendue, quoiqu'elle soit valable bien entendue.

Dobro, tu es extrêmement proche de la solution. Le principe est bon, mais tu stocke un seul candidat possible, le premier et tu te focalise que sur celui-ci.
Du coup, ça ne fonctionne pas vraiment, voici un cas qui ne fonctionne pas par exemple. Ici la paire 2;6 (élement 3 et 4 du tableau) font 8 mais n'est pas trouvée.
Code:
;***********************************************
;Titre  :*bidouille
;Auteur  : Zorro
;Date  :06/04/2018
;Heure  :09:51:20
;Version Purebasic :  PureBasic 5.62 (Windows - x86)
;Version de l'editeur :EPB V2.68
; Libairies necessaire : Aucune
;***********************************************

;soit un tableau rempli de nombres positifs non triés,
debut:
Dim tab(4)
; For i=1 To ArraySize(tab())
;       Tab(i)=Random(999,1)     
; Next i
tab(1)=7
tab(2)=3
tab(3)=2
tab(4)=6

Somme_a_trouver=8

;trouver la paire qui correspond à une somme donnée en O(n)...
; on recherche

For x=1 To ArraySize(tab())  ;  <<<<<<<<<<<<<<<<<  une seule boucle !!
      A=Tab(x)
      If A<Somme_a_trouver ; on trouve un candidat potentiel
            If Flag=0
                  Flag=1 ; on active le flag
                  mem_A=A; on memorise le canditdat
            Else
                  If Abs(Somme_a_trouver-mem_A)=A ; on cherche le complement de notre candidat  , s'il correspond on affiche !
                        Debug " la paire : "+"["+Str(A)+";"+Str(mem_A)+"]"+" forme la somme a trouver ="+Str(Somme_a_trouver)
                        Flag=0 ; on remet le flag a zero , pour voir s'il y en a d'autre avant la fin du scan du tableau
                        Flag2=1
                  EndIf
            EndIf   
      EndIf
Next x

If Flag2=0
    Debug "pas trouvé de candidat dans le tableau je relance le prg "
    End
;Goto debut
EndIf

Je peux donner un nouvel indice.Surlignez pour les faire apparaître si vous le souhaitez.
(Il faut utiliser une structure de donnée particulière pour stocker TOUS les compléments et vérifier à chaque fois si on a déja vu sa paire...)

deuxième indice:
La structure en question est une table de hachage (avec comme clé le chiffre) ou un tableau

_________________
Il y a deux méthodes pour écrire des programmes sans erreurs. Mais il n’y a que la troisième qui marche.
Version de PB : 5.45LTS - 32 bits


Dernière édition par Fig le Ven 06/Avr/2018 17:14, édité 1 fois.

Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Entretiens d'embauche chez Google
MessagePosté: Ven 06/Avr/2018 16:53 
Hors ligne

Inscription: Jeu 05/Fév/2009 17:58
Messages: 934
@ Fig
Je voudrais être sur d'une choses
Le tableau d''entrée des données ne comporte qu'une seule dimension (comme dans ton exemple), ou l'on peu utiliser un tableau a deux dimensions?


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Entretiens d'embauche chez Google
MessagePosté: Ven 06/Avr/2018 17:06 
Hors ligne
Avatar de l’utilisateur

Inscription: Jeu 14/Oct/2004 19:48
Messages: 1121
Tu fais ta soupe comme tu veux, j'attend une réponse en O(n), il n'y a pas qu'une manière de faire je suppose...

_________________
Il y a deux méthodes pour écrire des programmes sans erreurs. Mais il n’y a que la troisième qui marche.
Version de PB : 5.45LTS - 32 bits


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Entretiens d'embauche chez Google
MessagePosté: Ven 06/Avr/2018 17:57 
Hors ligne

Inscription: Jeu 05/Fév/2009 17:58
Messages: 934
@ Fig
je verrais demain si Zorro ou Torp ne me grille pas :roll: :lol:


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Entretiens d'embauche chez Google
MessagePosté: Ven 06/Avr/2018 18:07 
Hors ligne
Avatar de l’utilisateur

Inscription: Mar 31/Mai/2016 9:06
Messages: 2111
et comme ça ?

Recursif Power !! :)

Principe de fonctionnement
on prends le premier element de la liste , puis dans la procedure recursive, on le compare a tout les element de la liste ....
ensuite on recommence avec la boucle For-next , avec le deuxieme elements de la liste qu'on compare avec tout les elements de la liste
(y compris lui meme , mais ça doit pouvoir s'eviter avec une memoire de position du pointeur )
etc ...


Code:
;***********************************************
;Titre  :*bidouille
;Auteur  : Zorro
;Date  :06/04/2018
;Heure  :09:51:20
;Version Purebasic :  PureBasic 5.62 (Windows - x86)
;Version de l'editeur :EPB V2.68
; Libairies necessaire : Aucune
;***********************************************
Declare recherche(c,A)
;soit un tableau rempli de nombres positifs non triés,

Global Dim tab(10000)
For i=1 To ArraySize(tab())
      Tab(i)=Random(50,1)     
Next i


; Global Dim tab(4)
; tab(1)=7
; tab(2)=3
; tab(3)=2
; tab(4)=6

Global Somme_a_trouver=8

;trouver la paire qui correspond à une somme donnée en O(n)...
; on recherche
;calldebugger
For x=1 To ArraySize(tab())  ;  <<<<<<<<<<<<<<<<<  une seule boucle !!
      A=Tab(x)
      recherche(tab(x),A)
Next x
debug "fin"

Procedure recherche(c,A)
      ; recursif Power by Zorro
   
      static x
      x=x+1
      If x>ArraySize(tab())
            x=1
            ProcedureReturn
      Endif
      A=Tab(x)
      If c+A=Somme_a_trouver
            Debug " la paire : "+"["+Str(A)+";"+Str(c)+"]"+" forme la somme a trouver ="+Str(Somme_a_trouver)
               ProcedureReturn
      Endif
      
      If A<Somme_a_trouver                   
            c=recherche(c,A)               
      Endif
EndProcedure

_________________
Image
Image
Site: http://michel.dobro.free.fr/
Devise :"dis moi ce dont tu as besoin, je t'expliquerai comment t'en passer"


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Entretiens d'embauche chez Google
MessagePosté: Ven 06/Avr/2018 20:15 
Hors ligne
Avatar de l’utilisateur

Inscription: Jeu 14/Oct/2004 19:48
Messages: 1121
C'est une manière originale et créative de refaire une boucle interne supplémentaire.
Si on regarde de prés, pour trouver une paire qui se trouverait à la fin du tableau, tu passe en revu NxN éléments donc toujours O(n²).

Bon, je donnerai la réponse demain après midi.
Bonne soirée :wink:

_________________
Il y a deux méthodes pour écrire des programmes sans erreurs. Mais il n’y a que la troisième qui marche.
Version de PB : 5.45LTS - 32 bits


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Entretiens d'embauche chez Google
MessagePosté: Ven 06/Avr/2018 20:51 
Hors ligne
Avatar de l’utilisateur

Inscription: Mar 31/Mai/2016 9:06
Messages: 2111
Fig a écrit:
C'est une manière originale et créative de refaire une boucle interne supplémentaire.


je suis certain de te prouver que ta solution aura aussi une seconde boucle cachée ...

pour une raison simple , le fait de faire une comparaison de 2 éléments d'une liste de données
oblige a la gestion de 2 pointeurs
le pointeur 1 qui lit les éléments du debut a la fin
le pointeur 2 qui regarde chaque éléments de la liste pour trouver le complément de l’élément pointé par le pointeur 1

donc tu gères 2 pointeurs et leur avancés respective dans la liste
pour ça on utilise 2 boucles, ou bien une astuce pour éviter le trop voyant For-Next ; ForEach-Next ou autre While Wend
et l'astuce , peut etre la récursivité comme je l'ai fait , ou bien l'emploi de 2 variables qui retiennent la position de chaque pointeur dans la liste
mais il te faudra utiliser des sauts a la place de boucles....

franchement, je ne vois pas d'autre solution , meme en utilisant une structure , ça ne changera pas qu'il te faudra 2 pointeurs dans ta liste
et de les gerer ...

on peut aussi envisager de copier la liste 2 fois ...

la liste 1 a mettre au dessus
la liste 2 copie de la 1 a mettre dessous

puis de d'additionner les elements un par un pour obtenir le chiffre a chercher
si rien trouvé , on decale la liste 2 d'un cran, et on recommence

tant que la liste du bas n'a pas fait un tour ...

c'est une autre façon de comparer les elements d'une liste entre eux ...
mais ça reviens quand meme a faire deux boucles et a gerer un pointeur
le second pointeur etant lui , simulé par le decalage de la liste inferieur
decalage qui utilisera aussi une boucle...

_________________
Image
Image
Site: http://michel.dobro.free.fr/
Devise :"dis moi ce dont tu as besoin, je t'expliquerai comment t'en passer"


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Entretiens d'embauche chez Google
MessagePosté: Ven 06/Avr/2018 22:39 
Hors ligne
Avatar de l’utilisateur

Inscription: Jeu 14/Oct/2004 19:48
Messages: 1121
Quand on suit un pointeur, la réponse est en O(1) cad en temps constant. Tu peux suivre presque autant de pointeur que tu veux pour chaque élement, ça ne donnera qu'une réponse en O(n).
Par contre si pour chaque élement tu passe en revu tout les autres élement ça reste une réponse en O(n²)

De toute façon, si tu as un doute là dessus, on pourra chronométrer on aura le même type de réponse qu'entre les deux code de MLD et Torp plus haut, exponentielle pour l'un et linéaire pour l'autre, la différence de chroni étant exponentielle plus il y aura d'élements dans la liste.

_________________
Il y a deux méthodes pour écrire des programmes sans erreurs. Mais il n’y a que la troisième qui marche.
Version de PB : 5.45LTS - 32 bits


Haut
 Profil  
Répondre en citant le message  
Afficher les messages postés depuis:  Trier par  
Poster un nouveau sujet Répondre au sujet  [ 98 messages ]  Aller à la page Précédente  1, 2, 3, 4, 5, 6, 7  Suivante

Heures au format UTC + 1 heure


Qui est en ligne

Utilisateurs parcourant ce forum: Aucun utilisateur enregistré et 2 invités


Vous ne pouvez pas poster de nouveaux sujets
Vous ne pouvez pas répondre aux sujets
Vous ne pouvez pas éditer vos messages
Vous ne pouvez pas supprimer vos messages

Rechercher:
Aller à:  

 


Powered by phpBB © 2008 phpBB Group | Traduction par: phpBB-fr.com
subSilver+ theme by Canver Software, sponsor Sanal Modifiye