## Google Interview Question for Site Reliability Engineers

Team: Site reliabilty
Country: United States
Interview Type: Phone Interview

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

Start from the last index of the array and add 1... if that sum is == 10, make that number = 0, and carry "1" to the preceding num... exactly like you would add a number..

``````// assume a is the array
i = a.length() - 1;
while (i >= 0)
{
int sum = a[i] + 1;
if (sum == 10) /* sum cannot be > 10 since you're adding only 1, max will be 9 + 1 = 10 */
{
a[i] = 0;
i --;
}
else
{
a[i] = sum;
break;
}
}``````

it becomes tricky when the number is such that adding 1 increases the number of elements by 1... for example, the number is 999... then adding 1 will make it 1000 which is 1 digit more than that of the given number...

in that case, you could check the value of i after the while loop...

``````if (i < 0)
{
/* create a new array b with size = a.length + 1) */
b[0] = 1;
for (j = 1; j < b.length; j++)
{
b[j] = 0;
}
}``````

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

here is one version. I haven't dry run but should be okay

while(i > -1 && carry == 1){
result = arr[i] + carry;
if(result>10)
arr[i]=result%10;
else
carry = 0;
}
if(i == 0 and carry == 1){
int* newArr = new int[size+1];
copy(newArr+1, arr);
newArr[0]= carry;
}

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

``````int* add( int *src, int len, int data)
{
int *res;
int i;

for ( i = len - 1; i > = 0; i-- )
{
if ( data == 0)
{
break;
}
data = (src[i] + data) / 10;
src[i] = (src[i] + data) % 10;
}

if ( data == 0 )
return src;
else
{
res = (int*)malloc(sizeof(int)*(len+1));
memset(res, 0, len+1);
res[0] = data;
memcpy(res[1], src, len);
free(src);
return res;
}
}``````

Corrections are appreciated :)

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

You can use calloc to save the memset call

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

``````#something in python

number = [1,9,9,9]

i = len(number)-1
carry = 1
while(carry and i >= 0) :
n = number[i]
if n == 9:
number[i] = 0
else:
number[i] = n + carry
carry = 0
i = i-1

if carry == 1:
number.insert(0, 1)
return number

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

just to add, above code needs two changes
a) setting arr[i] in else loop in while
b) decrementing i.

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

Is that array is a binary representation of the number? Or just split up of the digits as arrays..?

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

``````just simple string addition

#include<stdio.h>
#include<string.h>
int main()
{
int k1,k2,i,j=0,temp1,temp2,temp=0;
char str1[10000];
char str2[10000];
scanf("%s",str1);
scanf("%s",str2);
k1=strlen(str1);
k2=strlen(str2);
k1=k1-1;
k2=k2-1;
temp=0;
for(i=k1;i>=0;i--)
{
if(k2>=0){
temp1=(str1[i]-'0')+(str2[k2]-'0')+temp;
//printf("%d\n",temp1);
temp2=temp1%10;
j=j+1;
k2=k2-1;
temp=temp1/10;
if(i==0&&temp!=0)
printf("%d",temp);
}
else
{
temp1=(str1[i]-'0')+temp;
//  printf("%d\n",temp1);
temp2=temp1%10;
temp=temp1/10;
if(i==0&&temp!=0)
printf("%d",temp);
j=j+1;
}
}
for(i=j-1;i>=0;i--)
{
}
return 0;
}
with this code we can calculate additon upto 1000000 digits :)``````

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

sum of two bits a,b is given by (a xor b).
carry is given by (a and b)

``````void add1(int * a, int length ){
int carry  = 1;
for(int i = length-1 ; i>-1; i--){

int temp = (a[i] ^ carry);
carry = carry & a[i];
a[i] = temp;
}
//if carry == 1 then we've a carry after the incremetataion
}``````

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

'''in python'''
def plusOneArray(n):
t = str(n+1)
r = []
for i in range(len(t)):
r.append(t[i])
return r

plusOneArray(200)

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

{{
# add 1 to last number in array
# if number is 9, change it to zero, and increment the next number by one.
# bcase case return number otherwise.
#
array[curr_index]
if array[curr_index] != 9
array[curr_index] += 1
return array
else # it is 9
array[curr_index] = 0
if curr_index.zero?
array.unshift(1)
return array
end
end
end

a = [1,0,0,0]
a = [1,0,0,9]
a = [1,9,9,9]
a = [9,9,9,9]
}}

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

Here's a small version in Python:

