Amazon Interview Question
Developer Program EngineersCountry: United States
Interview Type: Written Test
public class Subtract {
public static void main(String[] args) {
int[] A = {1,2,5,7,5};
int[] B = {3,4,8,9};
String result = String.valueOf(Integer.valueOf(getString(A)) - Integer.valueOf(getString(B)));
String[] resultStr = new String[result.length()];
System.out.println("Result: ");
System.out.print("{");
for(int loopCounter=0; loopCounter < result.length(); loopCounter++){
resultStr[loopCounter] = String.valueOf(result.charAt(loopCounter));
System.out.print(resultStr[loopCounter]);
if(loopCounter < (result.length()-1)){
System.out.print(", ");
}
}
System.out.print("}");
}
private static String getString(int[] array){
String str = "";
for(int loopCounter:array){
str = str + loopCounter;
}
return str;
}
}
public class JE2 {
public static void main(String[] args) {
// A - B
// A and B are an array of digits.
int A[] = {1, 0, 0, 3, 7, 5, 2};
int B[] = { 4, 2, 1, 0};
int C[];
C = LongSubtraction(A, B);
for(int i=0; i<C.length; i++)
System.out.print(C[i]+" ");
System.out.println("");
}
static int[] LongSubtraction(int[] a, int[] b) {
int[] c;
c = new int[a.length];
int borrow = 0;
for(int i=0; i<a.length; i++) {
int sub = a[a.length-1-i]-borrow - (i>=b.length? 0 : b[b.length-1-i]);
borrow = 0;
if(sub < 0) {
sub += 10;
borrow = 1;
}
c[c.length-1-i] = sub;
}
return c;
}
}
public class Diff {
static int a[] = {1,2,5,7,5};
static int b[] = {3,4,8,9};
static void difference(int a1[], int a2[]){
int i = 0, j;
int length1 = a1.length;
length1--;
i = a2.length-1;
while(i >= 0){
if(a1[length1] < a2[i]){
j = length1-1;
a1[length1] = a1[length1]+ 10-a2[i];
if(j>=0){
while(a1[j]==0){
a1[j] = 9;
j--;
}
a1[j] = a1[j] - 1;;
}
}
else{
a1[length1] = a1[length1]-a2[i];
}
length1--;
i--;
}
for(int i1 = 0; i1 < a1.length; i1++){
System.out.print(a1[i1]);
}
}
public static void main(String args[]){
int length1 = a.length;
int length2 = b.length;
if(length1 == length2){
while(true){
if(length1 == 0)
{
System.out.println(0);
break;
}
if(a[length1-1] > b[length1-1]){
difference(a,b);
break;
}
if(a[length1-1] < b[length1-1]){
difference(b,a);
break;
}
length1--;length2--;
}
}
else if(length1 > length2){
difference(a,b);
}
else{
difference(b,a);
}
}
}
static int[] sub(int[] a, int[] b){
int[] c = new int[a.length];
int i = a.length - 1;
int j = b.length - 1;
int borrow = 0;
while( j >= 0){
if(a[i] >= b[j]){
c[i] = a[i] - b[j] - borrow;
borrow = 0;
}
else{
c[i] = a[i] - b[j] - borrow + 10;
borrow = 1;
}
i--; j--;
}
while(i >= 0){
if(borrow == 1){
c[i] = a[i] - borrow;
borrow = 0;
}
else{
c[i] = a[i] ;
}
i--;
}
return c;
}
static int[] sub(int[] a, int[] b){
int[] c = new int[a.length];
int i = a.length - 1;
int j = b.length - 1;
int borrow = 0;
while( j >= 0){
if(a[i] >= b[j]){
c[i] = a[i] - b[j] - borrow;
borrow = 0;
}
else{
c[i] = a[i] - b[j] - borrow + 10;
borrow = 1;
}
i--; j--;
}
while(i >= 0){
if(borrow == 1){
c[i] = a[i] - borrow;
borrow = 0;
}
else{
c[i] = a[i] ;
}
i--;
}
return c;
}
public class Substract {
public static void main(String[] args) {
// TODO code application logic here
int[] A={1,2,5,7,5};
int[] B= {3,4,8,9};
int[] C= new int[A.length];
int i=A.length-1;
for(int j=B.length-1;j>=0;j--)
{
if(A[i]<B[j])
{
A[i]=A[i]+10;
A[i-1]=A[i-1]-1;
C[i]=A[i]-B[j];
}
else{
C[i]=A[i]-B[j];
}
System.out.print(A[i]+"");
System.out.print(B[j]+"");
System.out.print(C[i]+"");
System.out.println("");
i--;
}
while(i>=0&&A[i]!=0){
C[i]=A[i];
}
for(int m=0;m<C.length;m++)
{
System.out.print(C[m]+"");
}
}
}
I feel this one of the easiest of all the implementations given here:
public class Subtract {
public static void main(String[] args) {
int[] A = {1,2,5,7,5};
int[] B = {3,4,8,9};
int[] C = new int[A.length]; //The Resultant array will be atmost the length of the longest array
int num1 , num2, k=0;
for(int i = A.length - 1;i>=0 ;i--){ //Iterating from the end of the array
num1 = A[i]; //Taking the least significant digit of 1st array
try{
num2 = B[B.length-1-k];
}catch(Exception e){
num2 = 0;
}
if(num1<num2){
num1 = num1+10; //If less, add 10
A[i-1] = A[i-1]-1;
}
C[i] = num1-num2;
k++;
}
for (int i =0;i<C.length;i++)
System.out.print(C[i]);
}
}
Can someone please correct me with the time complexity of the algorithm. I believe it's O(max(len_A, len_B))
def difference_to_list(A, B):
if (len(A) or len(B)) > 20:
print "Cannot perform subtraction of list more than 20"
else:
number_a = 0
number_b = 0
for i in range(len(A)):
number_a += A[i]*10**(len(A)-i-1)
for j in range(len(B)):
number_b += B[j]*10**(len(B)-j-1)
diff = number_a - number_b
print list(str(diff))
A minor correction
import sys
def difference_to_list(A, B):
if (len(A) or len(B)) > 20:
print "Cannot perform subtraction of list more than 20"
sys.exit(1)
else:
number_a = 0
number_b = 0
for i in range(len(A)):
number_a += A[i]*10**(len(A)-i-1)
for j in range(len(B)):
number_b += B[j]*10**(len(B)-j-1)
diff = number_a - number_b
return list(str(diff))
def sub(A, B):
if len(A) == len(B):
if A[0] > B[0]:
larger = A
smaller = B
else:
larger = B
smaller = A
else:
if len(A) > len(B):
larger = A
smaller = B
else:
larger = B
smaller = A
offset = len(larger) - len(smaller)
for i, bottom in enumerate(smaller, offset):
if larger[i] < bottom:
larger[i-1] -= 1
larger[i] = larger[i] + 10 - bottom
else:
larger[i] -= bottom
zeros = 0
while larger[zeros] == 0:
zeros += 1
return larger[zeros:]
- nani2say October 12, 2013