PureBasic

Forums PureBasic
Nous sommes le Dim 17/Nov/2019 16:45

Heures au format UTC + 1 heure




Poster un nouveau sujet Répondre au sujet  [ 98 messages ]  Aller à la page 1, 2, 3, 4, 5 ... 7  Suivante
Auteur Message
 Sujet du message: Entretiens d'embauche chez Google
MessagePosté: Mar 27/Mar/2018 18:03 
Hors ligne
Avatar de l’utilisateur

Inscription: Jeu 14/Oct/2004 19:48
Messages: 1121
Question 1:

Comment trouver le premier caractère en double dans une chaîne de caractère ?

Par exemple dans cette chaine, le premier caractère en double est le (pas le A) mais le D !! (merci Marc)
Chaine$="POABCDEFTHLGDSALKL"

Il y a évidemment deux solutions, une naïve (qui vous vient déjà à l'esprit, ne niez pas ! ) en O(n²) et une plus efficace en O(n).
Jouez honnêtement le jeu, vous avez 30 secondes pour y réfléchir...


Du coup, on se dit qu'on devrait postuler, non ? 8)

_________________
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


Dernière édition par Fig le Jeu 29/Mar/2018 18:56, édité 3 fois.

Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Entretien d'embauche téléphonique chez Google
MessagePosté: Mar 27/Mar/2018 18:14 
Hors ligne
Avatar de l’utilisateur

Inscription: Jeu 25/Juin/2015 16:18
Messages: 268
Code:
Chaine$="POABCDEFTHLGDSALKL"

Dim c(255)
For i=1 To Len(Chaine$)
  a=Asc(Mid(chaine$,i,1))
  c(a)+1
  If c(a)=2:Debug Chr(a):End:EndIf
Next


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Entretien d'embauche téléphonique chez Google
MessagePosté: Mar 27/Mar/2018 18:43 
Hors ligne
Avatar de l’utilisateur

Inscription: Jeu 14/Oct/2004 19:48
Messages: 1121
Embauché ! :lol:

_________________
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: Entretien d'embauche téléphonique chez Google
MessagePosté: Mar 27/Mar/2018 18:58 
Hors ligne
Avatar de l’utilisateur

Inscription: Jeu 25/Juin/2015 16:18
Messages: 268
connaissent pas mes prétentions salariales !!


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Entretien d'embauche téléphonique chez Google
MessagePosté: Mar 27/Mar/2018 22:46 
Hors ligne

Inscription: Ven 29/Juin/2007 17:50
Messages: 3521
Pour aller plus vite :
http://www.purebasic.fr/french/viewtopic.php?f=6&t=16276
Il y a les SSE mais j'ai ommis où j'ai mis ça. C'est dans la section ASM. Ipistri ou Champistri, je sais plus...

And... Yea ! When Google becomes nake, Google becomes my friend ! A poil mon pote ! Rock n Roll !

Au fait... Mais... A qui profite le criiiii....
.....
...
(votre correspond s'est pris la comète "Tagoul 937" et c'est bien dommage pour lui, prends-en de la graine!)
...


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Entretien d'embauche téléphonique chez Google
MessagePosté: Mer 28/Mar/2018 8:17 
Hors ligne

Inscription: Sam 08/Fév/2014 15:19
Messages: 1635
Citation:
Comment trouver le premier caractère en double dans une chaîne de caractère ?
Par exemple dans cette chaine, le premier caractère en double est le A
Chaine$="POABCDEFTHLGDSALKL"

Ça dépend comment on perçoit le premier du double.
D'après le programme de Guillot et la logique pure, c'est D et pas A
P O A B C D E F T H L G D S A L K L
:?:


Voilà ma version (Code moche première fois que j'utilise une map)
Code:
Chaine$="POABCDEFTHLGDSALKL"
Debug "Chaine à traiter: " + Chaine$
NewMap Lettre.s()

For i = 1 To Len(Chaine$)
     Caratere.s = Mid(Chaine$, i, 1)
     Debug "#" + RSet(Str(i), 2, " ") + " -> " + Caratere
     If FindMapElement(Lettre(), Caratere)
          Debug "------ " + Caratere + " existe déjà !"
     Else
          AddMapElement(Lettre(), Mid(Chaine$, i, 1), #PB_Map_NoElementCheck)
     EndIf
Next

Code:
Chaine à traiter: POABCDEFTHLGDSALKL
# 1 -> P
# 2 -> O
# 3 -> A
# 4 -> B
# 5 -> C
# 6 -> D
# 7 -> E
# 8 -> F
# 9 -> T
#10 -> H
#11 -> L
#12 -> G
#13 -> D
------ D existe déjà !
#14 -> S
#15 -> A
------ A existe déjà !
#16 -> L
------ L existe déjà !
#17 -> K
#18 -> L
------ L existe déjà !

Mais c'est une méthode linéaire: le référentiel se construit au fur et à mesure.
Si la liste de référence est déjà construite, alors c'est effectivement le A qui sera vu en premier.
(mais j'ai toujours été nul en math, c'est pourquoi je n'ai pas compris le O(n²) et O(n) qui expriment sans doute cela d'une manière abstraite ?)
:wink:

_________________
Windows 10 Famille x64 + Linux (Slackware, Debian sur Oracle VirtualBox 6.0), Raspberry Pi


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Entretien d'embauche téléphonique chez Google
MessagePosté: Mer 28/Mar/2018 11:27 
Hors ligne
Avatar de l’utilisateur

Inscription: Lun 17/Déc/2007 12:44
Messages: 1635
Bonjour,

Une autre version possible :

Code:
EnableExplicit

Define.l i
Define.s temp, char = "POABCDEFTHLGDSALKL"

For i=1 To Len(char) - 1
  temp = Mid(char, i, 1)
  If FindString(char, temp, i + 1) > 0
    Debug temp
    Break 
  EndIf
Next i


Cordialement,
GallyHC

_________________
Image

Image

Image Official site of PureBasic
Image Official site of SpiderBasic

Configuration : Tower: Windows 10 (Processeur: i7 "x64") (Mémoire: 16Go) (GeForce GTX 760 - 2Go) - PureBasic 5.71 LTS (x86 et x64)


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Entretien d'embauche téléphonique chez Google
MessagePosté: Mer 28/Mar/2018 13:54 
Hors ligne
Avatar de l’utilisateur

Inscription: Dim 09/Oct/2005 16:51
Messages: 8779
Un peu plus de lignes..
Code:
Global NewList lettre.s()

Global char.s = "POABCDEFTHLGDSALKL"

For i=1 To Len(char) - 1 :   AddElement (lettre()) :   lettre() = Mid(char, i, 1) : Next i
SortList(Lettre(), #PB_Sort_Ascending)

For i=0 To Len(char) - 3
  SelectElement(lettre(),i)
  car1.s = lettre()
  SelectElement(lettre(),i+1)
  car2.s = lettre()
  If car1 = car2 : compte +1 : Debug "1er double trouvé : "+car1 : Break : EndIf
Next

_________________
~~~~Règles du forum ~~~~
.: Ar-S :. Tour + portable W10 x64 PB 5.4x / 5.6x
LDV MULTIMEDIA : Dépannage informatique & mes Logiciels PB
RESIZER GOLD : Mon logiciel de redimensionnement par lot 100% PB


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Entretien d'embauche téléphonique chez Google
MessagePosté: Mer 28/Mar/2018 15:23 
Hors ligne
Avatar de l’utilisateur

Inscription: Jeu 14/Oct/2004 19:48
Messages: 1121
Marc, tu as raison dans mon exemple c'est la lettre D qui est attendu et non le A comme je l'avais écrit.

Concernant la notation "Big O", ce n'est pas très compliqué mais fondamentale pour l'analyse de la vitesse des algorithmes indépendamment de l'implémentation.

http://bigocheatsheet.com/

Par exemple si tu dois examiner chaque élément d'une liste pour trouver la réponse à un problème, ton algo est de type O(n) cad que plus il y a d'éléments dans la liste (n éléments) plus ça sera proportionnellement long. C'est une droite.
Si pour chaque élément de la liste tu dois le comparer à chacun des autres éléments de cette même liste, tu fera n² itérations (soit une double boucle imbriquée). Dans ce cas, la courbe est quadratique au nombre d’éléments de la liste O(n²).
Cherche un élément en mémoire prend en moyenne un temps constant donc O(1)
Etc...
Selon le type d’algorithme et selon le nombre d’éléments traités, le but est de trouver un algo qui est calculable en un temps raisonnable.

Quelques exemples, en abscisse le nombre d'éléments, en ordonnée, le temps de traitement.
Image

La réponse de GallyHC est O(n²) car chaque élément est comparé à tous les autres (la fonction findstring est une boucle en fait), la tienne O(n).
Celle de Ars qui utilise le tri des listes est O(n log n) -pour simplifier, mais en fait pire à cause des deux autres boucles-, en effet, le tri des listes chainées en Pb est un tri par fusion (il me semble).

Si il y a une complexité forte, ça reste acceptable dans la mesure où on traite peu d'éléments.

_________________
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: Entretien d'embauche téléphonique chez Google
MessagePosté: Mer 28/Mar/2018 15:56 
Hors ligne
Avatar de l’utilisateur

Inscription: Dim 09/Oct/2005 16:51
Messages: 8779
Ah du coup j'avais mal lu l'énoncé, mon code trouve les premières lettre en double mais pas celles qui apparaissent dans la liste en 1er

_________________
~~~~Règles du forum ~~~~
.: Ar-S :. Tour + portable W10 x64 PB 5.4x / 5.6x
LDV MULTIMEDIA : Dépannage informatique & mes Logiciels PB
RESIZER GOLD : Mon logiciel de redimensionnement par lot 100% PB


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Entretien d'embauche téléphonique chez Google
MessagePosté: Mer 28/Mar/2018 16:09 
Hors ligne

Inscription: Sam 08/Fév/2014 15:19
Messages: 1635
Et dire que j'ai fais ça sans rien y comprendre :o 8O
:idea: Je me suis simplement dit que comme les Maps refusent les doublons, il suffit de remplir avec chaque caractère et d'attendre le message d'erreur :?: :P
(j'ai honte de ma logique cheap de vieux codeur autodidacte :oops: )
:mrgreen:

_________________
Windows 10 Famille x64 + Linux (Slackware, Debian sur Oracle VirtualBox 6.0), Raspberry Pi


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Entretien d'embauche téléphonique chez Google
MessagePosté: Mer 28/Mar/2018 16:26 
Hors ligne
Avatar de l’utilisateur

Inscription: Ven 13/Fév/2004 0:57
Messages: 3702
Code de Gally modifié pour prendre en compte le premier doublon tel qu'on l'attend:

Code:
EnableExplicit

Define.l i, position, mem=65535
Define.s temp, first, char = "POABCDEFTHLGDSALKL"

For i=1 To Len(char) - 1
    temp = Mid(char, i, 1)
    position = FindString(char, temp, i + 1)
    If position > 0
        Debug temp
        If position<mem
            mem=position
            first = temp
        EndIf
    EndIf
Next i

Debug "-----------------------------"
Debug mem
Debug first


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Entretien d'embauche téléphonique chez Google
MessagePosté: Mer 28/Mar/2018 17:03 
Hors ligne
Avatar de l’utilisateur

Inscription: Mer 09/Nov/2005 9:53
Messages: 4067
Ma contribution :
Code:
chaine$="POABCDEFTHLGDSALKL"

Dim c.b(90)

For i=1 To Len(chaine$)
  c(Asc(Mid(chaine$,i,1)))+1
  If c(Asc(Mid(chaine$,i,1)))>1
    Debug Mid(chaine$,i,1)
    End
  EndIf
Next


Aucune idee du temps qu'elle met... 8)

_________________
http://HexaScrabble.com/
!i!i!i!i!i!i!i!i!i!
!i!i!i!i!i!i!
!i!i!i!
//// Informations ////
Portable LENOVO ideapad 110-17ACL 64 bits
Version de PB : 5.70LTS - 32 bits


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Entretien d'embauche téléphonique chez Google
MessagePosté: Mer 28/Mar/2018 17:10 
Hors ligne
Avatar de l’utilisateur

Inscription: Lun 17/Déc/2007 12:44
Messages: 1635
La version de Nico simplifié ^^ (pour le première version, j'avais surement mal compris) :

Code:
EnableExplicit

Define.s temp, char = "POABCDEFTHLGDSALKL"
Define.l i, lpos, lmem = Len(char)

For i=1 To Len(char) - 1
  temp = Mid(char, i, 1)
  lpos = FindString(char, temp, i + 1)
  If lpos > 0 And lpos < lmem
    lmem = lpos
  EndIf
Next i
If lmem > 0
  Debug Mid(char, lmem, 1)
EndIf


Cordialement,
GallyHC

_________________
Image

Image

Image Official site of PureBasic
Image Official site of SpiderBasic

Configuration : Tower: Windows 10 (Processeur: i7 "x64") (Mémoire: 16Go) (GeForce GTX 760 - 2Go) - PureBasic 5.71 LTS (x86 et x64)


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Entretien d'embauche téléphonique chez Google
MessagePosté: Mer 28/Mar/2018 21:03 
Hors ligne
Avatar de l’utilisateur

Inscription: Lun 22/Nov/2004 13:05
Messages: 353
Non c'est pas le D c'est la A :mrgreen:
Code:
Chaine$="POABCDEFTHLGDSALKL"
For i = 1 To Len(Chaine$)
   txt$ = Mid(Chaine$, i, 1)
   a.a = CountString(Chaine$, txt$)
   If a= 2 : Debug txt$ : End : EndIf
Next i


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 1, 2, 3, 4, 5 ... 7  Suivante

Heures au format UTC + 1 heure


Qui est en ligne

Utilisateurs parcourant ce forum: Aucun utilisateur enregistré et 5 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 à:  

 


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