Entretiens d'embauche chez Google
Re: Entretiens d'embauche chez Google
@Fig
Oui ont peu le faire avec une seule boucle, et un index qui part du début du tableau et un autre de la fin.
Dans ce cas si plusieurs paires sont possible, ce n'est pas forcément la première paire la plus proche du début de tableau qui sera retenu pour le résulta ?
Oui ont peu le faire avec une seule boucle, et un index qui part du début du tableau et un autre de la fin.
Dans ce cas si plusieurs paires sont possible, ce n'est pas forcément la première paire la plus proche du début de tableau qui sera retenu pour le résulta ?
Re: Entretiens d'embauche chez Google
L’énoncé ne précise pas que la paire doit être la première rencontrée...
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 : 6.00LTS - 64 bits
Version de PB : 6.00LTS - 64 bits
Re: Entretiens d'embauche chez Google
Me suis grillé quelques neurones, mais je crois avoir la question 2 O(n)... ou pas. Je n'ai fait aucun test de rapidité par rapport à la version force brute.
Pour la Q3, je coince...
Code : Tout sélectionner
Idx1 = 0
Idx2 = 16
Dim Tab.b(Idx2)
For i = 0 To Idx2
Tab(i) = Random(30, 0)
Next
SortArray(Tab(), #PB_Sort_Ascending)
For i = 0 To Idx2
Debug Tab(i)
Next
Val.b = Random(60, 0)
Debug "valeur à trouver : " + Str(Val)
Repeat
i + 1
Som = Tab(Idx1) + Tab(Idx2)
If Som > val
Idx2 - 1
ElseIf Som < Val
Idx1 + 1
ElseIf SOm = Val
Debug Str(Tab(Idx1)) + " + " + Str(Tab(Idx2)) + " = " + Str(Val) + " en " + Str(i) + " tours": End
EndIf
Until (Idx1 > ArraySize(Tab())) Or Idx2 < 0
Debug "Pas de Somme en " + Str(i) + " tours"
Re: Entretiens d'embauche chez Google
La Q3, j'étais dessus et j'ai posté un code, mais :
1) Bool() doit contenir une égalité et non pas 2 arguments qui seraient vérifiés égaux ou inégaux donc Syntax error
2) Je n'ai pas mis d'explication alors que c'est récursif donc pas un code source très pédagogique naturellement.
3) J'ai fait un hors-sujet en augmentant le nombre de termes à x au lieu de ne rester qu'à 2 termes. Note 1 terme = impossible.
4) C'est de la force brute, donc aucune optimisation arithmétique.
5) La récursivité peut être quelque chose de lent si c'est mal géré. Or je n'ai rien vérifié.
6) Je n'ai pas pu me poser sur un ordi donc out un code plus sympa de ma part pour ce week-end.
Autrement dit, la Q3, il y a encore de quoi faire! C'est d'ailleurs entre la Q2 et la Q3 qu'on découvre l'heuristique. C'est-à-dire la stratégie pour compter le plus vite possible et le plus efficacement possible un traitement de données. L'étalon étant la force brute. Ça équivaut à tout tester de A à Z sans réfléchir à un rangement initial, ou bien un ordre, qui optimiserait les tests. La force brute a le défaut d'être très limitée en vitesse de test.
1) Bool() doit contenir une égalité et non pas 2 arguments qui seraient vérifiés égaux ou inégaux donc Syntax error
2) Je n'ai pas mis d'explication alors que c'est récursif donc pas un code source très pédagogique naturellement.
3) J'ai fait un hors-sujet en augmentant le nombre de termes à x au lieu de ne rester qu'à 2 termes. Note 1 terme = impossible.
4) C'est de la force brute, donc aucune optimisation arithmétique.
5) La récursivité peut être quelque chose de lent si c'est mal géré. Or je n'ai rien vérifié.
6) Je n'ai pas pu me poser sur un ordi donc out un code plus sympa de ma part pour ce week-end.
Autrement dit, la Q3, il y a encore de quoi faire! C'est d'ailleurs entre la Q2 et la Q3 qu'on découvre l'heuristique. C'est-à-dire la stratégie pour compter le plus vite possible et le plus efficacement possible un traitement de données. L'étalon étant la force brute. Ça équivaut à tout tester de A à Z sans réfléchir à un rangement initial, ou bien un ordre, qui optimiserait les tests. La force brute a le défaut d'être très limitée en vitesse de test.
Re: Entretiens d'embauche chez Google
Torp, tu as bien fait de te griller quelques neurones car c'est effectivement la solution attendue
Ta condition de sortie:
peut se résumer à ça, en fait:
Si les pointeurs se croisent, on a déjà tout vérifié...
Ollivier tu as mon respect, coder avec la correction orthographique sur un tel portable, sans pouvoir lancer le code, c'est c*uillu !
Ta condition de sortie:
Code : Tout sélectionner
Until (Idx1 > ArraySize(Tab())) Or Idx2 < 0
Code : Tout sélectionner
Until Idx1=Idx2
Ollivier tu as mon respect, coder avec la correction orthographique sur un tel portable, sans pouvoir lancer le code, c'est c*uillu !
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 : 6.00LTS - 64 bits
Version de PB : 6.00LTS - 64 bits
Re: Entretiens d'embauche chez Google
J'aime la langue, sur ce point, et au sens propre, bien que la mienne, au sens propre, soit classée Seveso, en général, et au sens figuré.
Ainsi se sublime ton respect à mon égard, plus que les préjugés à mon encontre, tant, que je rencontre, car le seul outil est ma mémoire, et sa manière exceptionnellement première, d'être dernière...
Qu'est-ce que j'aimerais m'amuser, mais l'humanité s'amuse de se briser... Qu'est-ce que j'aimerais vous aider, vous, qui, dans l'exception offrez confiance contre lecture.
Et la beauté d'un sujet, parti des limbes aux sordides artifices, que vos idées joviales si intelligemment, à tout perdre, blanchissent...
Mon temps ne m'appartient pas et plus encore m'enlise, parce que tant, qui n'écrivent sur la feuille, comme les aïeux, leurs yeux s'abimaient, à graver ce qu'ils disent.
Ainsi se sublime ton respect à mon égard, plus que les préjugés à mon encontre, tant, que je rencontre, car le seul outil est ma mémoire, et sa manière exceptionnellement première, d'être dernière...
Qu'est-ce que j'aimerais m'amuser, mais l'humanité s'amuse de se briser... Qu'est-ce que j'aimerais vous aider, vous, qui, dans l'exception offrez confiance contre lecture.
Et la beauté d'un sujet, parti des limbes aux sordides artifices, que vos idées joviales si intelligemment, à tout perdre, blanchissent...
Mon temps ne m'appartient pas et plus encore m'enlise, parce que tant, qui n'écrivent sur la feuille, comme les aïeux, leurs yeux s'abimaient, à graver ce qu'ils disent.
Re: Entretiens d'embauche chez Google
@Fig
Avant que Torp ne me grille, j’étais la dessus
ferai je partie du personnel de Gogol
Avant que Torp ne me grille, j’étais la dessus
Code : Tout sélectionner
Global Dim x.F(8)
Global R.F = 17:I = 0:i = 0:p1=0
Global a$
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)
For z = 1 To ArraySize(x())
If x(z)<> x(i) And x(i) + x(z) = R:p1 = x(i):p2= x(z): a$ = "paire " + Str(p1) + " ; " + Str(p2):Break: EndIf
Next
EndProcedure
Repeat
If i < ArraySize(x()) And p1 =0
If p1<> 0:Break:EndIf
i=i +1
EndIf
paire(i)
Until i = ArraySize(x())
If a$ <> ""
Debug a$
Else
Debug " pas de paire"
EndIf
Re: Entretiens d'embauche chez Google
MLD ta solution est bonne aussi mais en O(n²), à mon grand regret, celle de Torp est meilleur du coup, vu qu'a google France on n'a pas de la place pour tout le monde...
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.
J'ai encore d'autres petits problèmes comme ça, pour ceux qui aiment.
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.
J'ai encore d'autres petits problèmes comme ça, pour ceux qui aiment.
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 : 6.00LTS - 64 bits
Version de PB : 6.00LTS - 64 bits
Re: Entretiens d'embauche chez Google
@Fig
je ne suis pas sure que je met plus de temps que Torp, car je sort trés vite des boucles. Comme c'est toi l'arbitre c'est a toi de mesurer les temps de calcul
Je ne contesterait pas l'arbitrage.
Pour le 3 j'utilise le même algo. Avec une légère modif l'ons peut voir toutes les paires possible. (Sauf la mienne )
je ne suis pas sure que je met plus de temps que Torp, car je sort trés vite des boucles. Comme c'est toi l'arbitre c'est a toi de mesurer les temps de calcul
Je ne contesterait pas l'arbitrage.
Pour le 3 j'utilise le même algo. Avec une légère modif l'ons peut voir toutes les paires possible. (Sauf la mienne )
Re: Entretiens d'embauche chez Google
En fait, même si le code de Torp était écrit dans le langage le plus lent possible et le tiens en assembleur et hyper optimisé, avec un nombre important de chiffres à traiter dans le tableau, ton code serait toujours plus lent.
Ca ne remet pas en cause ta qualité comme programmeur, rassure toi.
Ca ne remet pas en cause ta qualité comme programmeur, rassure toi.
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 : 6.00LTS - 64 bits
Version de PB : 6.00LTS - 64 bits
Re: Entretiens d'embauche chez Google
@Fig
prouve le
prouve le
Re: Entretiens d'embauche chez Google
Démonstration 1:
Admettons que tu aies 1000 elements et pas de pairs dedans (pire cas) Ton code passe en revu 1000x1000 elements, celui de Torp 1000 seulement.
Si tu as 10 000 elements le tiens 10 000x10 000 et celui de Torp 10 000 seulement etc...
Démonstration 2:
Code : Tout sélectionner
;Fig generate an array with no answer (worst case) and sort it
DisableDebugger
#Sum=8
#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 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)
For z = 1 To ArraySize(x())
If x(z)<> x(i) And x(i) + x(z) = R:p1 = x(i):p2= x(z): a$ = "paire " + Str(p1) + " ; " + Str(p2):Break: EndIf
Next
EndProcedure
Chrono_MLD.q=ElapsedMilliseconds()
Repeat
If i < ArraySize(x()) And p1 =0
If p1<> 0:Break:EndIf
i=i +1
EndIf
paire(i)
Until i = ArraySize(x())
If a$ <> ""
MessageRequester("réponse",a$);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"): 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: 0ms
MLD: 6ms
Pour 10000 élements:
Torp: 0ms
MLD: 586ms
Pour 100 000:
Torp: 1ms
MLD: 59200ms
Et voila:
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 : 6.00LTS - 64 bits
Version de PB : 6.00LTS - 64 bits
Re: Entretiens d'embauche chez Google
@Fig
Malin ta réponse (et vrais dans le cas ou il n'y a pas de paire);et seulement dans ce cas
Bien entendus moi aussi je met pas en cause les talents de programmeur ni de Torp, ni les tients.
En fait j’adore ces discussions entre programmeurs qui ce respectent mutuellement, et de ce fait améliore notre savoir et notre art
PS(J'ai un doute sur le 0 mS)
Malin ta réponse (et vrais dans le cas ou il n'y a pas de paire);et seulement dans ce cas
Bien entendus moi aussi je met pas en cause les talents de programmeur ni de Torp, ni les tients.
En fait j’adore ces discussions entre programmeurs qui ce respectent mutuellement, et de ce fait améliore notre savoir et notre art
PS(J'ai un doute sur le 0 mS)
Re: Entretiens d'embauche chez Google
Pas de doute réel sur la milliseconde d'utilisation :
100 000 tests d'addition
sur
1 000 000 000 de tests possibles par seconde. (environ, mais c'est un minimum)
Donc 1 / 10 000ème de seconde pour 100 000 éléments.
Connaître les échelles approchées de ces rythmes-là facilite grandement l'absence d'ordi.
100 000 tests d'addition
sur
1 000 000 000 de tests possibles par seconde. (environ, mais c'est un minimum)
Donc 1 / 10 000ème de seconde pour 100 000 éléments.
Connaître les échelles approchées de ces rythmes-là facilite grandement l'absence d'ordi.
Re: Entretiens d'embauche chez Google
Si il y a une paire, le raisonnement est le même:MLD a écrit :@Fig
Malin ta réponse (et vrais dans le cas ou il n'y a pas de paire);et seulement dans ce cas
Bien entendus moi aussi je met pas en cause les talents de programmeur ni de Torp, ni les tients.
En fait j’adore ces discussions entre programmeurs qui ce respectent mutuellement, et de ce fait améliore notre savoir et notre art
PS(J'ai un doute sur le 0 mS)
10 000 élements, admettons que la paire est à la 5eme positions du début, ça fait pour ton code:
4x10 000+5 essais.
Pour celui de Torp, 10 000.
(Dois je modifier le code pour te le prouver ??)
Quant au 0ms, il faut comprendre inférieur à 1ms évidemment, puisque Elapsemilliseconde() comme son nom l'indique, ne renvoie pas de mesure inférieure à la ms. (en assembleur on peut avoir une mesure plus précise mais ça ne change rien aux conclusions.)
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 : 6.00LTS - 64 bits
Version de PB : 6.00LTS - 64 bits