PureBasic

Forums PureBasic - Français
https://www.purebasic.fr/french/

Entretiens d'embauche chez Google

https://www.purebasic.fr/french/viewtopic.php?t=17202

Page 5 sur 7

Re: Entretiens d'embauche chez Google

Publié : ven. 06/avr./2018 10:36
par Zorro
MLD a écrit : Heu, tu ne tricherait pas un tantinet? Car il me semble que la fonction "findstring" comporte en interne une boucle :?: :wink: :lol:
le code de Torp aussi alors... il reprends exactement mon principe
mais en utilisant une list en lieu et place de ma String .... et en utilisant Foreach-Next


quoiqu'il en soit a partir du moment ou tu as des données dans un tableau, une liste ou des data
et que tu dois faire une comparaison , tu es obligatoirement obligé de faire 2 boucles !!

une pour égrener les élément de ton tableau pour la comparaison
et une autre pour vérifier si ta comparaison se vérifie

la seule exception possible a mon avis c'est l'emploi de la récursivité !

ou donc, la meme procedure d'appel de façon recursive pour a la fois egréner l'element a observer
et verifier le resultat avec les autres elements du tableau ....

il n'y a pas a tortiller ... je ne suis pas ferru de Math
mais je ne pense pas qu'il existe une formule magique qui puisse eviter les 2 boucles dans l'absolu

je dis dans l'absolu , car meme en recursif, il s'agit bien de 2 boucles , meme si c'est la meme qui est utilisée
elle l'est au minimum 2 fois ... :)

Re: Entretiens d'embauche chez Google

Publié : ven. 06/avr./2018 10:53
par Torp
Effectivement j'ai aussi 2 boucles... "Au compte est Bon" je dirais : Pas mieux !

Re: Entretiens d'embauche chez Google

Publié : ven. 06/avr./2018 11:15
par Zorro
autre variante , SANS les 2 boucles !! :)

mais avec un tableau de data aléatoire, contrairement a mon exemple precedent
ou TOUT les chiffres entre 0 et X etaient present de façon mélangés
la on peut avoir plusieur fois les meme chiffres dans le tableau ....

lancer le code plusieurs fois , car le fait aléatoire peut sortir des resultats differents ;)

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,
debut:
dim tab(1000)
for i=1 to ArraySize(tab())
      Tab(i)=random(999,1)      
Next i


Somme_a_trouver=8

;trouver la paire qui correspond à une somme donnée en O(n)...
; on recherche

For x=1 to ArraySize(tab())  ;  <<<<<<<<<<<<<<<<<  une seule boucle !!
      A=Tab(x)
      If A<Somme_a_trouver ; on trouve un candidat potentiel
            If Flag=0
                  Flag=1 ; on active le flag
                  mem_A=A ; on memorise le canditdat
            Else
                  if abs(Somme_a_trouver-mem_A)=A ; on cherche le complement de notre candidat  , s'il correspond on affiche !
                        Debug " la paire : "+"["+str(A)+";"+str(mem_A)+"]"+" forme la somme a trouver ="+str(Somme_a_trouver)
                        Flag=0 ; on remet le flag a zero , pour voir s'il y en a d'autre avant la fin du scan du tableau
                        Flag2=1
                  Endif
            Endif   
      Endif
Next x

If Flag2=0
Debug "pas trouvé de candidat dans le tableau je relance le prg "
goto debut
Endif

Re: Entretiens d'embauche chez Google

Publié : ven. 06/avr./2018 11:28
par Torp
Bravo je pense que t'as décroché le super pompon ! :D

Re: Entretiens d'embauche chez Google

Publié : ven. 06/avr./2018 12:52
par MLD
@ Zorro
On verra ce que propose Fig :?:
Mais pour moi goto est une sorte de spaghetti qui fait une boucle :lol: Ce qui est dailleur admis en assembleur (Jump) :wink:
Je pense comme toi qu'il faut absolument deux boucles, mais va savoir :!: :lol:
Je ne suis pas sur que notre demande d'embauche chez Gogol soit valide :roll: :mrgreen:
@ Torp pour ton embauche tu as eu un piston :wink: :mrgreen:

Re: Entretiens d'embauche chez Google

