Jump to content
pedrix21

Desafio para programador C/C++ ( oferta de emprego)

Recommended Posts

pedrix21

Boas pessoal, esta no netEmprego e encontrei isto :P

Um desafio para o pessoal ;)

#define N    (1 << 25)
#define F(a,b)  { (a) ^= (b); (b) ^= (a); (a) ^= (b); }

uint32_t d[N];

int main(void)
{
   uint64_t h, i, j;

   for (i = 1; i < N; i++)
       d[i] = d[i-1] * 69069 + 1;

   for (i = 0; i < N; i++)
       for (j = 1; j < N; j++)
           if (d[j] < d[j-1])
               F(d[j-1], d[j])

   h = 0;

   for (i = 0; i < N; i++)
       h = h * 13 + d[i];

   h ^= 0x8678ADF24D4F64EFULL;

   printf("Please, mail your CV to %8.8s@grupopie.com\n", &h);

   return 0;
}

Ver Oferta de Emprego: http://www.net-empregos.com/1164427/desafio-para-programador-c/#ixzz1BjGlma3a

www.net-empregos.com - O maior site português de ofertas de emprego


@Pedro Lopes

Share this post


Link to post
Share on other sites
Triton

Então, mais ninguém consegui resolver?

Como já passou algum tempo e me pediram como explicar aqui fica:

SPOILER ALERT (Não ler o resto se querem tentar resolver):

A primeira coisa que devem fazer é compilar o código. Adicionar os devidos includes necessários. Depois reparar que o código implementa um LCG, um algoritmo simples para geração de números pseudo-aleatórios, embora mesmo sem reconhecer o algoritmo desse para resolver.

Depois meti uns prints antes e depois dos loops (podem mudar o valor de N para facilitar este passo). Vão reparar que um loop ali no meio está a ordenar o array da pior maneira possível. Basicamente a macro F é um in-place XOR swap. Substituam por um algoritmo eficiente para ordenação de números como radix sort ou qsort, et voilá.


<3 life

Share this post


Link to post
Share on other sites
selicerin

Em primeiro lugar peço desculpa por reavivar este tópico, mas nao fazia muito sentido criar um exactamente igual.

Estou a aprender C/C++ e dei com este anuncio por acaso (e uma pesquisa no google direccionou-me para aqui). Fiz o sugerido no post anterior, alterar o algoritmo de ordenação, mas o resultado que obtenho é uns caracteres estranhos (pontos de interrogação com fundo preto e por aí).

Nao estou interessado em responder ao anuncio, é apenas por curiosidade, mas agradecia se alguem me pudesse dar uma ajuda no porque de os prints saírem estranhos

Share this post


Link to post
Share on other sites
Triton

Se bem me lembro é mesmo só fazer o que disse em cima que se chegava à reposta facilmente, mas como já passou tanto tempo já não me lembro de detalhes concretos.


<3 life

Share this post


Link to post
Share on other sites
cffm

Boas

Estive a ver o exemplo e não percebi bem qual o objectivo do desafio, isto é, o que têm de fazer para o terminar?

Share this post


Link to post
Share on other sites
Warrior

Acho que isso é parte do desafio, mas o objectivo é descobrires para que mail enviar o currículo

Share this post


Link to post
Share on other sites
soniculture

eu tenho um problema com este código!

Implementei o qsort direitinho mas no printf tenho problemas :cheesygrin:

aqui vai o warning:

warning: format '%8.8s' expects type 'char *', but argument 2 has type 'uint64_t *'

estou a utilizar o xcode!

Obrigado ;)

Share this post


Link to post
Share on other sites
pmg

eu tenho um problema com este código!

Implementei o qsort direitinho mas no printf tenho problemas :cheesygrin:

aqui vai o warning:

warning: format '%8.8s' expects type 'char *', but argument 2 has type 'uint64_t *'

O codigo original tem muitas coisas que podem ser melhoradas. Uma delas e o abuso do tipo "uint64_t" na impressao.

