Amazon Interview Question
Software Engineer / DevelopersYou need to define your own data type for large numbers. Something like BigInteger type in Java. 100! has upto 150 digits. So an array of size 200 is enough to store the result. So store one decimal digit per array index. However you need to write your multiplication algorithm for multiplying two large numbers.
Make 2 arrays , array1 is initialized to 100 ie each digit of 100 is stored in different locations of array1.
Array2 in initialized to 99 ie each digit of 99 is stored in different location of array2
now multiply each digit of array1 with each digit of array2. This multiplication is identical to the multiplication that we were taught in school. Time complexity of this type of multiplication is O(n2)
assuming that the function is correct, store the number as byte array, where each memory location is 1 byte for 1 number location.
- Amit September 11, 2009