Facebook Interview Question
Software EngineersCountry: United Kingdom
Interview Type: Phone Interview
Integer[] a = {9, 9, 9};
int g = 9999;
List<Integer> list = new ArrayList<>();
for (int i = a.length -1 ; i >= 0; i--) {
g = a[i] + g;
list.add(0, g % 10);
g = g / 10;
}
//In case the number is greater than array size
while ( g >= 10) {
list.add(0, g % 10);
g = g / 10;
}
list.add(0, g);
list.toArray(a);
My answer to this question was using recursion:
var tmp = [];
(function addToArray(arr, toAdd){
if(!arr.length && !toAdd){
return;
}
if(!arr.length && toAdd){
arr = [0]
}
tmp.push(Math.floor((arr[arr.length-1]+toAdd)%10));
var _toAdd = Math.floor((arr[arr.length-1]+toAdd)/10)
_toAdd = (_toAdd < 0 ? 0 : _toAdd);
addToArray(arr.splice(0,arr.length-1), _toAdd);
})([0], 2);
console.log(tmp.reverse());
C#:
public static int[] Add(int[] arr, int other)
{
if (arr == null)
{
return null;
}
// we need to process "other" digit by digit starting at the end
int carry = 0;
int currentValue = 0;
for (int i=arr.Length-1; i>=0; i--)
{
if (!(arr[i] >=0 && arr[i] <= 9))
{
throw new InvalidOperationException();
}
int rem = other % 10;
other = (other - carry) / 10; // change 123 t0 12 by dropping the last digit
currentValue = arr[i] + rem + carry;
arr[i] = currentValue % 10;
carry = currentValue / 10;
}
if (carry != 0 || other != 0)
{
// We have exceeded the original array's size
int finalcarry = other + carry;
int size = 0;
while (finalcarry > 0)
{
finalcarry = finalcarry / 10;
size++;
}
int[] newArray = new int[arr.Length + size];
finalcarry = other + carry;
for (int i = size - 1; i >= 0; i--)
{
int rem = finalcarry % 10;
finalcarry = finalcarry / 10;
newArray[i] = rem;
}
for (int i = size; i < newArray.Length; i++)
{
newArray[i] = arr[i - size];
}
return newArray;
}
return arr;
}
All these tests passed:
int[] arr8 = new int[] { 1, 1, 2, 3 };
int[] result8 = ArrayQuestions.Add(arr8, 89);
arr8 = new int[] { 2, 3 };
result8 = ArrayQuestions.Add(arr8, 89);
arr8 = new int[] { 3 };
result8 = ArrayQuestions.Add(arr8, 89);
arr8 = new int[] { };
result8 = ArrayQuestions.Add(arr8, 89);
arr8 = new int[] { 0, 0, 1 };
result8 = ArrayQuestions.Add(arr8, 89);
C#:
public static int[] Add(int[] arr, int other)
{
if (arr == null)
{
return null;
}
// we need to process "other" digit by digit starting at the end
int carry = 0;
int currentValue = 0;
for (int i=arr.Length-1; i>=0; i--)
{
if (!(arr[i] >=0 && arr[i] <= 9))
{
throw new InvalidOperationException();
}
int rem = other % 10;
other = (other - carry) / 10; // change 123 t0 12 by dropping the last digit
currentValue = arr[i] + rem + carry;
arr[i] = currentValue % 10;
carry = currentValue / 10;
}
if (carry != 0 || other != 0)
{
// We have exceeded the original array's size
int finalcarry = other + carry;
int size = 0;
while (finalcarry > 0)
{
finalcarry = finalcarry / 10;
size++;
}
int[] newArray = new int[arr.Length + size];
finalcarry = other + carry;
for (int i = size - 1; i >= 0; i--)
{
int rem = finalcarry % 10;
finalcarry = finalcarry / 10;
newArray[i] = rem;
}
for (int i = size; i < newArray.Length; i++)
{
newArray[i] = arr[i - size];
}
return newArray;
}
return arr;
}
c++, implementation
void addAndNormalize(vector<int>& arr, int n) {
vector<int>::iterator it;
int r;
r = n;
if (arr.size() == 0) {
arr.push_back(n);
r = 0;
}
reverse(arr.begin(), arr.end());
it = arr.begin();
while (true) {
*it += r;
r = *it / 10;
if (r == 0) break;
*it %= 10;
it++;
if (it == arr.end()) {
it = arr.insert(it, r);
r = 0;
}
}
reverse(arr.begin(), arr.end());
}
Integer[] a = {9, 9, 9};
int g = 9999;
List<Integer> list = new ArrayList<>();
for (int i = a.length -1 ; i >= 0; i--) {
g = a[i] + g;
list.add(0, g % 10);
g = g / 10;
}
//In case the number is greater than array size
while ( g >= 10) {
list.add(0, g % 10);
g = g / 10;
}
list.add(0, g);
list.toArray(a);
Integer[] a = {9, 9, 9};
int g = 9999;
List<Integer> list = new ArrayList<>();
for (int i = a.length -1 ; i >= 0; i--) {
g = a[i] + g;
list.add(0, g % 10);
g = g / 10;
}
//In case the number is greater than array size
while ( g >= 10) {
list.add(0, g % 10);
g = g / 10;
}
list.add(0, g);
list.toArray(a);
# Bascially add a number and if carray over exists update the next significant digit
def add2(n1, num):
# print "Adding n1, num: {0}, {1} ".format(n1, num)
(carry, rem) = divmod((n1+num), 10)
return (carry, rem)
def add_array():
carry, rem = 0, 0
for i, v in enumerate(reversed(array)):
if i == 0:
(carry, rem) = add2(v, N)
if i > 0:
if carry >= 1:
(carry, rem) = add2(v, carry)
else:
(carry, rem) = add2(v, 0)
newArray.append(rem)
# print "latest array: ", newArray
if carry > 0:
newArray.append(carry)
if __name__ == '__main__':
N = 5; array = [0, 0, 1]; newArray = []
add_array()
newArray.reverse()
print array
print newArray
N = 9; array = [1]; newArray = []
add_array()
newArray.reverse()
print array
print newArray
N = 9; array = [9, 1]; newArray = []
add_array()
newArray.reverse()
print array
print newArray
This is the style that I was thinking about. I added some tests to check against as well.
The problem gives the possibility that the array [0,0,1] could exist. A test in your example could be the number 5 and the array [0,0,3] with the expected result being [0,0,8]..
Consider remembering the length of the original array, converting the resulting INT to a string, then padding that string with zeros with the difference (arrayNum.length vs array.length >>> JavaScript syntax).
I also tend to have verbose code when interviewing. Some languages have string padding, JavaScript does not.
function array_add( incoming_int, incoming_array ) {
var array_len = incoming_array.length,
array_to_num = parseInt( incoming_array.join('') ),
array_addition = array_to_num + incoming_int,
padding_length = array_len - array_addition.toString().length,
padding = '',
return_array = [];
for( var i = 0; i < padding_length; i++ ) { padding += '0'; }
num_to_string = String(padding + array_addition);
return_array = num_to_string.split('');
return return_array;
}
var tests = [
{
number: 5,
array: [0,9,3],
solution: [0,9,8]
},
{
number: 10,
array: [0,0,1],
solution: [0,1,1]
},
{
number: 111,
array: [0,0,2,5,0],
solution: [0,0,3,6,1]
}
];
for( var test in tests ) {
var result = arrayAdd( tests[test].number, tests[test].array );
console.log( "Result: " + result.toString() + "\nSolution: " + tests[test].solution.toString() );
}
My solution in Java:
class Solution {
public static void main(String[] args) {
int[] array = new int[]{0,2,5};
int[] newArray = new int[array.length];
int value = 25;
int index = array.length - 1;
printArray(sumArray(array, newArray, value, index));
}
private static int[] sumArray(int[] array, int[] resArray, int value, int index){
if(index >= 0){
int lastNumber = array[index];
int sum = lastNumber + value;
if(sum > 9){
resArray[index] = sum % 10;
sumArray(array, resArray, sum / 10, index - 1);
} else {
resArray[index] = sum;
sumArray(array, resArray, 0, index - 1);
}
}
return resArray;
}
private static void printArray(int[] array){
int length = array.length;
String print = "[";
for(int i = 0; i < length; i++){
print = print + array[i];
if(i == length - 1){
print = print + "]";
} else {
print = print + ",";
}
}
System.out.println("Value: " + print);
}
}
My solution in Java:
class Solution {
public static void main(String[] args) {
int[] array = new int[]{0,2,5};
int[] newArray = new int[array.length];
int value = 25;
int index = array.length - 1;
printArray(sumArray(array, newArray, value, index));
}
private static int[] sumArray(int[] array, int[] resArray, int value, int index){
if(index >= 0){
int lastNumber = array[index];
int sum = lastNumber + value;
if(sum > 9){
resArray[index] = sum % 10;
sumArray(array, resArray, sum / 10, index - 1);
} else {
resArray[index] = sum;
sumArray(array, resArray, 0, index - 1);
}
}
return resArray;
}
private static void printArray(int[] array){
int length = array.length;
String print = "[";
for(int i = 0; i < length; i++){
print = print + array[i];
if(i == length - 1){
print = print + "]";
} else {
print = print + ",";
}
}
System.out.println("Value: " + print);
}
}
class Solution {
public static void main(String[] args) {
int[] array = new int[]{0,2,5};
int[] newArray = new int[array.length];
int value = 25;
int index = array.length - 1;
printArray(sumArray(array, newArray, value, index));
}
private static int[] sumArray(int[] array, int[] resArray, int value, int index){
if(index >= 0){
int lastNumber = array[index];
int sum = lastNumber + value;
if(sum > 9){
resArray[index] = sum % 10;
sumArray(array, resArray, sum / 10, index - 1);
} else {
resArray[index] = sum;
sumArray(array, resArray, 0, index - 1);
}
}
return resArray;
}
private static void printArray(int[] array){
int length = array.length;
String print = "[";
for(int i = 0; i < length; i++){
print = print + array[i];
if(i == length - 1){
print = print + "]";
} else {
print = print + ",";
}
}
System.out.println("Value: " + print);
}
}
My solution in Java
private static int[] sumArray(int[] array, int[] resArray, int value, int index){
if(index >= 0){
int lastNumber = array[index];
int sum = lastNumber + value;
if(sum > 9){
resArray[index] = sum % 10;
sumArray(array, resArray, sum / 10, index - 1);
} else {
resArray[index] = sum;
sumArray(array, resArray, 0, index - 1);
}
}
return resArray;
}
C++ solution
class Solution
{
void addArray(vector<int>& m, int n)
{
if(m.size() == 0)
{
m.push_back(n);
return;
}
int carrier = n;
for(int i = (int)m.size()-1; i >= 0; i--)
{
carrier = (m[i] + carrier)/10;
m[i] = (m[i] + carrier)%10;
if(carrier == 0)
break;
}
if(carrier == 1)
m.insert(m.begin(), carrier);
}
};
My Solution in Java
public static int[] add(int[] arr, int num){
int fin = arr[arr.length -1];
int res = fin + num;
ArrayList<Integer> list = new ArrayList<>();
while(res > 9){
int m = res%10;
list.add(m);
res/= 10;
}
list.add(res);
int[] resArr = new int[arr.length -1 + list.size()];
int index = list.size();
for (int i = 0; i < resArr.length ; i++) {
if(i <= arr.length -2) resArr[i] = arr[i];
else resArr[i] = list.get(--index);
}
return resArr;
}
My solution in Java
public static int[] add(int[] arr, int num){
int fin = arr[arr.length -1];
int res = fin + num;
ArrayList<Integer> list = new ArrayList<>();
while(res > 9){
int m = res%10;
list.add(m);
res/= 10;
}
list.add(res);
int[] resArr = new int[arr.length -1 + list.size()];
int index = list.size();
for (int i = 0; i < resArr.length ; i++) {
if(i <= arr.length -2) resArr[i] = arr[i];
else resArr[i] = list.get(--index);
}
return resArr;
}
My Solution in php
time : O(4n + 2) // with helper variables.
space : O(4n + 2)
function addNumbersToDecimalList(array $list, $number)
{
$base = 10;
$i = count($list) - 1;
// while till to the $number is 0
while ($units = $number % $base) {
if (($res = (($units + $list[$i]) % $base)) == 0) {
$list[$i] = $units;
} else {
$list[$i] = $res;
$number = ($number - $res) / $base;
}
if (0 == $i) {
break;
}
--$i;
}
}
This is my solution using java
private static void addNumberToArray(int[] array, int number){
String stringNumber = "";
for(int i = 0; i < array.length; i++){
stringNumber = stringNumber + String.valueOf(array[i]);
}
int sum = Integer.parseInt(stringNumber) + number;
String sumString = String.format("%0" + array.length +"d", sum);
System.out.print(Arrays.toString(String.valueOf(sumString).split("")));
}
Java-
Keep adding the number to digits at different indices of the array, starting from the last index to 0.
int[] addNum(int[] arr, int num){
for(int i =arr.length-1;i>=0 && num!=0;i--){
num=num+arr[i];
arr[i]=num%10;
num=num/10;
}
if(num!=0){
int numLength = Integer.toString(num).length();
int[] retArr= new int[arr.length+numLength];
for(int i =numLength-1;i>=0;i--){
retArr[i]= num%10;
num=num/10;
}
for(int i=0;i<arr.length;i++){
retArr[i+numLength]=arr[i];
}
arr=retArr;
}
for(int i=0;i<arr.length;i++){
System.out.print(arr[i]+" ");
}
return arr;
}
void addnum(vector<int> &input, int num)
{
if(input.size() < 1)
return;
int carry = 0; int length = (int)input.size() -1;
int start = length;
while (start >= 0 && (carry > 0 || start == length)){
if(start == length)
input[start] = input[start] + num;
else
input[start] = input[start] + carry;
if(input[start] > 9){
carry = input[start] / 10;
input[start] = input[start] % 10;
}
else
carry = 0;
start--;
}
if(start < 0 && carry >= 1)
input.insert(input.begin(), carry);
}
int main (int argc, char *argv[])
{
vector<int> input = {1, 9, 2, 9, 9, 9};
int num = 9;
addnum(input, num);
for(int i = 0; i < input.size() ; i++)
cout << input[i] << " " ;
return 0;
}
I took a different approach to most people here.
Instead of complex looping, I did a simple number addition, and then added back in the extra leading 0's when needed!
function addNumerToArray(number, array) {
var i;
var arrayNumber = parseInt(array.join(''), 10);
var newNumberArray = (arrayNumber + number).toString().split('');
var difference = array.length - newNumberArray.length;
if (difference > 0) {
for (i = 0; i < difference; i++) {
newNumberArray.unshift(0);
}
}
return newNumberArray;
}
I took a different approach, I converted the array to a number, added the two numbers, then just added any extra leading 0's.
function addNumberToArray(number, array) {
var i;
var arrayNumber = parseInt(array.join(''), 10);
var newNumberArray = (arrayNumber + number).toString().split('');
var difference = array.length - newNumberArray.length;
if (difference > 0) {
for (i = 0; i < difference; i++) {
newNumberArray.unshift(0);
}
}
return newNumberArray;
}
My solution using python
- techinterviewquestion.com February 26, 2016