PureBasic

Forums PureBasic
Nous sommes le Lun 18/Nov/2019 2:50

Heures au format UTC + 1 heure




Poster un nouveau sujet Répondre au sujet  [ 98 messages ]  Aller à la page Précédente  1, 2, 3, 4, 5, 6, 7  Suivante
Auteur Message
 Sujet du message: Re: Entretiens d'embauche chez Google
MessagePosté: Ven 30/Mar/2018 16:19 
Hors ligne

Inscription: Jeu 05/Fév/2009 17:58
Messages: 923
@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 ? :?: :|


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Entretiens d'embauche chez Google
MessagePosté: Ven 30/Mar/2018 16:28 
Hors ligne
Avatar de l’utilisateur

Inscription: Jeu 14/Oct/2004 19:48
Messages: 1121
L’énoncé ne précise pas que la paire doit être la première rencontrée...

_________________
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 : 5.45LTS - 32 bits


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Entretiens d'embauche chez Google
MessagePosté: Ven 30/Mar/2018 22:57 
Hors ligne
Avatar de l’utilisateur

Inscription: Lun 22/Nov/2004 13:05
Messages: 353
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:
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...


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Entretiens d'embauche chez Google
MessagePosté: Ven 30/Mar/2018 23:28 
Hors ligne

Inscription: Ven 29/Juin/2007 17:50
Messages: 3521
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.


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Entretiens d'embauche chez Google
MessagePosté: Sam 31/Mar/2018 10:06 
Hors ligne
Avatar de l’utilisateur

Inscription: Jeu 14/Oct/2004 19:48
Messages: 1121
Torp, tu as bien fait de te griller quelques neurones car c'est effectivement la solution attendue :D
Ta condition de sortie:
Code:
Until (Idx1 > ArraySize(Tab())) Or Idx2 < 0

peut se résumer à ça, en fait:
Code:
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 ! 8O

_________________
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 : 5.45LTS - 32 bits


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Entretiens d'embauche chez Google
MessagePosté: Sam 31/Mar/2018 12:19 
Hors ligne

Inscription: Ven 29/Juin/2007 17:50
Messages: 3521
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.


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Entretiens d'embauche chez Google
MessagePosté: Sam 31/Mar/2018 13:16 
Hors ligne

Inscription: Jeu 05/Fév/2009 17:58
Messages: 923
@Fig
Avant que Torp ne me grille, j’étais la dessus

Code:

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


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Entretiens d'embauche chez Google
MessagePosté: Sam 31/Mar/2018 14:22 
Hors ligne
Avatar de l’utilisateur

Inscription: Jeu 14/Oct/2004 19:48
Messages: 1121
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... :mrgreen:

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

J'ai encore d'autres petits problèmes comme ça, pour ceux qui aiment.

_________________
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 : 5.45LTS - 32 bits


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Entretiens d'embauche chez Google
MessagePosté: Sam 31/Mar/2018 14:46 
Hors ligne

Inscription: Jeu 05/Fév/2009 17:58
Messages: 923
@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 :lol:
Je ne contesterait pas l'arbitrage. :lol:
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 :mrgreen: )


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Entretiens d'embauche chez Google
MessagePosté: Sam 31/Mar/2018 15:00 
Hors ligne
Avatar de l’utilisateur

Inscription: Jeu 14/Oct/2004 19:48
Messages: 1121
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. :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 : 5.45LTS - 32 bits


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Entretiens d'embauche chez Google
MessagePosté: Sam 31/Mar/2018 19:02 
Hors ligne

Inscription: Jeu 05/Fév/2009 17:58
Messages: 923
@Fig
prouve le :wink: :lol:


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Entretiens d'embauche chez Google
MessagePosté: Dim 01/Avr/2018 8:44 
Hors ligne
Avatar de l’utilisateur

Inscription: Jeu 14/Oct/2004 19:48
Messages: 1121
:roll:

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

_________________
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 : 5.45LTS - 32 bits


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Entretiens d'embauche chez Google
MessagePosté: Dim 01/Avr/2018 9:54 
Hors ligne

Inscription: Jeu 05/Fév/2009 17:58
Messages: 923
@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. :lol: :lol:
En fait j’adore ces discussions entre programmeurs qui ce respectent mutuellement, et de ce fait améliore notre savoir et notre art :wink: :lol: :lol:
PS(J'ai un doute sur le 0 mS)


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Entretiens d'embauche chez Google
MessagePosté: Dim 01/Avr/2018 11:02 
Hors ligne

Inscription: Ven 29/Juin/2007 17:50
Messages: 3521
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.


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Entretiens d'embauche chez Google
MessagePosté: Dim 01/Avr/2018 13:26 
Hors ligne
Avatar de l’utilisateur

Inscription: Jeu 14/Oct/2004 19:48
Messages: 1121
MLD a écrit:
@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. :lol: :lol:
En fait j’adore ces discussions entre programmeurs qui ce respectent mutuellement, et de ce fait améliore notre savoir et notre art :wink: :lol: :lol:
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.)

_________________
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 : 5.45LTS - 32 bits


Haut
 Profil  
Répondre en citant le message  
Afficher les messages postés depuis:  Trier par  
Poster un nouveau sujet Répondre au sujet  [ 98 messages ]  Aller à la page Précédente  1, 2, 3, 4, 5, 6, 7  Suivante

Heures au format UTC + 1 heure


Qui est en ligne

Utilisateurs parcourant ce forum: Aucun utilisateur enregistré et 3 invités


Vous ne pouvez pas poster de nouveaux sujets
Vous ne pouvez pas répondre aux sujets
Vous ne pouvez pas éditer vos messages
Vous ne pouvez pas supprimer vos messages

Rechercher:
Aller à:  
cron

 


Powered by phpBB © 2008 phpBB Group | Traduction par: phpBB-fr.com
subSilver+ theme by Canver Software, sponsor Sanal Modifiye