Алгоритмическая задачка 6.2.2019

1. Problem
2. Solution

1 Problem

This problem was recently asked by Google.

Given a list of numbers and a number k, return whether any two numbers from the list add up to k.

For example, given [10, 15, 3, 7] and k of 17, return true since 10 + 7 is 17.

Bonus: Can you do this in one pass?

2 Solution

def solution(l, k):
    """
    Whether any two numbers from the lst add up to num.
    Assume that there are no elements in l that are bigger than k.
    Assume that all elements in l are non-negative.

    :param list l: list of integers
    :param int k: seeked result of sum
    :return: True when there are such numbers, False otherwise
    :rtype: bool
    """
    additions = [None] * (k+1)
    for n in l:
        add = k - n
        if additions[add] is not None:
            return True
        additions[n] = n
    return False


test_data = (
    ([10, 15, 3, 7], 17, True),
    ([10, 15, 4, 8], 17, False),
    ([], 20, False),
    ([1], 1, False),
    ([1, 2], 3, True),
    ([1, 2, 3, 4, 5], 8, True)
)

for l, k, res in test_data:
    temp = solution(l, k)
    assert temp == res, '{} | {} -> {} <- {}'.format(l, k, temp, res)
print("ALL TESTS WERE PASSED")

ALL TESTS WERE PASSED

Алгоритмическая задачка 6.2.2019

Table of Contents

1 Problem

2 Solution