Google Interview Question for Software Engineer Interns

• 4

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
13
of 17 vote

``````int *AddArrays(int a[], int alen, int b[], int blen)
{
int maxLen = max(alen, blen);
int *c = new int[maxLen + 1];

int acur = alen - 1;
int bcur = blen - 1;
int ccur = maxLen;
int carry = 0;

while(ccur >= 0)
{
int cur = carry;
if(acur >= 0)
cur += a[acur--];
if(bcur >= 0)
cur += b[bcur--];

c[ccur--] = cur % 10;
carry = cur/10;
}

return c;
}``````

Comment hidden because of low score. Click to expand.
0

Really straightforward and simple solution. Runs in O(maxlen(a,b)) time.

Comment hidden because of low score. Click to expand.
0

Very nice. My only issue is that c[0] will be null (or undefined) if there is a carry on the most significant digit.

Comment hidden because of low score. Click to expand.
0

@Michael - First assuming all values of the arrays are initialized to zero, the fact that c is of length maxlen+1 will avoid that problem (the new array will always be one digit longer than the longest input, allowing room to contain the correct sum after the final carry step).

Comment hidden because of low score. Click to expand.
0

Nice !!. Neat and clean implementation.

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

Your solution is correct, but always increases the size of result by one, which is a design flaw. For example, if you have a=123 and b=256, c=a+b would be 0379 instead of 379. You can prevent it by just checking if summing two numbers will have a carry-on on the highest order digit or not by few lines of code.

Your solution also does not consider the fact that big numbers are signed or not signed.

Comment hidden because of low score. Click to expand.
0

Note that the question says the numbers are 'integers', meaning that they can be positive or negative. This code won't work as is when any or both or the numbers are negative. Like maybe the left-most cell in one of the number arrays contains a '-' character, indicating that the number is negative. We would most probably have to handle that in our code.

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

For fun because I wanted to act on a hunch that a few liner was possible. Though I expanded a line into multiple to make it clear that 3 possible cases of sum are being calculated.

Call this with b[] being bigger array, r[] having length b.length+1, and last argument 0
(use a wrapper if you like):
b stands for bigger, s for smaller, r for result

``````public int doit(int b[],int s[],int r[], int i)
{
if(i == b.length) return 0;

sum = doit(b,s,r,i+i) + ( i==0                   ? 0 :
b.length-a.length >= i ? b[i-1] :
b[i-1] + a[i-1-a.length]);
r[i] = sum%10, return sum/10;
}``````

I used this diagram (in notepad) to play with to scratch my itch (the hunch):

``````i               4  5
res [ ][ ][ ][ ][ ][ ]  res.length = b.length+1
b [ ][ ][ ][ ][ ]
a [ ][ ]

b.length-a.length=3``````

Yes, there are limitations to the design, but it looks cool (and different from the ones already posted). And probably has off by one errors.

Compiled on scrap paper, tested on that notepad diagram above.

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

Ughh careercup messed up alignments. Trying again:

``````public int doit(int b[],int s[],int r[], int i)
{
if(i == b.length) return 0;

sum = doit(b,s,r,i+i) + ( i==0                   ? 0 :
b.length-a.length >= i ? b[i-1] :
b[i-1] + a[i-1-a.length]);
r[i] = sum%10, return sum/10;
}``````

And:

``````i              4  5
res [ ][ ][ ][ ][ ][ ]
b [ ][ ][ ][ ][ ]
a [ ][ ]

b.length-a.length=3``````

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

#include <stdio.h>
#include <stdlib.h>
int array_add(int *result, int data_1[], int len_1, int data_2[], int len_2){
if( len_1 < 0 || len_2 < 0 ){
return -1;
}
int i,j,k;
int temp;

// i = (len_1 < len_2 ? len_1-1:len_2-1);
temp = 0;
i = len_1 -1;
j = len_2 -1;
k = (len_1 > len_2 ? len_1:len_2);

for( ; i > -1 && j > -1 ; i--,j--){
temp = data_1[i] + data_2[j] +result[k];
result[k] = temp%10;
result[k-1] = result[k-1] + temp/10;
k--;
}

// j = (len_1 > len_2 ? len_1-len_2-1 : len_2-len_1-1);

if(i > -1){
while( i > -1 ){
temp = result[k] + data_1[i];
result[k] = temp%10;
result[k-1] = result[k-1] + temp/10;
i--;
k--;
}
}else if( j > -1 ){
while( j > -1 ){
temp = result[k]+ data_2[j];
result[k] = temp%10;
result[k-1] = result[k-1] + temp/10;
j--;
k--;
}
}
return 1;
}
int main(){
int array_1[5] = {2,3,4,6,7};
int array_2[6] = {5,7,2,7,8,3};
int i;
int *result = (int *)malloc(sizeof(int)*7);
for ( i = 0; i < 7 ; i++ ){
result[i] = 0;
}
for ( i = 0; i < 7 ; i++ ){
printf("%d ",result[i]);
}
printf("\n");
return 1;
}

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

