Category: algorithms

The algorithm is necessary for a coding interview for a data scientist and a software engineering job. This article’s topic is one of the most important subjects.

Problem

Write a function to judge if a number is prime, where a prime number is a natural number greater than or equal to 2, whose positive divisor is 1 and itself. The function returns True if the number is prime, or returns False otherwise.

Solution

This solution is a simple approach without any specific mathematical knowledges. The approach consists three steps as follows.

1. Check the special case.
   From the definition of a prime number, 1 is NOT a prime number. And, 2 is the only prime number among even numbers.
2. An even number is NOT a prime number.
3. Judge against odd numbers.
   In turn, we will check the condition if a number exists whose remainder is zero, it is not a prime number. Note that, using prior knowledge that the number is not even, it is sufficient to examine only odd numbers.

def is_prime(num):
    # check the special case,
    # 1 is NOT a prime number,
    # the only prime number 2 in even numbers.
    if num <= 1:
        return False
    elif num == 2:
        return True
    
    # even number is a False case
    if num % 2 == 0:
        return False

    # Only checking on odd numbers is sufficient.
    for i in range(3, num, 2):
        if num % i == 0:
            return False
    return True

Test examples

nums = list(range(2, 15))
for n in nums:
    print(f"{n}: {is_prime(n)}")

>  2: True
>  3: True
>  4: False
>  5: True
>  6: False
>  7: True
>  8: False
>  9: False
>  10: False
>  11: True
>  12: False
>  13: True
>  14: False

As a comment, using mathematical knowledge of integers, it is also possible to implement a solution with a more efficient computational complexity.

The algorithm is necessary for a coding interview for a data scientist and a software engineering job. This article’s topic is one of the most important subjects.

Problem

Write a function to return True if there exists a pair of numbers whose summation equals the given target number, or to return False otherwise. You may assume that an element in a list is an integer.

Solution – Normal Approach

This solution is a simple approach, but not a computationally efficient method. Time Complexity is $O(N^2)$.

The method examines all the sums of two list elements in sequence to determine if they contain the desired result.

def two_sum(nums, target):
    """
    Time Complexity O(N^2)

    Args:
        nums(list): a list of an integer number
        target(int): target-integer number
    """
    for i in range(len(nums)):
        for j in range(len(nums)):
            if i != j and target == nums[i] + nums[j]:
                return True
    return False

Test examples

assert two_sum([10, 2, 3, 1], 5) == True
assert two_sum([1, 2, 3, 4], 1) == False

Solution – Better Approach

This solution is an improved approach, then the Time Complexity is $O(N)$!

The key concept is as follows. First, we choose one element in each iteration. As a result, we can determine the desired element from the “target number – one element”. Second, we check whether the desired element exists in a cache, where the cache is a list containing elements examined in iterations already performed.

By repeating the above procedures, it is possible to determine whether a desired pair of elements is included in the list.

def two_sum(nums, target):
    """
    Time Complexity O(N)

    Args:
        nums(list): a list of an integer number
        target(int): target-integer number
    """
    cache = set()
    for n in nums:
        ans = target - n
        if ans in cache:
            return True
        else:
            cache.add(n)
    return False

Test examples

assert two_sum([10, 2, 3, 1], 5) == True
assert two_sum([1, 2, 3, 4], 1) == False

Appendix: The case that the indices of numbers are required

Problem

Write a function to return the indices of the two numbers whose summation equals the given target number, or to return False otherwise. You may assume that an element in a list is an integer.

Solution

In this case, we should use a hash map, i.e., the dictionary in Python. The concept of a solution is the same as above. However, we have to store the indices of each number.

def two_sum(nums, target):
    cache = {}
    for i, n in enumerate(nums):
        ans = target - n
        if ans in cache:
            return (cache[i], i)
        else:
            cache[n] = i
    return False

Test examples

assert two_sum([10, 2, 3, 1], 5) == (1, 2)
assert two_sum([1, 2, 3, 4], 1) == False