Re: Entretiens d'embauche chez Google
Publié : dim. 01/avr./2018 13:45
@Fig
Méa culpa pour la controverse, tu as raison.
Méa culpa pour la controverse, tu as raison.
Forums PureBasic - Français
https://www.purebasic.fr/french/
Code : Tout sélectionner
;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
Code : Tout sélectionner
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
Code : Tout sélectionner
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
comme ça ?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.
Code : Tout sélectionner
;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
haa.. j'avais pas compris ce que voulais dire "O(n)"Fig a écrit :mais pas en O(n) -simple boucle N élements traités seulement-..
Code : Tout sélectionner
;***********************************************
;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
Code : Tout sélectionner
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"