O que se passa e que o valor final da variavel h vai ser qualquer coisa como "0x4142434445464748" que pode ser uma representacao da string "HGFEDCBA" (em formato little-endian).

No codigo original eles passam o endereco desse valor para o printf e tudo funciona como esperado, embora seja errado.

Podes fazer um cast e esperar que continue a funcionar (se funciona sem cast, tambem funciona com cast), mas mesmo com o cast continua a ser errado.

    printf("Please, mail your CV to %8.8s@grupopie.com\n", (char*)&h);

ou isolas cada elemento do valor e imprime-lo isoladamente

    printf("Please, mail your CV to ");
    putchar((h >> 0) & 0xFF);
    putchar((h >> 8) & 0xFF);
    putchar((h >> 16) & 0xFF);
    putchar((h >> 24) & 0xFF);
    putchar((h >> 32) & 0xFF);
    putchar((h >> 40) & 0xFF);
    putchar((h >> 48) & 0xFF);
    putchar((h >> 56) & 0xFF);
    printf("@grupopie.com\n");


What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

Share this post


Link to post
Share on other sites
soniculture

Fiz debug do qsort e ele ordena o array mas como que troca a parte direita com a esquerda!

Por exemplo o d[0] deveria ser o d[50] e vice-versa!

É normal o qsort fazer isto?

Concordo contigo com o abuso do int64_t... nem percebo qual a necessidade!

Deixo-te o meu código:

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <inttypes.h>

#define N 100

uint32_t d[N];

int sort(const void *x, const void *y)

int main (void) {

uint64_t i,h;
char palavra[64];

d[0]=0;

for (i=1;i<N;i++){
	d[i]=d[i-1]*2+1;
	printf("%u\n",d[i]);
	getchar();
}

qsort(d,N,sizeof(int32_t),sort);

for (i=0;i<N;i++){
	printf("i= %llu, d[i] = %lu\n",i,(long unsigned int)d[i]);

}


h=0;
for (i=0;i<N; i++) {
	h=h*13+d[i];
}

        h ^=0x8678ADF24D4F64EFULL;

printf("%8.8s",(char*)&h);

return 0;
}

int sort(const void *x, const void *y) {
return (*(int32_t*)x - *(int32_t*)y);
}

Share this post


Link to post
Share on other sites
soniculture

Cheguei a este resultado:

c\216\362\253 \316\334@grupopie.com

é possível?

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <inttypes.h>

#define N (1<<25)

uint32_t d[N];

int sort(const void *x, const void *y) {
return (*(int32_t*)x - *(int32_t*)y);
}

int main (void) {

uint64_t i,h;
uint32_t temp=0;

d[0]=0;

for (i=1;i<N;i++){
	d[i]=d[i-1]*69069+1;
	//printf("i= %llu, d[i] = %lu\n",i,(long unsigned int)d[i]);
	}

qsort(d,N,sizeof(int32_t),sort);

for (i=0;i<(N/2);i++){
	temp=d[i];
	d[i]=d[i+N/2];
	d[i+N/2]=temp;
}

h=0;
for (i=0;i<N; i++) {
	h=h*13+d[i];
}

h ^=0x8678ADF24D4F64EFULL;

printf("Please, mail your CV to %8.8s@grupopie.com\n", (char*)&h);

return 0;
}

Share this post


Link to post
Share on other sites
pmg

Cheguei a este resultado:

c\216\362\253 \316\334@grupopie.com

é possível?

A tua funcao de comparacao tem 1 bug ...

Estas a converter de "uint32_t" para "int32_t" e a subtrair os valores com sinal.

Na versao original, nao ha conversao.

Por exemplo, se os valores originais fossem "x = 0xFFFFFFFF" e "y = 0x00000001", x e maior que y ... mas depois de convertido para valor com sinal "x = -1" e "y = 1" e x NAO e maior que y.

Alem disso o codigo original assume uma implementacao com valores "little endian". Nao sei como se porta a tua implementacao, mas tem atencao a este ponto!


What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

Share this post


