quarta-feira, 13 de novembro de 2019

Java Code Duel #3 - Find common elements!


#engenhariaDeSoftware #algoritmos #java #collection #stream #codeDuel #oBomProgramador

O desafio era: Encontrar a interseção entre dois vetores de inteiros, com a limitação  de não repetir os números comuns. E foi dito que você nada poderia assumir quanto à classificação, unicidade e tamanho dos vetores.




E agora? Imagina isso em um code challenge de entrevista de emprego!


Uma abordagem naive seria: classificar um dos vetores e criar um algoritmo iterativo. Ok. Vamos ver isso. A primeira coisa seria pegar um dos vetores e classificar. Como você faria isso? Criaria um algoritmo de bubble sort? Se conhece Java, sabe da classe Arrays:

private static int [] findCommons(int[] a, int[] b) {
Arrays.sort(a);
Set<Integer> aSet = IntStream.of(a).boxed().collect(Collectors.toSet());
Set<Integer> bSet = IntStream.of(b).boxed().collect(Collectors.toSet());
List<Integer> output = new ArrayList<Integer>();
for (Integer el : bSet) {
if(aSet.contains(el)) {
output.add(el);
}
}
int [] arrOut = new int[output.size()];
return output.stream().mapToInt(i->i).toArray();
}

Uau! O que é isso? Eu transformei os vetores em Sets, eliminando as duplicidades, e rodei uma comparação iterativa. Depois, transformei a lista que criei em vetor de inteiros.

Esta é mais uma demonstração do poder da stream API. Para transformar o vetor de "int" em um Set de Integer, usei o IntStream, que cria um stream de inteiros a partir de um vetor, depois usei o map boxed, que empacota as variáveis em instâncias das wrapper classes. Finalmente, coletei como Set.

Para transformar uma lista de Integer em um vetor de "int" usei o processo contrário, com um map de Integer para "int" e transformando em um vetor.

Essa é a beleza da stream API.

Agora, é a melhor implementação? Certamente que não. No pior caso, é ordem O(n).

Estude e conheça as APIs da linguagem!

Eu tenho várias certificações Java. Algumas pessoas dizem que é bobagem, pois decoreba em nada ajuda. Eu discordo. Ajuda sim! Ajuda a conhecer a API da linguagem. E a Collection API tem coisas muito mais interessantes, como o método "retainAll()" da classe "Set". Veja só essa segunda implementação:

static int [] findCommons2 (int [] a, int [] b) {
    Set<Integer> setA = IntStream.of(a).boxed().collect(Collectors.toSet());
    Set<Integer> setB = IntStream.of(b).boxed().collect(Collectors.toSet());
    setB.retainAll(setA);
    return setB.stream().mapToInt(i -> i).toArray();
}

Virou programação funcional! O método "retainAll()" faz isto: retém apenas os elementos comuns!

Para testar:

public static void main(String[] args) {
int [] a = {4,7,8,10,11,12,20,25};
int [] b = {1,5,7,7,13,2,9,8,30,35,20,15};
System.out.println(Arrays.toString(findCommons(a,b)));
System.out.println(Arrays.toString(findCommons2(a,b)));
}


Até o próximo codeDuel!

Cleuton Sampaio, M.Sc.




Nenhum comentário:

Postar um comentário