Not sure if I'm missing something or I misunderstood the problem but here is mine. It seems to work.

``````public class ArrayAddition {
public static void main(String[] args)
{
int[] a = {2, 6, 0, 0};

int[] b = {1, 7};
int finalArrayLength = Math.max(a.length, b.length);  //returns the greater of the two lengths
char[] result = Integer.toString(finalNum).toCharArray();
int[] finalArray = new int[finalArrayLength];
for (int i = 0; i < finalArray.length; i++)
{
finalArray[i] = Character.getNumericValue(result[i]);
}
System.out.println(Arrays.toString(finalArray));

}
public static int addArray(int[] a, int[] b)
{
String stringA = "";
String stringB = "";
int finalNum;
for (int i = 0; i < a.length; i++)
{
stringA += Integer.toString(a[i]);
}
for (int j = 0; j < b.length; j++)
{
stringB += Integer.toString(b[j]);
}
finalNum = Integer.parseInt(stringA) + Integer.parseInt(stringB);
return finalNum;
}
}``````

Comment hidden because of low score. Click to expand.
0

doesn't work for all cases it seems. nevermind...

Comment hidden because of low score. Click to expand.
0

Also remember these are very large numbers. This means that the regular Integer class could not hold the value so parsing the array's string representation does not work.

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

Well, here's a fun way of doing it, not really any more efficient than the other methods shown here, this one uses a stack.

``````int[] add_arrays(int[] a, int[] b){

Stack s = new Stack();
int pa = a.length;
int pb = b.length;
int carry = 0;

while(pa >= 0 || pb >= 0){
if(pa < 0){
s.push(b[pb] + carry);
carry = 0;
pb--;
continue;
}else if (pb < 0){
s.push(a[pa] + carry);
carry = 0;
pa--;
continue;
}else {
int x = a[pa] + b[pb] + carry;
if(x > 9){
carry = 1;
x %= 10;
}else {
carry = 0;
}
s.push(x);
pa--;
pb--;
}
}

int[] result = new int[s.length()];

for(int i = 0; !s.isEmpty(); i++){
result[i] = s.pop();
}

return result;
}``````

