Entretiens d'embauche chez Google

[MLD]

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

[MLD]

@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 (sauf quand il n'y a pas de paire)
Mais je suis Breton donc têtu

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

[Torp]

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

[Fig]

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.

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]

Bonjour Fig
je ne sais pas si c'est la solution, mais j'ai ceci

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

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

[Guillot]

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]

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

[MLD]

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

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

[Zorro]

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.

comme ça ?

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

[Fig]

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]

mais pas en O(n) -simple boucle N élements traités seulement-..

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

[Fig]

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]

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

[Torp]

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 )

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"

[MLD]

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