Google Interview Question for Software Developers


Country: United States
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
1
of 1 vote

// BigNumber.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <vector>
class BigNumber {
public :
    BigNumber(const std::vector<char> & input);
    void increment();
    void print();
private:
    std::vector<int> _digits;
};

BigNumber::BigNumber(const std::vector<char> &input){
    std::vector<char>::const_iterator itr = input.cbegin();
    while(itr != input.cend()){
        _digits.push_back(*itr - '0');
        ++itr;
    }
}

void BigNumber::increment(){
    std::vector<int>::reverse_iterator itr = _digits.rbegin();
    int carry = 0;
    do{
        if(itr == _digits.rend()) {
            _digits.insert(_digits.begin(),1);
            break;
        }
        (*itr)++;
        if(*itr > 9){
            *itr = 0;
            carry = 1;
        } else {
            carry = 0;
        }
        ++itr;
    } while(carry);
}

void BigNumber::print(){
    std::vector<int>::const_iterator itr = _digits.cbegin();
    while(itr != _digits.cend()){
        printf("%d", *itr);
        ++itr;
    }
}

int _tmain(int argc, _TCHAR* argv[])
{
    char input1[] =  {'9','9','9','9','9','9','9','9','9','9','9','9','9','9','9','9','9','9'};
    std::vector<char> input(&input1[0], &input1[0] + 18);
    BigNumber bigNumber(input);
    bigNumber.print();
    printf("\n");
    bigNumber.increment();
    bigNumber.print();
    getchar();
	return 0;
}

- Sunil June 20, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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;
}

- nedh84 June 17, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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
*/

- Chris June 17, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
    }
}

- wolfengineer June 17, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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();
    }
}

- r.nyukhalov June 18, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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()

- Nikolay June 19, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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()

- nfokin June 19, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

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;
            }
        }
    }
    
    
}

- coder145 June 21, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

number=["1","2","4","9"]
def increment(number):
    carry=1
    for i in range(len(number),0,-1):
        value=int(number[i-1])+carry
        carry=0
        if(value==10):
            number[i-1]=0
            carry=1
        else:
            number[i-1]=value
        if(carry==0):
            break;
    if(carry==1):
        number="1"+number
    return number
        
print increment(number)

- Karthik Narayanan June 25, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void incNum(vector<int> numArr)
{
int carry =1; 
for(int i=0; i<numArr.size() && carry ==1; i++)
{
	if(carry==1 && numArr[i] < INT_MAX)
	{	
		++numArr[i]; 
		carry=0; 
	}
}
if(carry = = 1)
{
	numArr[i] = 1;
	carry = 0;
}
}

- anonymous July 16, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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();
    }
}

- ugurdonmez87 July 28, 2016 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More