Publié : ven. 06/avr./2018 13:22
par Zorro
MLD a écrit :@ Zorro
On verra ce que propose Fig :?:
Mais pour moi goto est une sorte de spaghetti qui fait une boucle :lol:
oui tu as raison , mais dans mon code le goto ne sert qu'a relancer automatiquement le prg
si aucune paire n'est trouvé dans le tableau :)
je l'ai ajouté pour ne pas avoir a recompiler si choux blanc ...

MLD a écrit : Je ne suis pas sur que notre demande d'embauche chez Gogol soit valide :roll: :mrgreen:
quoiqu'il en soit chez Google comme ailleurs, il y a des cracks , et aussi des quiches.... :roll:
donc au final, on s'en fout hein ? :lol:

Re: Entretiens d'embauche chez Google

Publié : ven. 06/avr./2018 13:30
par MLD
@Zorro
HI!HI! :lol: :lol:
Tous ceci fait quand même avancé le chmimilibilic. :lol:
et permet au programmeurs débutant de voir qu'un problème donné a XX solutions :wink:

Re: Entretiens d'embauche chez Google

Publié : ven. 06/avr./2018 15:19
par Fig
A tous, la solution implique une seule boucle, on passe en revu chaque élément une seule et unique fois.
Findstring, comme il a été dit plus haut, cache une boucle. Ce n'est donc pas une solution attendue, quoiqu'elle soit valable bien entendue.

Dobro, tu es extrêmement proche de la solution. Le principe est bon, mais tu stocke un seul candidat possible, le premier et tu te focalise que sur celui-ci.
Du coup, ça ne fonctionne pas vraiment, voici un cas qui ne fonctionne pas par exemple. Ici la paire 2;6 (élement 3 et 4 du tableau) font 8 mais n'est pas trouvée.

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,
debut:
Dim tab(4)
; For i=1 To ArraySize(tab())
;       Tab(i)=Random(999,1)      
; Next i
tab(1)=7
tab(2)=3
tab(3)=2
tab(4)=6

Somme_a_trouver=8

;trouver la paire qui correspond à une somme donnée en O(n)...
; on recherche

For x=1 To ArraySize(tab())  ;  <<<<<<<<<<<<<<<<<  une seule boucle !!
      A=Tab(x)
      If A<Somme_a_trouver ; on trouve un candidat potentiel
            If Flag=0
                  Flag=1 ; on active le flag
                  mem_A=A; on memorise le canditdat
            Else
                  If Abs(Somme_a_trouver-mem_A)=A ; on cherche le complement de notre candidat  , s'il correspond on affiche !
                        Debug " la paire : "+"["+Str(A)+";"+Str(mem_A)+"]"+" forme la somme a trouver ="+Str(Somme_a_trouver)
                        Flag=0 ; on remet le flag a zero , pour voir s'il y en a d'autre avant la fin du scan du tableau
                        Flag2=1
                  EndIf
            EndIf   
      EndIf
Next x

If Flag2=0
    Debug "pas trouvé de candidat dans le tableau je relance le prg "
    End
;Goto debut
EndIf
Je peux donner un nouvel indice.Surlignez pour les faire apparaître si vous le souhaitez.
(Il faut utiliser une structure de donnée particulière pour stocker TOUS les compléments et vérifier à chaque fois si on a déja vu sa paire...)

deuxième indice:
La structure en question est une table de hachage (avec comme clé le chiffre) ou un tableau

Re: Entretiens d'embauche chez Google

Publié : ven. 06/avr./2018 16:53
par MLD
@ Fig
Je voudrais être sur d'une choses
Le tableau d''entrée des données ne comporte qu'une seule dimension (comme dans ton exemple), ou l'on peu utiliser un tableau a deux dimensions?

Re: Entretiens d'embauche chez Google

Publié : ven. 06/avr./2018 17:06
par Fig
Tu fais ta soupe comme tu veux, j'attend une réponse en O(n), il n'y a pas qu'une manière de faire je suppose...

Re: Entretiens d'embauche chez Google

Publié : ven. 06/avr./2018 17:57
par MLD
@ Fig
je verrais demain si Zorro ou Torp ne me grille pas :roll: :lol:

Re: Entretiens d'embauche chez Google

Publié : ven. 06/avr./2018 18:07
par Zorro
et comme ça ?

Recursif Power !! :)

