PureBasic

Forums PureBasic
Nous sommes le Sam 14/Déc/2019 18:59

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é: Dim 01/Avr/2018 13:45 
Hors ligne

Inscription: Jeu 05/Fév/2009 17:58
Messages: 934
@Fig
Méa culpa pour la controverse, tu as raison. :oops: :lol:


Dernière édition par MLD le Dim 01/Avr/2018 17:53, édité 1 fois.

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

Inscription: Jeu 05/Fév/2009 17:58
Messages: 934
@Fig
Heu Heu!
Monsieur Bug est passé par ici. Dans ma tête j’avais bon, mais avec Ollivier, vous m’aviez convaincu. 8O Moi aussi maintenant j'ai zéro ms :lol: :lol: (sauf quand il n'y a pas de paire)
Mais je suis Breton donc têtu :?
Code:
;Fig generate an array with no answer (worst case) and sort it
DisableDebugger
#Sum= 100
#Nelement=10000
Global Dim x.f(#Nelement)
For i=1 To #Nelement
    x(i)=Random(100,10)
Next i
SortArray(x(),#PB_Sort_Ascending)

;MLD CODE
; Global Dim x.F(8) ;modified by Fig
Global R.F = #SUM ;modified by Fig
i = 0:p1 = 0
Global dp = 0
Global a$
;modified by Fig
;x(1) = 1:x(2) = 3: x(3) = 5:x(4) = 7:x(5) = 8: x(6) = 10:x(7) = -1:x(8)= 12

Procedure paire(i)
Shared p1 
For z = 0 To ArraySize(x())
If x(z)<> x(i) And  x(i) + x(z) = R:p1 = x(i):p2= x(z):dp = 1 :a$ = "paire " + Str(p1) + " ; " + Str(p2):Break: EndIf
Next
EndProcedure

Chrono_MLD.q=ElapsedMilliseconds()
Repeat
  If i < ArraySize(x()) ;And p1 =0
   If dp <> 0:Break:EndIf
   Debug i
  i=i +1
EndIf
paire(i)
Until i = ArraySize(x())
If a$ <> ""
  MessageRequester("réponse",a$ + "  "+ "en" + Str(i)+ " tours " + Str(ElapsedMilliseconds()-Chrono_MLD)+" ms") ;Modified by Fig
Else
  MessageRequester("réponse"," pas de paire en "+Str(ElapsedMilliseconds()-Chrono_MLD));modified by Fig
EndIf

;TORP CODE
Idx1 = 0
Idx2 = ArraySize(x());modified by FIG
   
;modified by FIG
; Dim Tab.b(Idx2)
; For i = 0 To Idx2
;    Tab(i) = Random(30, 0)
; Next
;SortArray(Tab(), #PB_Sort_Ascending)
; For i = 1 To Idx2
;    Debug Tab(i)
; Next

   
; i=0 ;modified by FIG
; Val.b = #sum; Random(60, 0) ;modified by FIG
; Debug "valeur à trouver : " + Str(Val)
;
; Chrono_Torp.q=ElapsedMilliseconds()
; Repeat
;    i + 1
;    Som = x(Idx1) + x(Idx2) ;modified by Fig
;    If Som > val
;       Idx2 - 1
;    ElseIf Som < Val
;       Idx1 + 1
;    ElseIf  SOm = Val
;       MessageRequester("réponse",Str(x(Idx1)) + " + " + Str(x(Idx2)) + " = " + Str(Val) + " en " + Str(i) + " tours" + "en "+Str(ElapsedMilliseconds()-Chrono_Torp)+" ms"): End  ;modified by Fig
;    EndIf
; Until (Idx1 > ArraySize(x())) Or Idx2 < 0 ;modified by Fig
;
; MessageRequester("réponse","Pas de Somme en "+Str(ElapsedMilliseconds()-Chrono_Torp)+" ms") ;modified by Fig


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

Inscription: Lun 22/Nov/2004 13:05
Messages: 353
Bon pour la Q3 je lache l'affaire. Je tourne en rond :roll:


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

Inscription: Jeu 14/Oct/2004 19:48
Messages: 1121
MLD, je n'ai rien contre les gens têtus, la prochaine fois, on passera en Pv pour régler ça, c'est mieux.

Pour la question 3, il faut juste mémoriser les compléments à la somme que tu cherche, des chiffres que tu as déjà croisés.
Si quelqu'un comprends cette phrase il résout le problème. :lol:

exemple si on cherche une somme de 8:
[5,4,7,3,1,4]
Pour 5, le complément à 8 est 3 (donc si je trouve un 3 j'ai ma paire avec 5). Je mémorise pour le 3 la position 1.
Pour 4, je mémorise 8-4 = 4 pour la position 2
etc...
A chaque fois je vérifie dans ce que j'ai mémorisé si le chiffre examiné correspond.

_________________
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é: Lun 02/Avr/2018 8:50 
Hors ligne

Inscription: Jeu 05/Fév/2009 17:58
Messages: 934
Bonjour Fig
je ne sais pas si c'est la solution, mais j'ai ceci

Code:
DisableDebugger
#Sum= 8
#Nelement=10000
Global Dim x.f(#Nelement)
For i=1 To #Nelement
    x(i)=Random(100,10)
Next i

Global R.F = #SUM
i = 0:p1 = 0
Global dp = 0
Global a$
Procedure paire(i)
Shared p1 
For z = 0 To ArraySize(x())
  If x(z)<> x(i)
    If x(i) + x(z) = R Or x(i) - x(z) = R:p1 = x(i):p2= x(z):dp = 1 :a$ = "paire " + Str(p1) + " ; " + Str(p2):Break: EndIf
  EndIf 
Next
EndProcedure

Chrono_MLD.q=ElapsedMilliseconds()
Repeat
  If i < ArraySize(x())
   If dp <> 0:Break:EndIf
   Debug i
  i=i +1
EndIf
paire(i)
Until i = ArraySize(x())
If a$ <> ""
  MessageRequester("réponse",a$ + "  "+ "en" + Str(i)+ " tours " + Str(ElapsedMilliseconds()-Chrono_MLD)+" ms") ;Modified by Fig
Else
  MessageRequester("réponse"," pas de paire en "+Str(ElapsedMilliseconds()-Chrono_MLD)+" ms");modified by Fig
EndIf

Comme auparavant je me base pour la vitesse sur les ruptures de boucle. :wink:


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

Inscription: Jeu 25/Juin/2015 16:18
Messages: 270
très intéressant ces problèmes
si t'en a d'autres poste les
même si on à pas envie ou pas le temps de se creuser la tête, c'est tres instructif de voir la solution

PS: pour la question 3, la plage des valeurs doit être limitée pour que le tableaux puissent tenir en mémoire (google aurait du le préciser dans l'ennoncé, sans quoi certain ne chercheront pas dans cette direction)


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

Inscription: Jeu 14/Oct/2004 19:48
Messages: 1121
Guillot effectivement mon enoncé manque de précision c'est à cause du passage d'un format à l'autre (interview => question fermée ici)
En effet, ce genre de problème se résout en dialoguant avec l'examinateur, la démarche est aussi importante que la solution pour eux.
La question originelle manque de quasiment toutes les précisions nécessaires pour la résoudre au départ.
Donc si on utilise un tableau ou une table de hachage, effectivement, ça prendra de la mémoire. Sauf qu'il est toujours possible de traiter cette longue série de chiffre par batch en mémoire vive... Après, la mémoire disque peut aussi se saturer, bien sûr... :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é: Jeu 05/Avr/2018 14:55 
Hors ligne

Inscription: Jeu 05/Fév/2009 17:58
Messages: 934
@Fig
une manière un peu différente , certainement plus rapide que la première. :D
Code:
DisableDebugger
#Sum= 101
Global max = 100
#Nelement=100000
Global Dim x.f(#Nelement)
For ii=1 To #Nelement
    x(ii)=Random(max,10)
Next ii

Global R.F = #SUM
Global i = 0
p1 = 0
Global a$

Declare paire()
Chrono_MLD.q=ElapsedMilliseconds()
paire()
Procedure paire()
  Static i
  If R > 0 And R < max*2
Repeat
For z = 0 To ArraySize(x())
  If x(z)<> x(i)
    If x(i) + x(z) = R Or x(i) - x(z) = R:p1 = x(i):p2= x(z):a$ = "paire " + Str(p1) + " ; " + Str(p2):ProcedureReturn #NUL: EndIf
  EndIf 
Next
i= i+ 1
Until i = ArraySize(x())
EndIf
EndProcedure

If a$ <> ""
  MessageRequester("réponse",a$ + "  "+ "en " + Str(i)+ " tours " + Str(ElapsedMilliseconds()-Chrono_MLD)+" ms") ;Modified by Fig
Else
  MessageRequester("réponse"," pas de paire en "+Str(ElapsedMilliseconds()-Chrono_MLD)+" ms");modified by Fig
EndIf
End



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

Inscription: Mar 31/Mai/2016 9:06
Messages: 2113
Fig a écrit:
Il reste la question 3, mais c'est la plus dur...
Pour rappel, soit un tableau rempli de nombres positifs non triés, trouver la paire qui correspond à une somme donnée en O(n)...
Bon courage. :wink:


comme ça ?

Code:
;soit un tableau rempli de nombres positifs non triés,

dim tab(1000)
for i=1 to 999
      Tab(i)=i      
Next i
RandomizeArray(Tab() )

; pour verifier le contenu du tableau activez ceci :
; For i= 1 to 999
; debug Tab(i)
; Next i



Somme_a_trouver=13

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

For x=1 to 999
      A=Tab(x)
      For y=1 to 999
            B=Tab(y)
            If ( y<>X) And (B+A)=Somme_a_trouver and A<>0 and B<>0
            Debug " la paire : "+"["+str(A)+";"+str(B)+"]"+" forme la somme a trouver ="+str(Somme_a_trouver)
            Endif
      Next y
Next x


_________________
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é: Jeu 05/Avr/2018 18:48 
Hors ligne
Avatar de l’utilisateur

Inscription: Jeu 14/Oct/2004 19:48
Messages: 1121
Ca fonctionne, Dobro, comme le code de MLD, en O(n²) -double boucles imbriquées, donc N*N élement à traiter- mais pas en O(n) -simple boucle N élements traités seulement-.
Je laisse encore quelques jours, ensuite, je donne une réponse possible. (et une nouvelle question).

_________________
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é: Jeu 05/Avr/2018 19:31 
Hors ligne
Avatar de l’utilisateur

Inscription: Mar 31/Mai/2016 9:06
Messages: 2113
Fig a écrit:
mais pas en O(n) -simple boucle N élements traités seulement-..

haa.. j'avais pas compris ce que voulais dire "O(n)" :lol:

_________________
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é: Jeu 05/Avr/2018 19:35 
Hors ligne
Avatar de l’utilisateur

Inscription: Jeu 14/Oct/2004 19:48
Messages: 1121
Pas de problème, j'ai mis une rapide (vague) explication en page 1 du sujet sinon.
Je vois que ta connexion internet fonctionne à nouveau, content de ton retour.

_________________
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 8:56 
Hors ligne
Avatar de l’utilisateur

Inscription: Mar 31/Mai/2016 9:06
Messages: 2113
oui ça marche maintenant , l'internet est devenu un truc indispensable :)


bon voici un deuxième jet ,
le principe , je transforme d'abord le tableau en une string (qui est en fait un tableau a une dimension )
ensuite je prends le chiffre a trouver , et je soustrais chacun des éléments du tableau un par un a ce chiffre a trouver.... si cet element est plus petit que le chiffre a trouver.. bien sur... j’économise ainsi du temps de recherche

a chaque fois ça me donne un résultat ,
je regarde simplement si ce résultat est présent dans la String avec FindString()

de meme , je ne prends pas en compte le doublon représenté par le résultat et la somme a trouver , c'est pourquoi il n'affichera pas [4;4]
puisque mon tableau de toute façon ne contient qu'un seul "4" ... :)

exemple le chiffre a trouver est 8
je prends le premier element du tableau (mettons 3) , je regarde s'il est plus petit que 8
si c'est le cas , je soustrais l'element 3 de 8 ce qui me donne un resultat (5)... c'est ce resultat que je recherche dans tout le tableau (la string)
si je le trouve , c'est le complement qu'il faut afficher avec l'element 3
et j'affiche donc "[ element (3) ;resultat(5) ] ======> "forme la somme a trouver = 8"



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,

dim tab(1000)
for i=1 to 999
      Tab(i)=i      
Next i
RandomizeArray(Tab() )
; mise en string du tableau pour recherche futur
for i=1 to 999
      chaine.s= chaine.s+str(Tab(i))+","   
Next i

; pour verifier le contenu du tableau activez ceci :
; For i= 1 to 999
; debug Tab(i)
; Next i
; ou ça :
;debug chaine.s


Somme_a_trouver=8

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

For x=1 to 999  ;  <<<<<<<<<<<<<<<<<  une seule boucle !!
      A=Tab(x)
      If A<Somme_a_trouver
            temp=(Somme_a_trouver-A)
            If  Mod(temp,1)=0 and A<>int(temp)
                  If findstring(chaine.s,str(temp))   
                        Debug " la paire : "+"["+str(A)+";"+str(Temp)+"]"+" forme la somme a trouver ="+str(Somme_a_trouver)
                  Endif
            Endif
      Endif
Next x







_________________
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 10:05 
Hors ligne
Avatar de l’utilisateur

Inscription: Lun 22/Nov/2004 13:05
Messages: 353
Bon je m'y suis remis car ça me turlupinais c't histoire (@Fig sans ta mise à plat du problème je n'aurais pas pigé le truc :wink:)

Code:
Idx = 16

Dim Tab.b(Idx)
For i = 0 To Idx
   Tab(i) = Random(30, 0)
Next

For i = 0 To Idx
   Debug Tab(i)
Next

Val.b = Random(60, 0)
Debug "valeur à trouver : " + Str(Val)

;--------------------------------
NewList CompSom.b()

For i = 0 To ArraySize(Tab())
   AddElement(CompSom())
   CompSom() = Val - Tab(i)
   ForEach CompSom()
      If Tab(i) = CompSom() And i <> ListIndex(CompSom())
         Debug Str(Tab(i)) + " + " + Str(Tab(ListIndex(CompSom()))) + " = " + Str(Val) + " en " + Str(i) + " tours"
         End
      EndIf 
   Next
Next i

Debug "Pas de Somme en " + Str(i) + " tours"


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

Inscription: Jeu 05/Fév/2009 17:58
Messages: 934
@Zorro
Bonjour, content de ton retour je m'était inquiété de ton absence de manière humoristique, cela n'a pas plus! Et mon message a été effacé. 8O
Si tu répond pour le trois, le tableau doit être remplis de manière aléatoire.
Heu, tu ne tricherait pas un tantinet? Car il me semble que la fonction "findstring" comporte en interne une boucle :?: :wink: :lol:
En fait tu as deux boucles dont une cachée. Si tu met un chrono sur ton algo tu verra qu'il n'est en fait pas très rapide.
Mais tu n'est pas obligé de montrer toutes les paires possible. FIg ne le demande pas. Donc tu peu sortir de la boucle au premier résultat.


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 9 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