5
\$\begingroup\$

I was given this coding challenge when a applying for a summer internship but didn't get selected for the next round and I was curious if it could be improved.

The problem says:

Given a number in base "-2" divide it by 2.

For example:

Given [1, 0, 0, 1, 1, 1] (-23) the output is [1, 0, 1, 0, 1, 1] (-11)

Given [0, 0, 1, 0, 1, 1] (-12) the output is [0, 1, 1, 1] (-6)

Note the array is read from left to right. [1, 0, 0, 1, 1, 1] = 1*(-2)^0 + 0*(-2)^1 + 0*(-2)^2 + 1*(-2)^3 + 1*(-2)^4 + 1 * (-2)^5 = 1 + 0 + 0 + (-8) + 16 + (-32) = -23

The easiest solution that I found was to convert the number to an integer, divide it by two and then convert it back to base -2.

Thanks in advance for your input.

My code in Python:

import math

# Main function
def solution(A):
    value = math.ceil(calculate_number(A) / 2)
    p = convert_number_to_binary(value)
    return p


# This function calculates the value of the list
def calculate_number(A):
    total = 0
    for i in range(0, len(A)):
        total += A[i] * (-2) ** i
    return total

# This function converts a number to base -2
def convert_number_to_binary(number):
    binary = []
    if number == 0:
        return binary

    while number != 0:
        number, remainder = divmod(number, -2)
        if remainder < 0:
            number += 1
            remainder -= -2
        binary.append(remainder)
    return binary

print(solution([1, 0, 0, 1, 1, 1]))
\$\endgroup\$
  • \$\begingroup\$ please add the context of how are you running the program \$\endgroup\$ – RomanPerekhrest Nov 25 '19 at 21:37
  • 2
    \$\begingroup\$ That is an arguably bad coding challenge for a summer internship; one wonders what signal they were attempting to extract from that challenge. Your solution seems quite straightforward; there are a few minor stylistic things I might change but the basic approach seems sound. I have given interview problems myself where the problem could be solved by transforming an unpleasant representation into a pleasant one, doing the work in the pleasant form, and then transforming back; it's a good technique that is applicable to real problems. \$\endgroup\$ – Eric Lippert Nov 25 '19 at 21:42
  • 1
    \$\begingroup\$ @EricLippert: Well, it tests if you understand the basic Python syntax, basic algorithms, know how to use functions and then if you know proper Python style. Not entirely useless IMO, depending on what you want to achieve... \$\endgroup\$ – Graipher Nov 26 '19 at 9:55
6
\$\begingroup\$

General

  • As per PEP 8 conventions, the variables in functions should be in lowercase.

  • Adding docstrings is recommended. PEP 257

  • Names should be short and meaningful. For example, convert_number_to_binary should actually be to_base_minus_two. Also, calculate_number should be from_base_minus_two

  • Use type hints

  • Instead of x == 0 python allows you to use use not x. Similarly, x != 0 can be replaced with x.

  • Envelop the main code inside if __name__ == '__main__':. This will prevent the code from being run if imported from another module.

  • Following @Martin R's advice, you can change -2 to a constant BASE

Function solution

value = math.ceil(from_base_minus_two(A) / 2)
p = to_base_minus_two(value)
return p

Can be replaced with the one liner:

return to_base_minus_two(math.ceil(from_base_minus_two(a) / 2))

Function from_base_minus_two

total = 0
for i in range(0, len(a)):
    total += a[i] * BASE ** i
return total

Instead, you can use:

return sum(j * BASE ** i for i, j in enumerate(a)))

Function to_base_minus_two

The value you are finding isn't exactly binary. Change it to base_minus_two

You don't need to use

if number == 0:
    return base_minus_two

Automatically, the while loop will terminate immediately as number is 0, and will return base_minus_two which is []


Here's what the final code might look like:

import math
from typing import List


BASE = -2


def from_base_minus_two(a: List[int]) -> int:
    """ Converts base 'BASE' to decimal """

    return sum(j * BASE ** i for i, j in enumerate(a))


def to_base_minus_two(number: int) -> List[int]:
    """ Converts decimal to 'BASE' """

    base_minus_two = []

    while number:
        number, remainder = divmod(number, BASE)

        if remainder < 0:
            number += 1
            remainder -= BASE

        base_minus_two.append(remainder)

    return base_minus_two


def solution(a: List[int]) -> List[int]:
    """

    * Converts from 'BASE' to decimal
    * Divides the decimal by 2
    * Converts the decimal back to 'BASE'

    """

    return to_base_minus_two(math.ceil(from_base_minus_two(a) / 2))


if __name__ == '__main__':
    print(solution([1, 0, 0, 1, 1, 1]))
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Re “remainder -= -2 can be replaced with remainder += 2”: I'd prefer the original version because it emphasizes the connection to the base -2. (Or better, remainder -= BASE using a constant definition). \$\endgroup\$ – Martin R Nov 26 '19 at 12:14
  • \$\begingroup\$ @MartinR Thanks for the idea. I've updated my code according to it \$\endgroup\$ – Sriv Nov 26 '19 at 16:32
4
\$\begingroup\$

A bug?

Here

value = math.ceil(calculate_number(A) / 2)

you use the ceil function, apparently to truncate the result dividing a negative number towards zero, so that, for example, -23 becomes -11. But for positive odd numbers this gives an unexpected result:

print(solution([1, 1, 1])) # 1 - 2 + 4 = 3

returns [0, 1, 1] = -2 + 4 = 2 where I would expect [1] = 1. If that line is replaced by

value = int(calculate_number(A) / 2)

then both positive and negative values are rounded towards zero. As a side-effect, the

import math

is not needed anymore.

Some small simplifications

The test

if number == 0:
    return binary

in convert_number_to_binary() is not needed: If the passed number is zero then the while loop will not execute.

The exponentiation in the conversion from binary to number can be avoided if the digits are processed in reverse order:

def calculate_number(A):
    total = 0
    for digit in reversed(A):
        total = (-2) * total + digit
    return total

And that can be compactly expressed as a reduce operation:

import functools

def calculate_number(binary):
    return functools.reduce(lambda total, digit: -2 * total + digit, reversed(binary))
| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

Python has docstrings to document your functions properly. Just move your comments there, as a first step.

In the calculate_number function (which I would rename to from_base_neg_2 or something similar) you can use a list comprehension (or even better, a generator expression):

def from_base_neg_2(A):
    """Calculate the value of a number in base -2,
       given as a list of coefficients, sorted from smallest exponent to largest.
    """
    return sum(a * (-2) ** i for i, a in enumerate(A))

Similarly, I would call the inverse function to_base_neg_2 or something like it.

Your main calling code should be under a if __name__ == "__main__": guard to allow importing from this module. Arguably the solution function should be defined last, since it depends on all the other functions and that makes it slightly easier to read.

def solution(A):
    """Main function.
    Divide A, a number in base -2, by 2.
    """
    return to_base_neg_2(math.ceil(from_base_neg_2(A) / 2))

if __name__ == "__main__":
    print(solution([1, 0, 0, 1, 1, 1]))
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.