Google Interview Question
Software DevelopersCountry: United States
Interview Type: Phone Interview
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
#define DIGITS 50
// Write a class to take in a large arbitrary number, also provide a function to increment the number.The number will be passed on as an array of integers.
// 1. Accept large number as string
// 2. Copy each digit into array of integers with one digit in each int (preferred to push number to end of array)
// 3. Create function to increment mega integer array
class LargeNumber {
public:
LargeNumber();
void printMegaIntArr();
void incrementMegaIntArr();
private:
string entry;
int arrOfNums[DIGITS];
};
int main()
{
LargeNumber largeNumber;
largeNumber.printMegaIntArr();
largeNumber.incrementMegaIntArr();
largeNumber.incrementMegaIntArr();
largeNumber.printMegaIntArr();
cout << endl << endl;
system("pause");
return 0;
}
LargeNumber::LargeNumber()
{
memset(arrOfNums, 0, sizeof(arrOfNums));
cout << "Enter a large number and press enter:";
cin >> entry;
// Return if string is empty otherwise save first character
if (!entry.empty()) {
char tmpChar = entry[0];
int j = (DIGITS - entry.size());
for (int n = 0; tmpChar != NULL; n++, j++) {
arrOfNums[j] = int(tmpChar - '0');
cout << "Inserting: " << arrOfNums[j] << " at j =" << j << endl;
tmpChar = entry[n + 1];
}
}
}
// Increment the Mega Array of numbers
void LargeNumber::incrementMegaIntArr()
{
int tmpNum = 0;
for (int n = DIGITS -1 ; ; n--) {
tmpNum = arrOfNums[n] + 1;
if (tmpNum < 10) {
arrOfNums[n] = tmpNum;
return;
}
else {
arrOfNums[n] = 0;
}
}
}
// Print the Mega Array of numbers
void LargeNumber::printMegaIntArr()
{
for (int n = 0; n < DIGITS; n++) {
cout << arrOfNums[n];
}
cout << endl << endl;
}
Assumptions:
- use a binary representation in contrast to decimal
- do it portable (32, 64 bit)
- number can grow to no limit, except memory ...
- output has hex is sufficient
- only deal with unsigned representation
- only integers, since they are passed as integer-array
#include <iostream>
#include <vector>
#include <limits>
using namespace std;
class LargeNumber;
ostream& operator << (ostream& os, const LargeNumber& ln);
class LargeNumber
{
friend ostream& operator << (ostream& os, const LargeNumber& ln);
public:
using dtype = unsigned int;
private:
vector<dtype> _data; // in "little endian": (data[0]^1, data[1]^(sizeof(dtype)*8), ...
public:
LargeNumber(initializer_list<dtype>&& data) : _data(data) {}
LargeNumber& operator ++()
{
size_t i = 0;
bool overflow = true;
while (overflow && i < _data.size())
{
_data[i]++;
overflow = _data[i] == 0;
i++;
}
if (overflow)
{// grow
_data.resize(_data.size() + 1);
_data[i] = 1;
}
return *this;
}
};
int main()
{
constexpr auto uintm = std::numeric_limits<LargeNumber::dtype>::max();
LargeNumber n1({ 0 });
LargeNumber n2({ uintm });
LargeNumber n3({ uintm - 3, uintm, });
cout << "n1 " << n1 << endl;
cout << "++n1 " << ++n1 << endl;
cout << "++n1 " << ++n1 << endl;
cout << "n2 " << n2 << endl;
cout << "++n2 " << ++n2 << endl;
cout << "++n2 " << ++n2 << endl;
cout << "n3 " << n3 << endl;
cout << "++n3 " << ++n3 << endl;
cout << "++n3 " << ++n3 << endl;
cout << "++n3 " << ++n3 << endl;
cout << "++n3 " << ++n3 << endl;
getchar();
}
ostream& operator << (ostream& os, const LargeNumber& ln)
{
constexpr auto nc = sizeof(LargeNumber::dtype) * 2; // nible count per int
bool lz = true; // leading zero
size_t i = ln._data.size()*nc;
while (i > 0)
{
--i;
auto sr = (i%nc) * 4;
auto v = (ln._data[i / nc] >> sr) & 0xf;
if (v != 0 || !lz)
{
cout << hex << v;
lz = false;
}
}
return os;
}
/* output
n1
++n1 1
++n1 2
n2 ffffffff
++n2 100000000
++n2 100000001
n3 fffffffffffffffc
++n3 fffffffffffffffd
++n3 fffffffffffffffe
++n3 ffffffffffffffff
++n3 10000000000000000
*/
Would this be similar to a BigInteger addition in Java.
public class bigInteger {
public static BigInteger add(BigInteger one, BigInteger two){
byte big [];
byte small[];
if(one.toByteArray().length > two.toByteArray().length){
big = one.toByteArray();
small = two.toByteArray();
}
else if(one.toByteArray().length < two.toByteArray().length){
small = one.toByteArray();
big = two.toByteArray();
}
else {
big = one.toByteArray();
small = two.toByteArray();
}
byte result[] = new byte[small.length+big.length];
int carry=0;
for(int i=0;i<big.length;i++){
int digit2 = i>=small.length?0:small[i];
int sum = big[i]+digit2+carry;
carry = (byte)( sum > 9?1:0);
result[i] = (byte)(sum % 10);
}
result[big.length]= (byte)carry;
return new BigInteger(result);
}
}
Here`s solution for positive big numbers. It`s a pretty simple solution with one problem: a large number of expended memory. It can be improved by using all bits of integers in array.
import java.util.ArrayList;
import java.util.ListIterator;
public class LargeNumber {
public static void main(String[] args) {
LargeNumber largeNumber = new LargeNumber("999999999999999999999999999999999999999999999999999999999999999999912321321399");
System.out.println(largeNumber.toString());
largeNumber.increment();
System.out.println(largeNumber.toString());
}
private ArrayList<Integer> buffer;
public LargeNumber(String largeNumber) {
buffer = new ArrayList<>();
for (int i = largeNumber.length() - 1; i >= 0; i--) {
buffer.add(Integer.parseInt(String.valueOf(largeNumber.charAt(i))));
}
}
public void increment() {
add(0, 1);
}
private void add(int position, int addValue) {
Integer curValue = buffer.get(position);
buffer.set(position, (curValue + addValue) % 10);
int residue = (curValue + addValue) / 10;
if (residue > 0) {
int nextPosition = position + 1;
if (nextPosition < buffer.size()) {
add(nextPosition, residue);
} else {
buffer.add(1);
}
}
}
@Override
public String toString() {
StringBuilder stringBuilder = new StringBuilder();
ListIterator<Integer> backIterator = buffer.listIterator(buffer.size());
while(backIterator.hasPrevious()) {
stringBuilder.append(backIterator.previous());
}
return stringBuilder.toString();
}
}
Simple python solution:
class LargeNumber():
str = None
numbers = None
def __init__(self, large_number):
self.str = large_number
self.numbers = [int(s) for s in large_number.split()]
def print_me(self):
print (''.join([str(n) for n in self.numbers]))
def inc_val(self):
for i, n in enumerate(self.numbers):
if n == 9:
self.numbers[i] = 0
else:
self.numbers[i] += 1
break
l = LargeNumber("0")
l.print_me()
l.inc_val()
l.print_me()
l.inc_val()
l.print_me()
l = LargeNumber("999999999999")
l.print_me()
l.inc_val()
l.print_me()
l.inc_val()
l.print_me()
class LargeNumber():
str = None
numbers = None
def __init__(self, large_number):
self.str = large_number
self.numbers = [int(s) for s in large_number.split()]
def print_me(self):
print (''.join([str(n) for n in self.numbers]))
def inc_val(self):
for i, n in enumerate(self.numbers):
if n == 9:
self.numbers[i] = 0
else:
self.numbers[i] += 1
break
l = LargeNumber("0")
l.print_me()
l.inc_val()
l.print_me()
l.inc_val()
l.print_me()
l = LargeNumber("999999999999")
l.print_me()
l.inc_val()
l.print_me()
l.inc_val()
l.print_me()
public static void main(String []args) {
// input is an integer array - i can read it
int []array = input;
System.out.println("Incremented Number : " + outputArray(array));
}
public static int[] outputArray(int []inputArray) {
if(inputArray == null) return inputArray;
int arrLength = inputArray.length();
// check for all 9s
boolean all9s = true;
for(int i=0;i<arrLength && all9s;i++) { // 0(k) --> k is the first non 9
if(all9s && inputArray[i] == 9) {
all9s = true;
} else {
all9s = false;
}
}
if(all9s) {
int []newInputArray = new int[arrLength+1];
newInputArray[0] = 1; // 0(1)
for(int i=1;i<newInputArray;i++) { // 0(n)
newInputArray[i] = 0;
}
return newInputArray;
} else {
for (int i = arrLength-1; i > -1;i --) { // O(k+1) where is the first non 9
int k = inputArray[i];
if(k == 9) {
inputArray[i] = 0;
} else {
inputArray[i] = k++; // o(1)
return inputArray;
}
}
}
}
public class LargeInteger {
private List<Integer> number;
public LargeInteger(int [] array) {
this.number = new ArrayList<>();
for (int i = array.length-1; i >= 0; i--) {
this.number.add(array[i]);
}
}
public void increment() {
for (int i = 0; i < this.number.size(); i++) {
if (this.number.get(i) < 9) {
this.number.set(i, this.number.get(i) + 1);
return;
} else {
this.number.set(i, 0);
}
}
this.number.set(this.number.size()-1, 0);
this.number.add(1);
}
@Override
public String toString() {
StringBuilder buf = new StringBuilder();
buf.append("Large Integer").append('\n');
for (int i = this.number.size()-1; i >= 0; i--) {
buf.append(this.number.get(i));
}
return buf.toString();
}
}
- Sunil June 20, 2016