``````def convert(a):
for x in range(len(a) -1, -1, -1):
a[x] = (a[x] + 1) % 10  ## If the digit gets to 10, the modulo operation will make it 0
if a[x]:                ## If it isn't 0, there's no more carry and we're done
return a
return [1] + a              ## If we got to this point, we'll have to add another digit``````

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

``````def convert(a):
for x in range(len(a) -1, -1, -1):
a[x] = (a[x] + 1) % 10
if a[x]:
return a
return [1] + a``````

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

``````public class Add {

public static void main(String[] args) {
int[] array = {9,9,9,9};
int[] res = add(array, 1, array.length-1);
for (int i = 0; i < res.length; i++) {
System.out.print(res[i]);
}
System.out.println();
}
public static int[] add(int[] array, int num, int idx) {
if(idx < 0) {
int[] newArray = new int[array.length+1];
for (int i = 0; i < array.length; i++) {
newArray[i+1] = array[i];
}
array = newArray;
array[0] = num;
//			 allocate a new array
return array;
}

// recursion move:
int temp  = array[idx] + num;
// we want to attempt and add num to the current cell. we consider whether this
// will affect the next digit to the right
if(temp / 10 == 0) { // temp is a single digit
array[idx] += num;
} else {
// temp is a 2-digits number
// add to array[idx] the less significant digit
array[idx] = temp % 10;

// call recursively to the next digit
}

return array;
}

}``````

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

Guys, use Perl!

@a=(1,0,0,0);
\$a[-1]++;

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

``````vector<int> addOne(vector<int>& a)
{
vector<int> ans;
int c(1), i(a.size()-1);
while (i >=0 )
{
int d = a[i--] + c;
ans.push_back(d%10);
c = d/10;
}
if (c) ans.push_back(c);
reverse(ans.begin(), ans.end());
return ans;
}``````

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

Python

``````In [86]: a = [9,9,9]

In [87]: [int(x) for x in str((int(''.join([ str(x) for x in a])) + 1))]
Out[87]: [1, 0, 0, 0]``````

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

``[int(i) for i in str(int("".join([str(n) for n in number]))+1)]``

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

``````def bla(lst):
# convert list to string
to_str = ''.join(map(str,lst))
# convert string to int
to_int = int(to_str)
# plus 1 to int
result_new = to_int + 1
# obtain new list with digits
result_lst = [ i for i in  str(result_new) ]
return result_lst``````

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

#include<stdio.h>
#include<stdlib.h>

int main(){

int a[4]={0,0,1,9},i;
int size,length;
int carry=1;
size=sizeof(a)/sizeof(a[0]);

for(i=size-1;i>=0;i--){
if(a[i]==9 && (carry==1)){
a[i]=0;
carry=1;
}
else if (carry==1){
a[i]=a[i]+1;
carry=0;
}
}
printf("\n\n");
for(i=0;i<size;i++)
printf("%d ",a[i]);
printf("\n\n");
return 0;
}

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

What's the point of this question?

``````int *foo2(int a[], int n)
{
int *b, carry = 1, t;

if ((b = (int *)malloc(n + 1)) == NULL) {
fprintf(stderr, "malloc failed\n");
return NULL;
}

for (int i = n - 1; i >= 0; i--) {
t = a[i] + carry;
if (t == 10) {
t = 0;
carry = 1;
} else {
carry = 0;
}

b[i + 1] = t;
}

b[0] = carry;

return b;
}

int main()
{
int a[] = { 2, 0, 9, 9 }, *b;

b = foo(a, 4);
if (b != NULL) {
for (int i = 0; i < 5; i++) printf("%d ", b[i]);
printf("\n");
}

free(b);

b = foo2(a, 4);
if (b != NULL) {
for (int i = 0; i < 5; i++) printf("%d ", b[i]);
printf("\n");
}

free(b);

return 0;
}``````

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

With bits of Java library classes (Math, Arrays):

``````import java.util.Arrays;

public class NumberAsArray {

public static void main(String[] args) {
System.out.println(Arrays.toString(inc(new int[] {1,0,0,1})));
System.out.println(Arrays.toString(inc(new int[] {3,7,9,9})));
System.out.println(Arrays.toString(inc(new int[] {9,9,9,9,9})));
}

private static int[] inc (int[] is) {
// Convert array to number
int a = 0;
for (int i = 0; i < is.length; i++) {
a += is[i] * Math.pow(10, is.length - i - 1);
}
// Increment number
a++;
// Convert number to array
int[] result = new int[(int) Math.log10(a) + 1];
for (int i = 0; i < result.length; i++) {
result[result.length - i - 1] = a % 10;
a = a /  10;
}
return result;
}

}``````

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.