It will always take O(max(a.length,b.length)) time (so, O(n) where n is longest array's length). In no event will it have a extraneous digit on the front.

It's not a pretty or short solution, unfortunately, but it works and it is time efficient. It only works if you are adding in the following manner ( there is another version where the last digit is the highest)

{1,2,3} = 123.
{4,5,6} = 456.
{1,2,3} + {4,5,6} = 579

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

``````public static int[] AddArrays(int[] a, int lengtha, int[] b, int lengthb)
{
int[] result = new int[Math.Max(lengtha, lengthb) + 1];

int indexa = lengtha - 1;
int indexb = lengthb - 1;

int indexResult = result.Length - 1;

int carryOver = 0;

while (indexa >= 0 || indexb >= 0)
{
int valuea = 0;
int valueb = 0;

if (indexa >= 0)
{
valuea = a[indexa];
indexa--;
}

if (indexb >= 0)
{
valueb = b[indexb];
indexb--;
}

if (valuea / 10 > 0)
{
throw new ArgumentException();
}

if (valueb / 10 > 0)
{
throw new ArgumentException();
}

int tmp = valuea + valueb + carryOver;
result[indexResult] = tmp % 10;
carryOver = tmp / 10;

indexResult--;
}

if (indexResult != 0 && indexResult != 1)
{
throw new InvalidOperationException();
}

return result;``````

}

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

Java Solution:

``````private static int[] add(int[] one, int[] two) {
if (one == null || two == null)
throw new IllegalArgumentException("Parameters cannot be null.");
int size = Math.max(one.length, two.length) + 1;
int[] ret = new int[size];
boolean carry = false;

for (int i = 0; i < size; i++) {
int sum = 0;
if (carry) {
sum++;
carry = false;
}

if (i < one.length)
sum += one[i];
if (i < two.length)
sum += two[i];
if (sum >= 10) {
carry = true;
sum -= 10;
}
ret[size - i - 1] = sum;
}
return ret;
}``````

Comment hidden because of low score. Click to expand.
0

I guess I also could've added a check for the length of one and two to make sure they actually had values on the IllegalArguementException

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

``````#include<iostream>
#include<math.h>
using namespace std;

void print(int * added_arr,int size )
{
for(int i=0; i<size; i++)
cout<<endl;
}

void sum(int * first_num, int * second_num, int size_of_1st_no ,int size_of_2st_no)
{
int i=0;
for( i=size_of_1st_no-1; size_of_2st_no-1>=0; i--)
{

{
first_num[i-1]=first_num[i-1] + 1;  // in the case of carry adding
}
else
{
}

size_of_2st_no--;

}

if(i>0 &&  first_num[i] > 9 )
{
while(i>=0 && first_num[i] > 9)
{
first_num[i]=0;
first_num[i-1]=first_num[i-1]+1;
i--;
}
}
}

void main()
{
int size_of_1st_no=0;
int size_of_2st_no=0;
cout<<"Enter Size of first Array::";
cin>>size_of_1st_no;
cout<<"Enter Size of second Array::";
cin>>size_of_2st_no;
//---------Create arrys for both numbers. Number arry that is biger used to store the result later
int * first_num;
int * second_num;
if(size_of_1st_no >= size_of_2st_no)
{
size_of_1st_no=size_of_1st_no+1;   // one index more in case of over flow
first_num=new int [size_of_1st_no];
second_num=new int [size_of_2st_no];
}
else
{
size_of_2st_no=size_of_2st_no+1;   // one index more in case of over flow
first_num=new int [size_of_1st_no];
second_num=new int [size_of_2st_no];
}

int i=0;
int j=0;

if(size_of_1st_no >= size_of_2st_no)
{
i=1; j=0;
first_num[0]=0;
}
else
{
i=0; j=1;
second_num[0]=0;
}

for( ; i<size_of_1st_no;i++)
{
cout<<"Enter Element for First No:";
cin>>first_num[i];
}

for( ; j<size_of_2st_no;j++)
{
cout<<"Enter Element for Second No:";
cin>>second_num[j];
}

if(size_of_1st_no>size_of_2st_no)
sum(first_num, second_num,size_of_1st_no,size_of_2st_no);
else
sum(second_num, first_num,size_of_2st_no,size_of_1st_no);

if(size_of_2st_no>=size_of_1st_no)
print(second_num,size_of_2st_no);
else
print(first_num,size_of_1st_no);

//-----------------------------------------
system("pause");
}``````

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

``````alist =             [1, 2, 4, 5, 6, 7]
blist =          [9, 9, 3, 3, 2, 1, 9]
sumlist = []

alen = len(alist) - 1
blen = len(blist) - 1

carry = 0
while alen >= 0 or blen >= 0:
a = 0
b = 0
if alen >= 0:
a = alist[alen]
if blen >= 0:
b = blist[blen]
absum = (a + b + carry) % 10
carry = (a + b + carry) / 10
sumlist[:0] = [absum]
alen -= 1
blen -= 1

if carry > 0:
sumlist[:0] = [carry]
print sumlist``````

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

github.com/vikhyath/c-runs/tree/master/sum-arrays

github.com/vikhyath/python-runs/tree/master/sum-arrays

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

Java Solution

``````public class TwoArraySum {

public static int[] addArray(int[] a, int[] b){
int alen = a.length;
int blen = b.length;
int clen = Math.max(alen, blen);
int[] c  = new int[clen];
boolean carry = false;

for ( int i = 0; i < clen; i++ ){
int eleSum = 0;

if ( i < alen ){
eleSum = a[i];
}
if ( i < blen){
eleSum += b[i];
}
if ( carry ){
eleSum += 1;
carry = false;
}
carry = (eleSum > 10);
c[i] = (carry)? eleSum-10 : eleSum;
}
return c;

}

public static void main(String[] args){
int[] b = new int[] { 6, 6, 6, 6, 6 };
int[] a = new int[] { 5, 0, 5 };

StringBuilder sb = new StringBuilder();
for ( int ele : c ){
sb.insert(0, ele);
}
System.out.println(sb.toString());

}
}``````

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

There's already a simple straightforward solution.

A more performant solutions would use some sort of SIMD, like SSE2.
You'd have to do an add operation to add the two arrays, divide by 10 to get the carry, re-align the resultant carry data, then add the carry.

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

My intuitive algorithm:

``````vector<int> sum(vector<int> &a, vector<int> &b) {
int i, cary = 0;
int ap = a.size() - 1;
int bp = b.size() - 1;
int sz = 0;
//gets result size
while (ap >= 0 || bp >= 0) {
int d = 0;
if (ap >= 0)
d += a[ap--];
if (bp >= 0)
d += b[bp--];
d += cary;
cary = d / 10;
d %= 10;
sz++;
}
//Compute the sum
vector<int> ans(sz);
while (sz > 0) {
int d = 0;
if (ap >= 0)
d += a[ap--];
if (bp >= 0)
d += b[bp--];
d += cary;
cary = d / 10;
d %= 10;
ans[sz--] = d;
}
if (cary > 0)
ans[sz--] = cary;
reverse(ans.begin(), ans.end());
return ans;
}``````

The time complexity: O(max(|a|,|b|))

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

// assume the integers are positive
// 1-Select the size of the biggest array maxLen
// 2-Start the sum from the end of the selected array
// carry = 0;
// x goes from maxLen-1 to 0
// y = ( 0 or a[x] if x<aLen ) + ( 0 or b[x] if x<bLen ) + carry
// if y>9
// y = 10-y and carry = 1
// else
// carry = 0

``````int* Sum_array(unsigned int a[], std::size_t aLen, unsigned int b[], std::size_t bLen)
{
int maxLen    = (aLen>bLen) ? aLen:bLen ;
int * Res     = new int[maxLen+1];
std::size_t carry     = 0;

for(int j=maxLen-1;j>=0;j--)
{
Res[j+1] = ((j<aLen) ? a[j]:0) + (( j<bLen ) ? b[j]:0) + carry;
if(Res[j+1]>9)
{
Res[j+1]=10-Res[j+1];
carry = 1;
}
else
{
carry = 0;
}
}

Res[0] = carry;

return Res;
}``````

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

I used long instead of int just so it could handle larger values.

public static void main(String arg[]) {
long[] arraySum1 = { 1, 2, 3, 4, 5, 1, 9, 8, 9, 3, 4 };
long[] arraySum2 = { 1, 2, 9, 4, 5, 2, 3, 8, 5 };
long arraySum = arraySum(arraySum1, arraySum2);
System.out.println(arraySum);
}
public static long arraySum(long[] x, long[] y) {
int a = x.length - 1, b = y.length - 1;
long sum = 0;
while (a >= 0 || b >= 0) {
if (a >= 0)
{sum += x[a] * Math.pow(10, x.length - a - 1);}
if (b >= 0)
{sum += y[b] * Math.pow(10, y.length - b - 1);}
System.out.println(sum);
a--; b--;
}
return sum;
}

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

I used long instead of int just so it could handle larger values.

public static void main(String arg[]) {
long[] arraySum1 = { 1, 2, 3, 4, 5, 1, 9, 8, 9, 3, 4 };
long[] arraySum2 = { 1, 2, 9, 4, 5, 2, 3, 8, 5 };
long arraySum = arraySum(arraySum1, arraySum2);
System.out.println(arraySum);
}
public static long arraySum(long[] x, long[] y) {
int a = x.length - 1, b = y.length - 1;
long sum = 0;
while (a >= 0 || b >= 0) {
if (a >= 0)
{sum += x[a] * Math.pow(10, x.length - a - 1);}
if (b >= 0)
{sum += y[b] * Math.pow(10, y.length - b - 1);}
System.out.println(sum);
a--; b--;
}
return sum;
}

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

Assuming arrays can be of different length:

``````int a[] = {9,5,7,2,4,8,5,9,1,5};
int b[] = {8,5,9,1};

int s, prev = 0, cA = sizeof(a)/sizeof(*a), cB = sizeof(b)/sizeof(*b);
int k = max(cA, cB), j;
int sum[k + 1];

for (int i = k - 1; i >= 0; i --){
s = prev;
j = (i - k + cA);
if (j >= 0 && j < cA){
s += a[j];
}
j = (i - k + cB);
if (j >= 0 && j < cB){
s += b[j];
}
prev = 0;
if (s > 9){
prev = (s / 10);
s %= 10;
}
sum[i] = s;
}
if (prev > 0){
sum[k] = prev;
}
else {
sum[k] = 0;//or remove the extra element
}

for (int i = 0; i < k; i ++){
printf("%d", sum[i]);
}``````

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

This seems too easy to be a Google SE Intern question... I'm suspicious.

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

How's it stored and in what type of array?

Comment hidden because of low score. Click to expand.
0

The numbers are stored from most sig digit to least from right to left in the array, as you'd probably naturally imagine.

int[] arr = {1, 2, 3}; // 123

The type of array is int[]. (This was originally in Java when asked).

Comment hidden because of low score. Click to expand.
0

Ok, that's interesting.

Let me try recursive for fun.

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

public class Sum {

static int a1[] = {1,2,3,4};
static int a2[] = {9,9,9,9};
static int a3[];

static void findSum(int a1[], int a2[]){

int len1 = a1.length-1, len2 = a2.length-1, len3 = a3.length-1;
int carry = 0,sum;
while(len2 != -1){
sum = a1[len1--] + a2[len2--]+carry;
carry = sum / 10;
a3[len3--] = sum%10;
}
while(len1 != -1){
sum = a1[len1--] + carry;
a3[len3--] = sum%10;
carry = sum/10;
}
a3[len3] = carry;
for(int i = 0; i <a3.length; i++){
System.out.print(a3[i]);
}
}

public static void main(String args[]){
if(a1.length>a2.length){
a3 = new int[a1.length+1];
findSum(a1,a2);
}
else{
a3 = new int[a2.length+1];
findSum(a2,a1);
}
}
}

Comment hidden because of low score. Click to expand.
0

seems to add an extra 0 at the beginning in some cases

Comment hidden because of low score. Click to expand.
-2
of 4 vote

public static void main(String[] args) {
int[] a = {9,5,7,2,4,8,5,9,1,5};
int[] b = {9,1,1,1,2,3,8,5,9,1};
}

static void add(int[] x, int[] y){
int xLength = x.length;
int yLength = y.length;
int zLength = Math.max(xLength, yLength)+1;
int[] z = new int[zLength];
int k = 0;
for (int i=1;i<=zLength;i++){
if(xLength-i<0 && yLength-i>=0){
z[zLength-i] = (y[yLength-i]+k)%10;
k = (y[yLength-i]+k)/10;
}
else if(yLength-i<0 && xLength-i>=0){
z[zLength-i] = (x[xLength-i]+k)%10;
k = (x[xLength-i]+k)/10;
}
else if(yLength-i<0 && xLength-i<0){
z[zLength-i] = k;
}
else if(yLength-i>=0 && xLength-i>=0){
z[zLength-i] = (x[xLength-i]+y[yLength-i]+k)%10;
k = (x[xLength-i]+y[yLength-i]+k)/10;
}
}
for (int i=0;i<zLength;i++){
System.out.print(z[i]);
}
System.out.println();
}

Comment hidden because of low score. Click to expand.
-2
of 2 vote

``````#!/usr/bin/env python

def getVal(tlist, i):
if i < len(tlist):
return tlist[i]
else:
return 0

total = list()
carryOn = 0
index1 = len(list1)-1
index2 = len(list2)-1
while index1 >= 0 and index2 >= 0:
tsum = list1[index1] + list2[index2] + carryOn
total.append(tsum%10)
carryOn = int(tsum/10)
index1-=1
index2-=1
print total,index1,index2
if index2 < 0:
while index1 >=0:
tsum = carryOn + list1[index1]
total.append(tsum%10)
carryOn = int(tsum/10)
index1-=1
print total
else:
while index2 >=0:
tsum = carryOn + list2[index2]
total.append(tsum%10)
carryOn = int(tsum/10)
index2-=1

if __name__ == '__main__':
list1 = [1,2,3,4,8]
list2 = [3,7,8,9,2,3,4]

Comment hidden because of low score. Click to expand.
0

No need for so much duplicated code. Check this:

``````def sum_big(a, b):
c = [0 for it in xrange(max(len(a),len(b))+1)]

it_a = len(a) - 1
it_b = len(b) - 1
it_c = len(c) - 1
carry = 0

while it_c >= 0:
s = carry

if it_a >= 0:
s += a[it_a]

if it_b >= 0:
s += b[it_b]

c[it_c] = s % 10
carry = s / 10

it_a -= 1
it_b -= 1
it_c -= 1

return c``````

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.

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.