Goldman Sachs Questions Q 1

From Software Engineers Wiki
Jump to: navigation, search

We have a very big number which our datatypes does not provide. We need to multiply such numbers, how to do?

Answer

For arithmetic, little-endian format is easier to operate, because the carry can be moved toward right, and there is no need to shift the array when the carry happens. Following python code performs multiplication of two arbitrary numbers.

def arr_reverse(arr):
        left = 0
        right = len(arr) - 1;
        while (left < right):
                arr[left], arr[right] = arr[right], arr[left]
                left += 1
                right -= 1

def arr_set(arr, index, value):
        if (len(arr) <= index):
                arr.append(value)
        else:
                arr[index] = value

def multiply(a_arr, b_arr):
        arr_reverse(a_arr)
        arr_reverse(b_arr)
        r_arr = []

        for i in range(0, len(a_arr)):
                carry = 0
                j = 0
                while (j < len(b_arr)):
                        val = a_arr[i] * b_arr[j] + carry
                        if (len(r_arr) <= i + j):
                                r_arr.append(0)
                        val += r_arr[i + j]
                        carry = val / 10
                        val %= 10
                        r_arr[i + j] = val
                        j += 1

                if (carry):
                        arr_set(r_arr, i + j, carry)

        arr_reverse(a_arr)
        arr_reverse(b_arr)
        arr_reverse(r_arr)
        return r_arr

Test program:

def main():
        num_a = [ 1, 2, 3, 4, 5 ]
        num_b = [ 6, 7, 8, 9, 0, 1 ]
        num_m = multiply(num_a, num_b)
        print("{0} x {1} = {2}".format(num_a, num_b, num_m))

main()

Test result:

[1, 2, 3, 4, 5] x [6, 7, 8, 9, 0, 1] = [8, 3, 8, 1, 0, 3, 2, 8, 4, 5]

Reference

http://www.careercup.com/question?id=4849846286548992

Personal tools
Namespaces

Variants
Actions
Navigation
Toolbox