Entretiens d'embauche chez Google

[MLD]

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

[Fig]

L’énoncé ne précise pas que la paire doit être la première rencontrée...

[Torp]

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.

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"

Pour la Q3, je coince...

[Ollivier]

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.

[Fig]

Torp, tu as bien fait de te griller quelques neurones car c'est effectivement la solution attendue
Ta condition de sortie:

Code : Tout sélectionner

Until (Idx1 > ArraySize(Tab())) Or Idx2 < 0

peut se résumer à ça, en fait:

Code : Tout sélectionner

Until Idx1=Idx2

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 !

[Ollivier]

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.

[MLD]

@Fig
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  

ferai je partie du personnel de Gogol

[Fig]

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.

[MLD]

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

[Fig]

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.

[MLD]

@Fig
prouve le

[Fig]

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

Pour 1000 élements:
Torp: 0ms
MLD: 6ms

Pour 10000 élements:
Torp: 0ms
MLD: 586ms

Pour 100 000:
Torp: 1ms
MLD: 59200ms

Et voila:

[MLD]

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

[Ollivier]

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.

[Fig]

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

Si il y a une paire, le raisonnement est le même:
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.)