Entretiens d'embauche chez Google

Vous débutez et vous avez besoin d'aide ? N'hésitez pas à poser vos questions
Avatar de l’utilisateur
Zorro
Messages : 2185
Inscription : mar. 31/mai/2016 9:06

Re: Entretiens d'embauche chez Google

Message 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 ... :)
Dernière modification par Zorro le ven. 06/avr./2018 10:59, modifié 2 fois.
Image
Image
Site: http://michel.dobro.free.fr/
Devise :"dis moi ce dont tu as besoin, je t'expliquerai comment t'en passer"
Torp
Messages : 360
Inscription : lun. 22/nov./2004 13:05

Re: Entretiens d'embauche chez Google

Message par Torp »

Effectivement j'ai aussi 2 boucles... "Au compte est Bon" je dirais : Pas mieux !
Avatar de l’utilisateur
Zorro
Messages : 2185
Inscription : mar. 31/mai/2016 9:06

Re: Entretiens d'embauche chez Google

Message 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

Dernière modification par Zorro le ven. 06/avr./2018 11:28, modifié 1 fois.
Image
Image
Site: http://michel.dobro.free.fr/
Devise :"dis moi ce dont tu as besoin, je t'expliquerai comment t'en passer"
Torp
Messages : 360
Inscription : lun. 22/nov./2004 13:05

Re: Entretiens d'embauche chez Google

Message par Torp »

Bravo je pense que t'as décroché le super pompon ! :D
Avatar de l’utilisateur
MLD
Messages : 1097
Inscription : jeu. 05/févr./2009 17:58
Localisation : Bretagne

Re: Entretiens d'embauche chez Google

Message 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:
Avatar de l’utilisateur
Zorro
Messages : 2185
Inscription : mar. 31/mai/2016 9:06

Re: Entretiens d'embauche chez Google

Message 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:
Dernière modification par Zorro le ven. 06/avr./2018 13:30, modifié 1 fois.
Image
Image
Site: http://michel.dobro.free.fr/
Devise :"dis moi ce dont tu as besoin, je t'expliquerai comment t'en passer"
Avatar de l’utilisateur
MLD
Messages : 1097
Inscription : jeu. 05/févr./2009 17:58
Localisation : Bretagne

Re: Entretiens d'embauche chez Google

Message 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:
Avatar de l’utilisateur
Fig
Messages : 1176
Inscription : jeu. 14/oct./2004 19:48

Re: Entretiens d'embauche chez Google

Message 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
Dernière modification par Fig le ven. 06/avr./2018 17:14, modifié 1 fois.
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
Avatar de l’utilisateur
MLD
Messages : 1097
Inscription : jeu. 05/févr./2009 17:58
Localisation : Bretagne

Re: Entretiens d'embauche chez Google

Message 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?
Avatar de l’utilisateur
Fig
Messages : 1176
Inscription : jeu. 14/oct./2004 19:48

Re: Entretiens d'embauche chez Google

Message 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...
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
Avatar de l’utilisateur
MLD
Messages : 1097
Inscription : jeu. 05/févr./2009 17:58
Localisation : Bretagne

Re: Entretiens d'embauche chez Google

Message par MLD »

@ Fig
je verrais demain si Zorro ou Torp ne me grille pas :roll: :lol:
Avatar de l’utilisateur
Zorro
Messages : 2185
Inscription : mar. 31/mai/2016 9:06

Re: Entretiens d'embauche chez Google

Message 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
Image
Image
Site: http://michel.dobro.free.fr/
Devise :"dis moi ce dont tu as besoin, je t'expliquerai comment t'en passer"
Avatar de l’utilisateur
Fig
Messages : 1176
Inscription : jeu. 14/oct./2004 19:48

Re: Entretiens d'embauche chez Google

Message 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:
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
Avatar de l’utilisateur
Zorro
Messages : 2185
Inscription : mar. 31/mai/2016 9:06

Re: Entretiens d'embauche chez Google

Message 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...
Image
Image
Site: http://michel.dobro.free.fr/
Devise :"dis moi ce dont tu as besoin, je t'expliquerai comment t'en passer"
Avatar de l’utilisateur
Fig
Messages : 1176
Inscription : jeu. 14/oct./2004 19:48

Re: Entretiens d'embauche chez Google

Message 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.
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
Répondre