Entretiens d'embauche chez Google

MLD · **Inscription:** Jeu 05/Fév/2009 17:58 **Messages:** 979

@Fig
Méa culpa pour la controverse, tu as raison. :oops:

MLD · **Inscription:** Jeu 05/Fév/2009 17:58 **Messages:** 979

@Fig
Heu Heu!
Monsieur Bug est passé par ici. Dans ma tête j’avais bon, mais avec Ollivier, vous m’aviez convaincu.

Moi aussi maintenant j'ai zéro ms :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

Torp · **Inscription:** Lun 22/Nov/2004 13:05 **Messages:** 355

Bon pour la Q3 je lache l'affaire. Je tourne en rond :roll:

Fig · **Inscription:** Jeu 14/Oct/2004 19:48 **Messages:** 1139

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.

MLD · **Inscription:** Jeu 05/Fév/2009 17:58 **Messages:** 979

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:

Guillot · **Inscription:** Jeu 25/Juin/2015 16:18 **Messages:** 304

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)

Fig · **Inscription:** Jeu 14/Oct/2004 19:48 **Messages:** 1139

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:

MLD · **Inscription:** Jeu 05/Fév/2009 17:58 **Messages:** 979

@Fig
une manière un peu différente , certainement plus rapide que la première.

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

Zorro · **Inscription:** Mar 31/Mai/2016 9:06 **Messages:** 2208

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

Fig · **Inscription:** Jeu 14/Oct/2004 19:48 **Messages:** 1139

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).

Zorro · **Inscription:** Mar 31/Mai/2016 9:06 **Messages:** 2208

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:

Fig · **Inscription:** Jeu 14/Oct/2004 19:48 **Messages:** 1139

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.

Zorro · **Inscription:** Mar 31/Mai/2016 9:06 **Messages:** 2208

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

Torp · **Inscription:** Lun 22/Nov/2004 13:05 **Messages:** 355

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"

MLD · **Inscription:** Jeu 05/Fév/2009 17:58 **Messages:** 979

@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é.

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 :?:

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.

PureBasic

Entretiens d'embauche chez Google

Qui est en ligne