Melhores Entrevistas #2 – A lista tem os itens necessários para a soma ser igual a um número K?

Olá, tudo bem contigo?

Hoje, retomando a nossa série de posts sobre entrevistas de emprego em quadros brancos, algoritmos e estruturas de dados.

Neste post, nós vamos falar de um desafio que o nosso caro Henrique Bastos comentou em seu Instagram:

Dado uma lista de números e um número k, retorne se quaisquer dois números da lista somados resultam no número k.

Por exemplo, dado [10, 15, 3, 7] e k = 17, retorne verdadeiro, já que 10 + 7 = 17.

Extra: Passe pelos números da lista uma única vez.

Henrique Bastos

Então vamos resolver isso utilizando TDD e as boas práticas de código!

Bora codar!

Basicamente, neste desafio temos de achar um par de números que somem um valor igual ao número pré-definido.

Ou seja, dado a lista [10, 15, 3, 7], encontre os valores, que somados, dão 17.

Neste caso, só possuímos uma alternativa: 10 + 7

Então, uma boa forma de começarmos a codar isso é criando um teste unitário que permita com que avaliemos se o resultado da função dará certo:

from unittest import TestCase
from .desafio import acha_soma
class TesteDesafioHB(TestCase):
     def setUp(self):
         self.lista = [10, 15, 3, 7]

     def test_se_soma_eh_igual_a_17(self):
         self.assertTrue(acha_soma(17, self.lista))
         self.assertTrue(acha_soma(18, self.lista))
         self.assertFalse(acha_soma(19, self.lista))


Para você avaliar se existe esta soma basta utilizar fors encadeados, ou seja, um for dentro de um for, permitindo que utilizemos dois números ao mesmo tempo.

def acha_soma(soma, lista):
    for primeiro_n in lista:
        for segundo_n in lista:
            pass

Neste código acima, montamos nossa função acha_soma, onde recebemos o valor que queremos que seja comparado como soma e a lista de atributos.

Com estes fors, basta somarmos as variáveis primeiro_n e segundo_n para podermos e checarmos se seu valor é igual a busca procurada.

def acha_soma(soma, lista):
    for primeiro_n in lista:
        for segundo_n in lista:
            if (primeiro_n + segundo_n) == soma:
                pass

Com essa checagem no lugar, já podemos colocar os retornos e continuações de código, assim nosso teste passará!

def acha_soma(soma, lista):
    for primeiro_n in lista:
        for segundo_n in lista:
            if (primeiro_n + segundo_n) == soma:
                return True
            continue
    return False

Como você pode ver abaixo, os testes passaram com sucesso!

.
----------------------------------------------------------------------
Ran 1 test in 0.000s

OK

Agora vem a segunda parte

Anteriormente, nós vimos como fazer o desafio com dupla iteração na lista, mas existe uma maneira de se resolver este desafio com apenas uma iteração!

Para fazer esse desafio precisamos entender uma equação básica:

Primeiro Número da Iteração + Segundo Número da Iteração = Soma

Então podemos mudar o lugar do primeiro número, poderemos iterar somente uma vez, ficando:

Segundo Número da Iteração = SomaPrimeiro Número da Iteração

Neste caso, só faremos um for e utilizaremos de nossa nova equação que diz qual o segundo número, assim checamos se o número está na lista e retornamos o valor… Passando para código, ficaria:

def acha_soma(soma, lista):
    for numero in lista:
        segundo_numero = soma - numero
        if segundo_numero in lista:
            return True
    return False

Simples né?

O que achou de nosso desafio? Compartilhe com seus amigos e tente refazê-lo!

Para melhorar ainda mais o algoritmo

O Henrique Bastos, em seu Instagram, postou a seguinte solução:

def sum_pairs(k, nums):
    for i, n in enumerate(nums[:-1], start=1):
        for m in nums[i:]:
            if n + m == k:
                return True
    return False

A solução utiliza enumerate e list slicing para permitir maior eficiência nas N-1 iterações do algoritmo.

Basicamente ele pega um item da lista e todos a frente dele e itera!

Valeu HB pela sua resposta e pelo desafio!

PS: Este é realmente um desafio utilizado em entrevistas do Google.

Autor: Vinicius Mesel

Ex-desenvolvedor de sistemas para bancos de investimentos. Trabalhou com mesas de investimentos e áreas de atendimento a grandes riquezas automatizando processos com Python. Também atuou como pesquisador de bioinformática no Instituto Butantan e hoje é CEO da RecrutaDev.

3 comentários em “Melhores Entrevistas #2 – A lista tem os itens necessários para a soma ser igual a um número K?”

Deixe uma resposta

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *