Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Written Test
void my_add(char *n1,char * n2,char *n3)
{
int top=-1,carry,sum;
int i=0,j=0;
carry=0;
while(n1[i] && n2[j])
{
sum=n1[i] + n2[j] - 96 + carry;
printf("%d .. ",sum);
carry=sum/10;
sum%=10;
n3[++top]=(char)(sum+48);
i++;j++;
}
while(n1[i])
{
sum=n1[i] - 48 + carry;
carry=sum/10;
sum%=10;
n3[++top]=(char)(sum+48);
i++;
}
while(n2[j])
{
sum=n2[j] - 48 + carry;
carry=sum/10;
sum%=10;
n3[++top]=(char)(sum+48);
j++;
}
if(carry)
n3[++top]=(char)(carry+48);
n3[++top]='\0';
printf("%s",n3);
printf("Add\n");
}
package careercup;
/**
*
* @author patna
*/
public class Main {
public void addLargeNum(String num1, String num2){
int min = (num1.length() < num2.length()? num1.length():num2.length());
int max = (num1.length() < num2.length()? num2.length():num1.length());
int n1[] = new int[max];
int n2[] = new int[max];
System.out.println("max is "+max + "min is "+min);
for ( int i =0; i < num1.length() ; i++){
n1[i]= num1.charAt(num1.length()-1-i)-48;
}
System.out.printf(num1);
System.out.println("\n");
for ( int i =0; i < num2.length(); i++){
//System.out.println(i+" \t " + (num2.length()-1-i));
n2[i]= num2.charAt(num2.length()-1-i)-48;
}
System.out.printf(num2);
int carry = 0;
int sum[] = new int[max+1];
int k =0;
for ( k =0; k <max; k++){
sum[k] = (n1[k] + n2[k] + carry)%10;
if ( (n1[k]+n2[k]+carry) >= 10)
carry = 1;
else
carry = 0;
}
sum[max]=carry;
System.out.println("\n");
String result;
for ( int j = max; j >=0; j--){
//result.charAt(max-j)= (sum[j]+48);
System.out.printf("%d ",sum[j]);
}
}
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
Main obj = new Main();
obj.addLargeNum("999912346786", "99651234");
}
}
I wonder why no one could think of single linked list for this, maybe high memory requirements(?). Anyway, i just now figured out using 3 stacks we can do it, for best practices - using dynamic stack with doubly linked list for operands and for result.
n1 does not include '\0'
char* add (char* a1, int n1, char* a2, int n2)
{
if (n1 < n2)
{
return add (a2, n2, a1, n1);
}
char *s = new char[n1+2]; // 2: 1 for '\0', 1 for the possible carrier.
int ca = 0;
for (int i=n1; i>-1; i--)
{
int t = atoi(a1[n1]) + (n1-i) > n2 ? 0 : atoi(a2[i-n1+n2]) + ca;
s[n1-i] = t%10;
ca = t/10;
}
if (ca != 0)
{
s[n1+1] = ca;
s[n1+2] = '\0';
len = n1+1;
}
else
{
s[n1+1] = '\0';
len = n1;
}
revert (s, len);
return s;
}
void revert (char * s; int len)
{
int i=0, j=len;
while (i<j)
{
swap(s[i++], s[j--]);
}
}
static string add_str_nums(string str1, string str2)
{
string sum = "";
//Make strings the same length
str2 = new String('0', str1.Length - str2.Length) + str2;
str1 = new String('0', str2.Length - str1.Length) + str1;
//get string length
int str_len = str1.Length;
//init carryover
int carryover = 0;
//Step through strings adding each number, remembering to add carryover to the next number
for (int ii = str_len - 1; ii >= 0; ii--)
{
int val = Convert.ToInt32(str1.Substring(ii, 1)) + Convert.ToInt32(str2.Substring(ii, 1)) + carryover;
carryover = val / 10;
val = val % 10;
sum = val.ToString() + sum;
}
//If there was carry over, add it to the beginning of the number
if (carryover != 0)
{
sum = carryover.ToString() + sum;
}
return sum;
}
public class Add2Nos {
public static void main(String arg[]){
String number1 = new String(arg[0]);
String number2 = new String(arg[1]);
StringBuffer result = new StringBuffer();
int carry = 0;
int maxLength = number1.length()>number2.length()?number1.length():number2.length();
maxLength-=1;
number1 = equalize( number1, maxLength);
number2 = equalize( number2, maxLength);
while( maxLength>-1 ){
int value1 = getValue( number1, maxLength );
int value2 = getValue( number2, maxLength );
int sum = value1 + value2 + carry;
carry = sum / 10;
result.append( sum%10 );
maxLength--;
}
if( carry>0 ){
result.append(carry);
}
System.out.println( result.reverse() );
}
private static String equalize( String number , int size){
StringBuffer sb = new StringBuffer( number );
while( sb.length()<=size ){
sb.insert(0, '0');
}
return sb.toString();
}
private static int getValue(String text, int pos){
if( !(pos>text.length()-1) ){
return text.charAt(pos)-'0';
}
return 0;
}
}
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
void main()
{
char *str1="19999999999999999999999999";
char *str2="12999934556677898856565678";
char *str;
int len,lno1,lno2,carry=0;
len=strlen(str1)>strlen(str2)?strlen(str1):strlen(str2);
strlen(str1)>strlen(str2)?strcpy(str,str1):strcpy(str,str2);
lno1=strlen(str1)-1;
lno2=strlen(str2)-1;
while(lno1>=0 && lno2>=0 )
{
str[--len]='0'+((str1[lno1]-48)+(str2[lno2]-48)+carry)%10;
carry=(str1[lno1--]-48+str2[lno2--]-48+carry)/10;
}
while(carry)
{
str[len-1]='0'+(str[len]-48+carry)%10;
carry=(str[len--]-48+carry)/10;
}
printf("\n%s",str);
}
o/p
32999934556677898856565677
It has segmentation fault.
Str being accessed without being initialied.
Please can you tell on which compiler did this worked properly.
#include<iostream>
#include<fstream>
#include<conio.h>
using namespace std;
void read_into_buffer(std::istream& stream, char* buffer, int length) {
stream.read(buffer, length);
}
long getFileSize( char * fileName)
{
FILE * fp = NULL;
long size=0;
fp = fopen(fileName,"rb");
if (fileName == NULL)
{
return 0;
}
else
{
fseek(fp, 0, SEEK_END);
size = ftell(fp);
}
fclose(fp);
return size;
}
void reverse(char (*arr)[1024],const int size)
{
int start=0; int end=size-1; char temp;
while(end>start)
{
temp=(*arr)[end];
(*arr)[end]=(*arr)[start];
(*arr)[start]=temp;
start++;
end--;
}
}
int main()
{
char buffer1[1024];
char buffer2[1024];
char sum[1025];
char *pFile = "input1.txt";
char *pfile2 = "input2.txt";
long size1 = getFileSize(pFile);
long size2 = getFileSize(pfile2);
if (pFile == NULL || pfile2 == NULL)
{
return 0;
}
else
{
ifstream file(pFile);
read_into_buffer(file, buffer1, size1); // reads 10 bytes from the file
file.close();
buffer1[size1]='\0';
ifstream file2(pfile2);
read_into_buffer(file2, buffer2, size2);
file2.close();
buffer2[size2]='\0';
}
int smaller= size1>size2?size2:size1;
int index=0;
int carry=0; int temp=0;
reverse(&buffer1,size1);
reverse(&buffer2,size2);
cout<<buffer1<<endl;
cout<<" + "<<endl;
cout<<buffer2<<endl;
while(index<smaller)
{
temp=buffer1[index]-48+buffer2[index]-48+carry;
carry=0;
if(temp>9)
{
carry=temp/10;
temp=temp%10;
}
sum[index]=temp+48;
index++;
}
if(size1>size2)
{
while(index<size1)
{
temp=buffer1[index]+carry-48;
carry=0;
if(temp>9)
{
carry=temp/10;
temp=temp%10;
}
sum[index]=temp+48;
index++;
}
}else
{
while(index<size2)
{
temp=buffer2[index]+carry-48;
carry=0;
if(temp>9)
{
carry=temp/10;
temp=temp%10;
}
sum[index]=temp+48;
index++;
}
}
if(carry>0)
{ sum[index]=carry+48; index++;}
sum[index]='\0';
cout<<endl<<" == " <<endl<<sum<<endl;
getch();
return 0;
}
A solution in c
char * add(char str1[],char str2[])
{
char *a=str1,*b=str2,*c=NULL;
printf("Functon entry\n");
if(strlen(b)>strlen(a))
{
a=str2,b=str1;
}
int a_len = strlen(a),b_len = strlen(b);
c = (char*)malloc(sizeof(char)*(a_len+2));
memset(c,48,a_len+1);
int carry=0,sum=0,i;
for(i=1;i<=b_len;i++)
{
sum = a[a_len-i]+b[b_len-i]+carry-96;
c[a_len+1-i]= sum%10 + 48;
carry= sum/10;
}
while(carry && i<=a_len)
{
sum = a[a_len-i]+carry-48;
c[a_len+1-i]= sum%10 + 48;
carry= sum/10;
i++;
}
while(i<=a_len)
{
c[a_len+1-i]=a[a_len-i];
i++;
}
c[0]= carry +48;
c[a_len+1]='\0';
return c;
}
Visit the link: anshulsalvo.blogspot.in/2012/02/problem-20.html
- salvo4u June 23, 2012