Principe de fonctionnement
on prends le premier element de la liste , puis dans la procedure recursive, on le compare a tout les element de la liste ....
ensuite on recommence avec la boucle For-next , avec le deuxieme elements de la liste qu'on compare avec tout les elements de la liste
(y compris lui meme , mais ça doit pouvoir s'eviter avec une memoire de position du pointeur )
etc ...

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
;***********************************************
Declare recherche(c,A)
;soit un tableau rempli de nombres positifs non triés,

Global Dim tab(10000)
For i=1 To ArraySize(tab())
		Tab(i)=Random(50,1)     
Next i


; Global Dim tab(4)
; tab(1)=7
; tab(2)=3
; tab(3)=2
; tab(4)=6

Global Somme_a_trouver=8

;trouver la paire qui correspond à une somme donnée en O(n)...
; on recherche
;calldebugger
For x=1 To ArraySize(tab())  ;  <<<<<<<<<<<<<<<<<  une seule boucle !!
		A=Tab(x)
		recherche(tab(x),A) 
Next x
debug "fin"

Procedure recherche(c,A)
		; recursif Power by Zorro
	
		static x
		x=x+1
		If x>ArraySize(tab())
				x=1
				ProcedureReturn
		Endif
		A=Tab(x)
		If c+A=Somme_a_trouver 
				Debug " la paire : "+"["+Str(A)+";"+Str(c)+"]"+" forme la somme a trouver ="+Str(Somme_a_trouver)
					ProcedureReturn
		Endif
		
		If A<Somme_a_trouver 						
				c=recherche(c,A)					
		Endif
EndProcedure

Re: Entretiens d'embauche chez Google

Publié : ven. 06/avr./2018 20:15
par Fig
C'est une manière originale et créative de refaire une boucle interne supplémentaire.
Si on regarde de prés, pour trouver une paire qui se trouverait à la fin du tableau, tu passe en revu NxN éléments donc toujours O(n²).

Bon, je donnerai la réponse demain après midi.
Bonne soirée :wink:

Re: Entretiens d'embauche chez Google

Publié : ven. 06/avr./2018 20:51
par Zorro
Fig a écrit :C'est une manière originale et créative de refaire une boucle interne supplémentaire.
je suis certain de te prouver que ta solution aura aussi une seconde boucle cachée ...

pour une raison simple , le fait de faire une comparaison de 2 éléments d'une liste de données
oblige a la gestion de 2 pointeurs
le pointeur 1 qui lit les éléments du debut a la fin
le pointeur 2 qui regarde chaque éléments de la liste pour trouver le complément de l’élément pointé par le pointeur 1

donc tu gères 2 pointeurs et leur avancés respective dans la liste
pour ça on utilise 2 boucles, ou bien une astuce pour éviter le trop voyant For-Next ; ForEach-Next ou autre While Wend
et l'astuce , peut etre la récursivité comme je l'ai fait , ou bien l'emploi de 2 variables qui retiennent la position de chaque pointeur dans la liste
mais il te faudra utiliser des sauts a la place de boucles....

franchement, je ne vois pas d'autre solution , meme en utilisant une structure , ça ne changera pas qu'il te faudra 2 pointeurs dans ta liste
et de les gerer ...

on peut aussi envisager de copier la liste 2 fois ...

la liste 1 a mettre au dessus
la liste 2 copie de la 1 a mettre dessous

puis de d'additionner les elements un par un pour obtenir le chiffre a chercher
si rien trouvé , on decale la liste 2 d'un cran, et on recommence

tant que la liste du bas n'a pas fait un tour ...

c'est une autre façon de comparer les elements d'une liste entre eux ...
mais ça reviens quand meme a faire deux boucles et a gerer un pointeur
le second pointeur etant lui , simulé par le decalage de la liste inferieur
decalage qui utilisera aussi une boucle...

Re: Entretiens d'embauche chez Google

Publié : ven. 06/avr./2018 22:39
par Fig
Quand on suit un pointeur, la réponse est en O(1) cad en temps constant. Tu peux suivre presque autant de pointeur que tu veux pour chaque élement, ça ne donnera qu'une réponse en O(n).
Par contre si pour chaque élement tu passe en revu tout les autres élement ça reste une réponse en O(n²)

De toute façon, si tu as un doute là dessus, on pourra chronométrer on aura le même type de réponse qu'entre les deux code de MLD et Torp plus haut, exponentielle pour l'un et linéaire pour l'autre, la différence de chroni étant exponentielle plus il y aura d'élements dans la liste.
Fuseau horaire sur UTC+01:00
Page 5 sur 7

Développé par phpBB® Forum Software © phpBB Limited

Traduction française officielle © Qiaeru