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 »

Fig a écrit :Par contre si pour chaque élement tu passe en revu tout les autres élement ça reste une réponse en O(n²)
oui, mais c'est LA seule solution, pour ne rien louper !
si tu ne passe pas en revu tout les elements, tu prends le risque de louper des pairs possibles ....

la solution pour ne rien louper c'est celle-ci entre autre :
(avec l'emloi de 2 pointeurs de données de 2 boucles ) tu es sur de ressortir toutes les paire possibles

si tu n'emploi pas ce systeme , tu risque de louper des paires possible , car tout tes elements ne seront pas pris en compte

mais a ce stade,j'ai peut etre pas compris le but final .... :)

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 rotation()
;soit un tableau rempli de nombres positifs non triés,
; ; 
 Global Dim tab(100)
 
 For i=1 To ArraySize(tab())
 				Tab(i)=Random(50,1)   		
 Next i





; 
; ; 
;  Global Dim tab(4)
;  
;  
;  
;  tab(1)=5
;  tab(2)=7
;  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

For y=1 to ArraySize(tab())
		For x=1 To ArraySize(tab()) 
				if x<>y
						a=Tab(y)
						C=Tab(x)
						If a+C=Somme_a_trouver
								Debug " la paire : "+"["+Str(A)+";"+Str(c)+"]"+" forme la somme a trouver ="+Str(Somme_a_trouver)
								Break
						Endif
				Endif
		Next x
		
Next y

debug "fin"

; Epb
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 »

@Fig
Après m'avoir bien trituré les méninges, comme zorro je suis persuadé qu'il faut d'une manière ou d'une autre deux boucles pour obtenir le résultat. (Ou je n'est rien compris)
Il faut bien prendre chaque indice du tableau, et le comparé avec les autres pour trouver une paire valable. :?:
J'ai hâte de voir ta solution 8O :lol:
@ Zorro
La comparaison peut être a+c ou a-c :wink:
Avatar de l’utilisateur
Fig
Messages : 1176
Inscription : jeu. 14/oct./2004 19:48

Re: Entretiens d'embauche chez Google

Message par Fig »

Voila ma solution... Je suis sûr que ça va vous paraître évident maintenant.
Pour plus de souplesse et pour économiser de la mémoire, on peut utiliser une map (table de hachage). (ça ne changera rien au O(n))
Mais dans le principe, ça donne ça:

Code : Tout sélectionner

;Somme à trouver
#somme=8
;tableau des #nbElement valeurs
#nbElement=5
;valeur maximale des élements
#valeur_max=12
Dim Tableau.i(#nbElement) ;remplissage du tableau
For i=1 To #nbElement
    tableau(i)=Random(#valeur_max,1)
    ;Debug Tableau(i)
Next i

;tableau des compléments ou map si on le souhaite...
Dim comp.i(#valeur_max)

;on passe en revu chaque élément. Pour chacun d'eux, on vérifie si on a déja croisé par le passé son complément, sinon on le rajoute
For i=1 To #nbElement ;On a O(1) x N soit O(N) pour le traitement de tous les élements
    element.i=tableau(i) ;temps constant O(1)
    complement.i=#somme-element:If complement<0:Continue:EndIf
    
    ;vérifie si le complément de la valeur actuelle a déja été vue.
    If comp(complement) ;temps constant O(1)
        ;dans ce cas on a une paire
        MessageRequester("Résultat","La paire est "+Str(tableau(i))+";"+Str(tableau(comp(complement))))
        End
    Else ;sinon on le rajoute
        comp(element)=i ;temps constant O(1)
    EndIf
Next i
MessageRequester("Résultat","Pas de paire trouvée")
End
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 »

:roll: :roll: :roll:

on a tellement l'habitude de penser Tableau dans une boucle et scan de celui-ci depuis le debut
qu'on en oublie qu'una case d'un tableau peut etre accedé en mode direct par son index !! :oops: :oops:

Code : Tout sélectionner

 If comp(complement)
bien vu ... purée , je vais arreter la prog , et faire autre chose moi ... :lol:
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 »

@Fig

Ou j'ai rien compris ou il y a un problème de fonctionnement :?:

Code : Tout sélectionner

;Somme à trouver
#somme= 10
;tableau des #nbElement valeurs
#nbElement=10
;valeur maximale des élements
#valeur_max=100
Dim Tableau.i(#nbElement) ;remplissage du tableau
; For i=1 To #nbElement
;     tableau(i)=Random(#valeur_max,1)
;     Debug Tableau(i)
; Next i
tableau(1)=24:tableau(2)=81:tableau(3)= 73:tableau(4)= 41:tableau(5)=51:tableau(6)= 67:tableau(7)= 2:tableau(8)= 99:tableau(9)= 57:tableau(10)=26
;tableau des compléments ou map si on le souhaite...
Dim comp.i(#valeur_max)
;on passe en revu chaque élément. Pour chacun d'eux, on vérifie si on a déja croisé par le passé son complément, sinon on le rajoute
For i=1 To #nbElement
    element.i=tableau(i)
    complement.i=#somme-element:If complement<0:Continue:EndIf
   
    ;vérifie si le complément de la valeur actuelle a déja été vue.
    If comp(complement)
        ;dans ce cas on a une paire
        MessageRequester("Résultat","La paire est "+Str(tableau(i))+";"+Str(tableau(comp(complement))))
        End
    Else ;sinon on le rajoute
        comp(element)=i
    EndIf
  Next i

MessageRequester("Résultat","Pas de paire trouvée")

End

51-41 font bien 10 il me semble :wink:
Avatar de l’utilisateur
Fig
Messages : 1176
Inscription : jeu. 14/oct./2004 19:48

Re: Entretiens d'embauche chez Google

Message par Fig »

On cherche la somme pas la différence... La paire 41;51 fait 92...
Je me sers du complément car si tu as un 4 et que tu cherche à faire une somme de 10, il faut que tu trouve un 6... (10-4)

Question 4: (plus simple)
Trouvez si deux rectangles (définis par leurs points haut-gauche et bas-droit) se chevauchent (subsidiaire, savoir si ils se confondent, ou se touchent).
Dernière modification par Fig le sam. 07/avr./2018 14:09, 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
Ok j'ai pas compris :oops: J'ai pensé une somme, mais pas la somme de deux paires.
Déformation professionnel: Comme je travail beaucoup pour des financiers ou des cabinets d'avocats. J'ai très souvent a rechercher dans des tableaux de chiffres des écarts ou des similitudes
mais rarement la somme de deux chiffres dans un même tableau.
D'ailleurs je vais avoir dans les semaines qui viennent beaucoup de travail.de fait je n'aurais pas le temps pour ton problème de triangles.
Merci pour ces exercices
Michel
Avatar de l’utilisateur
Zorro
Messages : 2185
Inscription : mar. 31/mai/2016 9:06

Re: Entretiens d'embauche chez Google

Message par Zorro »

pour les collisions j'avais fait ça a une epoque

une procedure de "Super collision"
elle a la particularité d'indiquer exactement ou a lieu la collision sur un polygone de 4 cotés

je pense que ça repond a la question ....
garder en tete, qu'il s'agit d'une procedure de collision , donc le test n'a lieu qu'au moment de la colision

ça indique si on est dessous, dessus, a gauche , a droite et aussi en bas a gauche, en bas a droite , en haut a gauche, en haut a droite
et Dedans ou en dehors ....
bougez la souris pour voir ce qui est ecrit en haut a gauche de l'ecran :)

Code : Tout sélectionner


; prg realisé par Dobro
#dobro=1
#Police=1
#sprite=1

Declare.s super_collision(sprite_numero1, x_sprite1, y_sprite1, sprite_numero2, x_sprite2, y_sprite2)
; cette procedure renvoie du quelle coté le sprite a été touché !

; sprite_numero1= le numero du sprite 1 a tester
;  largeur_spr1 = largeur en pixel du sprite numero 1
; hauteur_spr1 = hauteur en pixel du sprite numero 1
; x_sprite1 = coordonée X du sprite numero 1
; y_sprite1=coordonée Y du sprite numero 1
; --------------------------------------------------------------------------
; sprite_numero2=  le numero du sprite 2 a tester
;  largeur_spr2 = largeur en pixel du sprite numero 2
; hauteur_spr12 = hauteur en pixel du sprite numero 2
; x_sprite2 = coordonée X du sprite numero 2
; y_sprite2 coordonée Y du sprite numero 2

Enumeration
		#Window
		#sprite_cible
		#sprite_souris
		#sprite_text 
EndEnumeration

Structure sprite
		x.w
		y.w 
EndStructure
Dim sprite.sprite(1)

Dim ecran(640,400)
For x = 0 To 640 ; un écran de couleurs aléatoires
		For y = 0 To 400
				r=Random(255)
				G=Random(255)
				b=Random(255)
				c=RGB(r,G,b)
				ecran(x,y)= c
		Next y
Next x
; ***********************************
Resultat = InitSprite()
FontID = LoadFont(#Police, "arial", 18, #PB_Font_Bold )
EcranX = GetSystemMetrics_(#SM_CXSCREEN):;=largeur de l'ecran
EcranY = GetSystemMetrics_(#SM_CYSCREEN):;=hauteur de l'ecran
WindowID = OpenWindow(#Window, 0, 0, 800, 600,  "hello",#PB_Window_SystemMenu|#PB_Window_BorderLess |#PB_Window_ScreenCentered )

Result = OpenWindowedScreen(WindowID(#Window),0,0, 800, 600, 1, 0,0)


CreateSprite( #sprite_cible, 64, 64)  ; sprite exemple
StartDrawing(SpriteOutput( #sprite_cible) ) ; on dessine dedans
		Box(0, 0, 64, 64, RGB($FF,$0,$80))
StopDrawing()

CreateSprite( #sprite_souris, 32, 32)  ; sprite souris
StartDrawing(SpriteOutput( #sprite_souris) ) ; on dessine dedans
		Box(0, 0, 64, 64,RGB($13,$F8,$7))
StopDrawing()

bord$="aucun bord"
CreateSprite(#sprite_text, 150,14)  ; le text
StartDrawing(SpriteOutput(#sprite_text) ) ; on dessine dedans
		DrawText(1,1,bord$,RGB(0,0,0), RGB(255,255,255))
StopDrawing()

Resultat = InitMouse()  
Repeat
		ExamineMouse()
		Event=WindowEvent()
		
		DisplaySprite(#sprite_cible, WindowWidth(#Window) /2+50,  WindowHeight(#Window)/2+100)
		sprite(1)\x=WindowWidth(#Window)/2+50
		sprite(1)\y=WindowHeight(#Window)/2+100
		
		DisplaySprite(#sprite_souris,  MouseX(),   MouseY())
		DisplaySprite( #sprite_text,  10,  10) 
		
		bord$=super_collision(#sprite_cible, sprite(1)\x,sprite(1)\y, #sprite_souris,MouseX(), MouseY())  
		
		
		StartDrawing(SpriteOutput(#sprite_text) ) ; on dessine dedans
				DrawText(1,1,"                              ", RGB(0,0,0), RGB(255,255,255))
				DrawText(1,1,bord$,RGB(0,0,0), RGB(255,255,255)) 
		StopDrawing() 
		If MouseButton(2)
				End
		EndIf 
		
		FlipBuffers():; affiche l'ecran
		ClearScreen(RGB(0, 0, 0)) :;efface l'ecran 
Until Event=#PB_Event_CloseWindow






Procedure.s super_collision(sprite_numero1, x_sprite1, y_sprite1, sprite_numero2, x_sprite2, y_sprite2)
		; code Dobro
		spr1_milieu_x=x_sprite1+SpriteWidth(sprite_numero1) /2
		spr1_milieu_y=y_sprite1+SpriteHeight(sprite_numero1)/2
		spr2_milieu_x=x_sprite2+SpriteWidth(sprite_numero2)/2
		spr2_milieu_y=y_sprite2+SpriteHeight(sprite_numero2)/2
		
		spr1_hauteur=SpriteHeight(sprite_numero1)
		spr1_largeur=SpriteWidth(sprite_numero1)
		spr2_hauteur=SpriteHeight(sprite_numero2)
		spr2_largeur=SpriteWidth(sprite_numero2)
		
		
		If SpriteCollision(sprite_numero1,x_sprite1, y_sprite1,sprite_numero2,x_sprite2, y_sprite2)
				If  spr2_milieu_x<x_sprite1 And spr2_milieu_y<y_sprite1
						bord$="haut-gauche  a cheval               "
						Goto suite
				EndIf
				
				If  spr2_milieu_x>(x_sprite1+spr1_largeur) And spr2_milieu_y<y_sprite1
						bord$="haut-droit  a cheval         "
						Goto suite
				EndIf
				
				If spr2_milieu_x>x_sprite1+spr1_largeur And spr2_milieu_y>y_sprite1+spr1_hauteur
						bord$="bas-droit  a cheval       "
						Goto suite
				EndIf
				
				If spr2_milieu_x<x_sprite1 And spr2_milieu_y>y_sprite1+spr1_hauteur
						bord$="bas-gauche  a cheval"
						Goto suite
				EndIf
				
				
				
				
				If x_sprite2+spr2_largeur>x_sprite1 And  x_sprite2<x_sprite1+spr1_largeur And spr2_milieu_y<y_sprite1
						bord$="haut  a cheval       "
						Goto suite
				EndIf
				
				If  y_sprite2+spr2_hauteur>y_sprite1 And y_sprite2<y_sprite1+spr1_hauteur And spr2_milieu_x>x_sprite1+spr1_largeur
						bord$="droit  a cheval             "
						Goto suite
				EndIf
				
				If  x_sprite2+spr2_largeur>x_sprite1 And x_sprite2<x_sprite1+spr1_largeur And spr2_milieu_y>y_sprite1+spr1_hauteur
						bord$="bas  a cheval            "
						Goto suite
				EndIf
				
				If  y_sprite2+spr2_hauteur>y_sprite1 And y_sprite2<y_sprite1+spr1_hauteur And  spr2_milieu_x<x_sprite1
						bord$="gauche  a cheval          "
						Goto suite
				EndIf
				
				If x_sprite2 > x_sprite1 And (x_sprite2+spr2_largeur) <x_sprite1+spr1_largeur
						If  y_sprite2>y_sprite1  and  y_sprite2+spr2_hauteur<y_sprite1+spr1_hauteur
								bord$="Dedans                   "
								Goto suite
						Endif
				EndIf
				Else
				
		bord$=" en dehors" 
	
				
				
		EndIf
		
		suite:
		ProcedureReturn  bord$
EndProcedure




Image
Image
Site: http://michel.dobro.free.fr/
Devise :"dis moi ce dont tu as besoin, je t'expliquerai comment t'en passer"
zaphod_b
Messages : 76
Inscription : mar. 09/déc./2014 20:02

Re: Entretiens d'embauche chez Google

Message par zaphod_b »

Salut,
pour la soluce "officielle" du prob 3 : c pas clair.

avec ces valeurs :

Code : Tout sélectionner

tableau(1)=5:tableau(2)=6:tableau(3)=4:tableau(4)=2:Tableau(5)=10:tableau(6)=4:tableau(7)=3
on a comme résultat : paire 2:6
Il suffisait donc de trouver une seule paire dans le tableau ????
Il y a aussi 5;3 et 4;4 avec les données de l'exemple ci dessus.
Comme il n'y a qu'une boucle les autres paires ne sont pas trouvées.
Avatar de l’utilisateur
Zorro
Messages : 2185
Inscription : mar. 31/mai/2016 9:06

Re: Entretiens d'embauche chez Google

Message par Zorro »

retire le End de la ligne 27
et repond au dialogue :)

avec le End , ça s'arrete au premier trouvé effectivement

le secret du truc , c'est qu'il utilise un acces direct au tableau
au lieu de l'habituel acces sequentiel des elements d'un tableau

on a l'habitude de scanner l'ensemble des elements d'un tableau pour connaitre la valeur de chaque case

là l'astuce consiste a utiliser un tableau comme si c’était des appartements d'un HLM
il ne met dans une case QUE l'element correspondant au numero de la case (adresse de l'appart ) :lol:

mince ... on est dans la citée .... vite REDIM :mrgreen:

en tout cas c'est bien vu cette utilisation d'un tableau
pourtant je le sais qu'un tableau c'est un ensemble de case memoire
mais je ne sais pas pourquoi , je l'utilise toujours dans une boucle... c'est con hein ? :mrgreen: :lol:

encore que maintenant, je prefere les listes chainées , mon probleme viens surement de ça :)
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 »

Puisque Dobro avait déja anticipé la question 4... :wink:
Question 5:

On a un tableau dont chaque valeur est la hauteur de la tour.
On part de la tour numéro 0 (indice 0 du tableau) et on souhaite sauter en position 6 en dehors du tableau dans le cas particulier de mon exemple.
On peut sauter de gauche à droite au maximum de la hauteur de la tour sur laquelle on se trouve.
(si on est sur la tour de hauteur 4, on peut sauter 4, 3, 2 ou 1 tour vers la droite)
On ne peut pas sauter une tour plus haute que celle sur laquelle on est.
Si on est sur une tour de hauteur 0, on ne peut plus avancer, on est bloqué, il n'y a pas de solution ou ce n'est pas la solution.
Evidemment, le programme devra permettre plus de 6 tours si nécessaire.

Le but est de trouver une solution (si elle existe) qui permet de sortir à droite du tableau en un minimum de saut.
Il existe 3 manières de faire différente: Récursive, via un graph, ou un algorithme glouton.


Si vous avez des questions...

Voila l'illustration du problème:
Image
Dernière modification par Fig le dim. 08/avr./2018 19:55, 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
Zorro
Messages : 2185
Inscription : mar. 31/mai/2016 9:06

Re: Entretiens d'embauche chez Google

Message par Zorro »

Verrai ça demain, mais deja
Je ne comprends pas trop l'énoncé.... :)

Vous pouvez repeter la question (ref:les inconnus)

Donc dans ton dessin le trajet ideale serai 0145 ?
Ou 045 ?
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 »

04(6)

Le bonhomme en 1 est juste là pour illustrer une position intermédiaire à la résolution du problème.
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 »

En principe pour moi ce probleme est resolu :)

je vais attendre un peu avant de poster ma solution
histoire de pas décourager ceux qui cherchent :)

ps: j'ai choisi la solution recursive :)
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
Zorro
Messages : 2185
Inscription : mar. 31/mai/2016 9:06

Re: Entretiens d'embauche chez Google

Message par Zorro »

hum , ça a pas l'air de concerner grand monde :)
vous avez donc une vie en dehors de Purebasic ?? :lol:
Image
Image
Site: http://michel.dobro.free.fr/
Devise :"dis moi ce dont tu as besoin, je t'expliquerai comment t'en passer"
Répondre