Google Interview Question Software Engineer in Tests
Country: United States
Interview Type: In-Person
if the question is as simple I thought (unlike others)
#include <iostream>
#include <math.h>
using namespace std;
int main()
{
long double arr[3]={1,2,9},final =0;
int arrLength = 3;
for(int i=0;i<3;i++)
final = final +arr[i]*pow((double)10,arrLength-i-1);
final++;
cout<<"Value after adding 1: "<<final<<endl;
}
~
#include <iostream>
#include <vector>
using namespace std;
void increase(vector<int> &value)
{
vector<int>::iterator iter;
for (iter = value.begin(); iter != value.end(); ++iter)
{
if (*iter < 9)
{
++*iter;
break;
}
else
{
*iter = 0;
}
}
if (iter == value.end())
{
value.push_back(1);
}
iter = value.end() - 1;
for (; iter >= value.begin(); --iter)
{
cout << *iter;
}
cout << endl;
}
int main()
{
vector<int> value;
string s;
cin >> s;
for (int i = s.size() - 1; i >= 0; --i)
{
value.push_back(s[i] - '0');
}
increase(value);
return 0;
}
public int[] plusOne(int[] num) {
int[] result = new int[num.length];
int carry = 1;
for (int i = num.length - 1; i >= 0; i++) {
result[i] = num[i] + carry;
carry = result[i] / 10;
result[i] %= 10;
}
//this will happen very rear -> 1 / (sum(9*10^i)), i = [0, num.length)
if (carry > 0){
int[] oldResult = result;
result = new int[num.length + 1];
System.arraycopy(oldResult, 0, result, 1, oldResult.length);
result[0] = carry;
}
return result;
}
import java.util.Arrays;
import java.util.List;
import java.util.Vector;
public class Test
{
public static void main(String[] args)
{
Vector<Integer> array = new Vector<Integer>(Arrays.asList(1, 1));
System.out.println("Input: " + array);
System.out.println("Array result: " +
increment(array, array.size() - 1, true));
printArray(array);
System.out.println();
array = new Vector<Integer>(Arrays.asList(9, 9));
System.out.println("Input: " + array);
System.out.println("Array result: " +
increment(array, array.size() - 1, true));
printArray(array);
}
static void printArray(final Vector<Integer> array)
{
System.out.print("Result: ");
for(int digit: array)
{
System.out.print(digit);
}
System.out.println();
}
static List<Integer> increment(final Vector<Integer> array, int start,
boolean carry)
{
if (start < 0)
{
array.insertElementAt(0, 0);
start = 0;
}
for (int i = start; i >= 0; i--)
{
if ((array.get(i) == 9) && carry)
{
array.set(i, 0);
increment(array, i - 1, true);
}
else if ((array.get(i) < 9) && carry)
{
array.set(i, array.get(i) + 1);
carry = false;
}
}
return array;
}
}
Output:
Input: [1, 1]
Array result: [1, 2]
Result: 12
Input: [9, 9]
Array result: [2, 0, 0]
Result: 200
perl code
my @num = qw (9 9 9 9 9);
my $carry = 1;
for(my $i = scalar(@num) - 1; $i >= 0; $i--) {
$n = ($carry + $num[$i]) % 10;
$carry = int (($carry + $num[$i]) / 10);
$num[$i] = $n;
last if (!$carry);
}
if ($carry) {
unshift(@num, $carry);
}
print "@num\n";
-----------------------------
public class IncrementValueInArray {
public static Integer[] plusOne(final Integer[] input) {
int carry = 1;
for (int i = input.length - 1; i >= 0; i--) {
int sum = input[i] + carry;
carry = sum /10;
input[i] = carry > 0? sum % carry : sum;
}
if (carry != 0) {
Integer[] result = new Integer[1 + input.length];
result[0] = carry;
for (int j = 0; j < input.length; j++) {
result[j + 1] = input[j];
}
return result;
}
return input;
}
private static void printArray(final Integer[] array) {
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
System.out.println();
}
public static void main(String args[]) {
printArray(plusOne(new Integer[]{9,9}));
printArray(plusOne(new Integer[]{8, 2}));
printArray(plusOne(new Integer[]{1, 8, 2}));
printArray(plusOne(new Integer[]{1, 9, 9}));
printArray(plusOne(new Integer[]{9, 9, 9}));
}
}
Output:
1 0 0
8 3
1 8 3
2 0 0
1 0 0 0
1 #include <iostream>
2 #include <vector>
3 #include <algorithm>
4
5 using namespace std;
6
7 void addOne(int arr[], int len, vector<int>& vec) {
8 if(arr == 0 || len == 0) return;
9
10 int carry = 1;
11
12 for(int i = len-1; i >= 0; i--) {
13 arr[i] += carry;
14 carry = arr[i]/10;
15 arr[i] %= 10;
16 vec.push_back(arr[i]);
17 }
18 if(carry)
19 vec.push_back(carry);
20 }
21
22 int main() {
23 int arr[] = {9, 9};
24 int len = sizeof(arr)/sizeof(int);
25 vector<int> vec;
26 addOne(arr, len, vec);
27 reverse(vec.begin(), vec.end());
28 for(int i = 0; i < vec.size(); i++)
29 cout << vec[i] << " ";
30 cout << endl;
31
32 return 0;
33 }
1 #include <iostream>
2 #include <vector>
3 #include <algorithm>
4
5 using namespace std;
6
7 void addOne(int arr[], int len, vector<int>& vec) {
8 if(arr == 0 || len == 0) return;
9
10 int carry = 1;
11
12 for(int i = len-1; i >= 0; i--) {
13 arr[i] += carry;
14 carry = arr[i]/10;
15 arr[i] %= 10;
16 vec.push_back(arr[i]);
17 }
18 if(carry)
19 vec.push_back(carry);
20 }
21
22 int main() {
23 int arr[] = {9, 9};
24 int len = sizeof(arr)/sizeof(int);
25 vector<int> vec;
26 addOne(arr, len, vec);
27 reverse(vec.begin(), vec.end());
28 for(int i = 0; i < vec.size(); i++)
29 cout << vec[i] << " ";
30 cout << endl;
31
32 return 0;
33 }
package Miscellaneous;
import java.util.Arrays;
public class IncrementArray {
public static int[] increment (int[] arr){
StringBuilder sb = new StringBuilder();
for (int i : arr){
sb.append(i);
}
int x = Integer.parseInt(sb.toString());
Integer result = x + 1;
String b = result.toString();
String[] items = b.replaceAll("\\[", "").replaceAll("\\]", "").split(",");
System.out.println(Arrays.toString(items));
int[] results = new int[items.length];
for (int i = 0; i < items.length; i++) {
try {
results[i] = Integer.parseInt(items[i]);
} catch (NumberFormatException nfe) {};
}
return results;
}
public static void main(String[] args){
int[] a = {9,9};
int[] b = increment(a);
System.out.println(Arrays.toString(b));
}
}
My Python solution:
def changeArray(arr):
l=len(arr)
flag=0
while(flag!=1):
if(arr[l-1]==9):
arr[l-1]=0
l=l-1
else:
arr[l-1]=arr[l-1]+1
flag=1
print arr
int increment(int[] nums) {
if (nums == null || nums.length == 0)
return 0;
int res = 0;
int carry = 1;
for (int i = nums.length - 1; i >= 0; i--) {
nums[i] += carry;
carry = nums[i] / 10;
nums[i] %= 10;
res += Math.pow(10, nums.length - 1 - i) * nums[i];
}
return carry == 1 ? (res + (int) Math.pow(10, nums.length)) : res;
}
int increment(int[] nums) {
if (nums == null || nums.length == 0)
return 0;
int res = 0;
int carry = 1;
for (int i = nums.length - 1; i >= 0; i--) {
nums[i] += carry;
carry = nums[i] / 10;
nums[i] %= 10;
res += Math.pow(10, nums.length - 1 - i) * nums[i];
}
return carry == 1 ? (res + (int) Math.pow(10, nums.length)) : res;
}
C implementation int* add(int *src, int len, int data) { int *res; int carry = data; int i; for (i = len-1; i > = 0; i-- ) { if ( carry == 0 ) { break; } src[i] = ( src[i] + carry ) % 10; carry = ( src[i] + carry ) / 10; } if ( carry == 0 ) { return src; } else { res = (int *)malloc(sizeof(int) * (len + 1)); res[0] = carry; memcpy(res[1],src,len); free(src); return res; } }Corrections are appreciated :)
- code_monkey September 30, 2012--
“A mistake is a crash-course in learning.”
--