6
\$\begingroup\$

I am practicing interview questions and have written the following code for the given task.

Task : Given a non-negative number represented as an array of digits, add 1 to the number (increment the number represented by the digits). The digits are stored such that the most significant digit is at the head.

Code:

class Solution:
# @param A : list of integers
# @return a list of integers
    def plusOne(self, A):
        Rev_A = A[::-1]
        i = 0
        while i <= len(A)-1:
            if Rev_A[i] != 9:
                Rev_A[i] +=1
                carry = 0
                break
            else:
                Rev_A[i] = 0
                carry = 1
            i += 1
        if carry == 1:
            Rev_A.append(1)
        while True:
            if Rev_A[-1]==0:
                Rev_A.pop()
            else:
                break
        return Rev_A[::-1]


    def __init__(self):
        self.list = []

Test cases:

if __name__ == "__main__":


    A = Solution()
    ## Test Cases   
    print A.plusOne([0])
    print A.plusOne([9,0,0])
    print A.plusOne([6,9,9])
    print A.plusOne([9,9,9])
    print A.plusOne([0,9,9,9])
    print A.plusOne([0,0,0,1,2,3])

How can this code be better?

\$\endgroup\$
  • \$\begingroup\$ @Ohh thats a mistake while adding the test cases. I will edit it \$\endgroup\$ – Latika Agarwal May 5 '18 at 6:16
13
\$\begingroup\$
  1. Run the code through pycodestyle, then understand and apply all of the recommended changes. This is tedious the first couple times, but you'll learn to write much more idiomatic Python.
  2. The class is pointless - you might as well just write a bare function instead. __init__ also creates a field which is then never used.
  3. Names like A make the code harder to read. Naming your variables what they actually are makes the code much easier to read.
  4. I would swap around your first if/else to avoid the negative comparison.
  5. You use a number for carry, but it might as well be boolean because it can never be more than 1.
  6. Personally I consider this code hard to understand. You reverse the list twice (making a copy both times), add and remove to it. This is my take on it:

    def increment(digits):
        for index, digit in reversed(list(enumerate(digits))):
            if digit == 9:
                digits[index] = 0
            else:
                digits[index] += 1
                return digits
        digits.insert(0, 1)
        return digits
    
    if __name__ == '__main__':
        print(increment([0]))
        print(increment([9,0,0]))
        print(increment([6,9,9]))
        print(increment([9,9,9]))
        print(increment([0,9,9,9]))
        print(increment([0,0,0,1,2,3]))
    
    1. Reverse the list one element at a time
    2. Set trailing nines to zero
    3. If any number is not nine, increment it and we're done
    4. If we get through the whole list, it must have been all nines, so we add a one to the start and return
    5. This code treats an empty list as zero, which may or may not be allowed in the exercise.
\$\endgroup\$
  • \$\begingroup\$ Thanks for your review. The class function was inbuilt with the console i was practising on, so i had to use. Yes, reversing the list twice was really inefficient.. \$\endgroup\$ – Latika Agarwal May 5 '18 at 15:10
  • \$\begingroup\$ Nice simplification of the increment algorithm! However you are both mutating and returning digit. I would recommend picking one. (and optionally renaming the function accordingly, like incremented if you choose to return a new list) \$\endgroup\$ – njzk2 May 5 '18 at 19:25
  • \$\begingroup\$ also, you don't necessarily need to create a list out of the enumerate (as that adds an expensive step right before starting to even loop). An alternative option would be to use for index in range(len(digits) -1, -1, -1) and then if digits[index] == 9... \$\endgroup\$ – njzk2 May 5 '18 at 19:29
3
\$\begingroup\$
  1. This while loop:
i = 0
while i <= len(A) - 1:
    ...
    i += 1

should just be a for loop:

for i in range(len(A)):
    ...

or:

for i, x in enumerate(A):  # x == A[i]
    ...
  1. Building on l0b0's suggestions 4 and 5:
carry = Rev_A[i] == 9  # or x == 9
if carry:
    Rev_A[i] = 0
else:
    Rev_A[i] += 1
    break
  1. This:
while True:
    if Rev_A[-1] == 0:
        Rev_A.pop()
    else:
        break

can be:

while Rev_A[-1] == 0:
    Rev_A.pop()
  1. The purpose of the above loop isn't clear. If the input has extra zeroes, why not let them be? You're doing something outside of the scope of the task, which takes time and increases the chances of errors, and which the user may not what. Maybe I want my 'numbers' to be sortable lexicographically.

  2. Descriptive variable names are good, but here you have so few and you repeat Rev_A so many times. Rather I would make both A and Rev_A just a. That includes writing a = a[::-1]. The reader will quickly learn what a is and doesn't need a long name to remind them.

  3. Write actual test cases that assert the output of the function is equal to something. Never require manual inspection of output to determine if tests passed.

  4. You've written comments instead of a docstring. Don't. Also describe parameters and return values more than just their types.

\$\endgroup\$
  • \$\begingroup\$ Thanks for your review. The extra zeroes were part of the input but had to be removed in the o/p. It was a variation in the test cases. \$\endgroup\$ – Latika Agarwal May 5 '18 at 15:15
1
\$\begingroup\$

The problem is well suited for recursion. I don't know if it is wise in an interview to metion quotes as: "to iterate is human, to recurse is divine" but recursion is a fun approach for this problem.

As l0b0 said a class is not needed for this case so i changed the method plusOne to a normal function.

def plusOne(a):
    return addOneToDigitsList(a, 1)

Where addOneToDigitsList is the following recursive function:

def addOneToDigitsList(a, pos):
    if pos > len(a):
        a.insert(0,0)
    if a[-pos] != 9:
        a[-pos] += 1
        return a
    else:
        a[-pos] = 0
        return addOneToDigitsList(a, pos + 1)

The remaining part is almost the same:

def main():
    ## Test Cases   
    print(plusOne([0]))
    print(plusOne([9,0,0]))
    print(plusOne([6,9,9]))
    print(plusOne([9,9,9]))
    print(plusOne([0,9,9,9]))
    print(plusOne([0,0,0,1,2,3]))

if __name__ == "__main__":
    main()
  • I added a main function because it is common to do so
  • I added parentheses to make it Python 3 compatible
  • I did not, but should have, used Alex Hall comments about docstrings.
  • I should have done more error checking (for unexpected situations)
\$\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.