Link to post
Share on other sites
soniculture

Já alterei :)

o resultado dá o mesmo!

penso q se alterar a opção do printf para %1.1 chego a c@grupopie.com!

q achas?

Share this post


Link to post
Share on other sites
pmg

Se so mudaste os casts, continuas a ter problema na funcao de comparacao ...

Supoe que "x" e "y" sao respectivamente 1 e 2. Quando subtrais um do outro (1 - 2) com valores de tipo "uint32_t" ("unsigned") o resultado e 4294967295. Se o "int" no teu computador for de 32 bits (faz "#include <limits.h>" e ve "sizeof (int) * CHAR_BIT") a conversao deste valor para tipo "int" nao e fiavel (mas provavelmente da o resultado esperado -1); se o "int" for de 64 bits, o resultado e um valor positivo ... indicando que 1 e maior que 2!!!!

Alem disso, depois de compores a funcao de comparacao, precisas de remover a parte do codigo que troca as metades do array.


What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

Share this post


Link to post
Share on other sites
soniculture

O código que fiz foi:

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>

#define N (1<<25)

uint32_t d[N];

int sort(const void *x, const void *y) {
return (*(uint32_t*)x - *(uint32_t*)y);
}

int main (void) {

uint64_t i,h;
uint32_t temp=0;

d[0]=0;

for (i=1;i<N;i++){
	d[i]=d[i-1]*69069+1;
	}

qsort(d,N,sizeof(uint32_t),sort);

for (i=0;i<(N/2);i++){
	temp=d[i];
	d[i]=d[i+N/2];
	d[i+N/2]=temp;
}


h=0;

for (i=0;i<N; i++) {
	h=h*13+d[i];
}
h ^=0x8678ADF24D4F64EFULL;


printf("Please, mail your CV to %8.8s@grupopie.com\n", (char*)&h);

	getchar();

return 0;
}

Estás a dizer que tenho que mudar o tipo que devolve a função, certo?

Ou seja uint32_t sort(const void *x, const void *y) 

Share this post


Link to post
Share on other sites
pmg

Nao! A funcao tem que ter o prototipo "int foo(const void *, const void *);" senao pode dar faisca com o "qsort".

O que tens a fazer e nao misturar alhos com bugalhos ... OH! ... nao misturar numeros "signed" e "unsigned".

int sort(const void *x, const void *y) {
  const uint32_t *xx = x;
  const uint32_t *yy = y;
  if (*xx < *yy) return -1;
  if (*xx > *yy) return 1;
  return 0;
}


What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

Share this post


Link to post
Share on other sites
soniculture

Exacto :)

Aquela ciclo para dividir o array a meio era pq a ordenação estava partida.

funciona direitinho!

Obrigado :P

Share this post


Link to post
Share on other sites
cffm

Boas

Estava a tentar resolver com base no que foi dito pelo @pmg mas dá-me erro na conversão const void*' to const uint32_t*

O que será?

int sort(const void *x, const void *y) {
  const uint32_t *xx = x;
  const uint32_t *yy = y;
  if (*xx < *yy) return -1;
  if (*xx > *yy) return 1;
  return 0;
}

Agradeço a ajuda!

Share this post


Link to post
Share on other sites
pmg

A linguagem C++ e diferente da linguagem C. O meu codigo foi feito em C, mais propriamente C99.

Para funcionar em C++ precisa de ser convertido ... e eu nao sei C++

Experimenta assim

int sort(const void *x, const void *y) {
  const uint32_t *xx = (const uint32_t *)x;
  const uint32_t *yy = (const uint32_t *)y;
  if (*xx < *yy) return -1;
  if (*xx > *yy) return 1;
  return 0;
}


What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

Share this post


Link to post
Share on other sites
cffm

Boas

Obrigado pela ajuda. Eu também apenas sei C e C#, mas gostava de resolver isto em C++ porque estou a tentar batalhar um bocado nesta linguagem. Vou ver se consigo por a funcionar em C++.

Mais uma vez obrigado.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.