Amazon Interview Question for SDE1s

• 1
of 1 vote

Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
2
of 4 vote

Not a bad question - IMHO, about the right level for an interview. I can't believe how complicated in terms of algorithmic development or code some of the questions are here. Under the stress of an interview, I cant believe most people could do many of the questions posed here.

In any case, can we assume the numbers are both positive? If so, read each of the numbers into a vector (using push_back). Equalize the length of the two vectors to simplify the addition. Note that the digits in the vector will be in order, from MSD to LSD, so add on a corresponding number of 0s to the beginning of the smaller to make equal length with the longer. Now that they two are equal length, just iterate over the digits of both (from last to first digit), summing and storing sum mod 10 and propagating forward sum / 10. Oh, make sure sum has length = length of either (since same, equalized now) plus one, to accomodate for additional digit possible due to carry. Now write that sum vector back out, from MSD down to LSD.

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

This question reminds me of adding 2 numbers stored in linked lists. If that's what they looking for, I wonder why the extra silly complexity of asking candidates to read the number into a linked list (or vector) instead of just giving these directly. This question would seem much more reasonable IF the numbers are stored in reverse order. In other words, a file containing "001" actually means the number is 100. Then you can compute and write to the third file on the fly without additional data structure.

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

@dn Have u taken into consideration the two facts mentioned here:
1) A very large number &
2) return type of read() fn. is int

Not only you but all the answers below assume that the number can be read as a string which is not the case.

I wonder if something is missing in the question or we need to think more

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

@dn I mean you cant read the whole number as it is very large
& as for others you cant read it as a string either

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

Read this 2 files to 2 linked lists. Each node in the linked list will store a digit of the big number.
Now we have 2 linked lists representing 2 big numbers. Now the problem became, addition of 2 linked lists and store the result in 3rd list. This can be done in O(M+N) complexity.

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

Read the numbers as astring from the file.
Then iterate over the string and store in a linked list with each node of the linked list containing the digits of the number.
Now add the digits in the two linked list to get the sum in another linked list.
Need to take care of the MSD and LSD of the numbers.
Can store the linked list such that the head points ot the LSD.
Also need a carry integer.
The final result in the linked list will have to be stored in the output file.
Complexity: O(m) where m is the maximum number of digits out of the two input numbers.

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

Can you please provide the coded solution??

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

I am java guy, So i coded in Java. Please see code and make comment if not good solution.

import java.io.File;
import java.io.IOException;
import java.util.Iterator;

/*
* Complexity O(m+n).
*/

public class sumNumbersFromFiles {
public static void main(String[] args) throws IOException {
File file1 = new File("number1.txt");
String s1 = null;
}

s1 = null;
File file2 = new File("number2.txt");
}
//add numebrs from list1 and list2.
for(int i = 0 ; i < list1.size(); i++) {
int res = Integer.parseInt(list1.get(i))+Integer.parseInt(list2.get(i));
}

//print final list
Iterator<String> result = list3.iterator();
while(result.hasNext()) {
System.out.println(result.next());
}
}
}

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

Good Solution, but requires small modification at

1. how will it handle when a file contains value in a single line without any new line character.

2. If my number digit size vary in two files, then the logic will fails for 5492 and 999999

3. With the above logic the solution for following values will be 10131817 instead of 11497

File1:
5
4
9
8

File 2:
5
9
9
9

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

My mistake, i will update shortly... thanx TechTycoon

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

If input will not be in new line then i will take delimiter(like space etc.)

public class sumNumbersFromFiles {
public static void main(String[] args) throws IOException {
File file1 = new File("number1.txt");
String s1 = null;
StringBuffer sb1 = new StringBuffer();
sb1.append(s1);
}

s1 = null;
File file2 = new File("number2.txt");
StringBuffer sb2 = new StringBuffer();
sb2.append(s1);
}

if(sb1.length() != sb2.length()) {
if(sb1.length() > sb2.length()) {
}
else {
}
}

System.out.println("result =" + (Integer.parseInt(sb1.toString()) + Integer.parseInt(sb2.toString())) );
}

@SuppressWarnings("null")
private static String padding(StringBuffer sb1, StringBuffer sb2) {
StringBuffer bf = new StringBuffer();
for(int i = 0; i < (sb1.length()-sb2.length()) ; ++i) {
bf.append("0");
}
return bf.toString();
}
}

Please comment if this is not a good solution.

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

void AddTwoLargeNumb(string& outFileName, string& inFileName1, string& inFileName2)
{
vector<unsigned char> v1;
vector<unsigned char> v2;
vector<unsigned char> v3;

int minLen = v1.size() < v2.size() ? v1.size() : v2.size();

if(v1.size() > v2.size()){
v1.swap(v2);
}

int i = 0;
unsigned char carry(0);
unsigned char result;
unsigned char num1;
unsigned char num2;
int sum;
while(i < v1.size()){
num1 = v1[i];
num2 = v2[i];
sum = num1 + num2;
sum += carry;

result = sum & 0xFF;
carry = sum >> (sizeof(unsigned char) * 8);

v3.push_back(result);
i++;
}

while(i < v2.size()){
num2 = v2[i];
sum = carry + num2;

result = sum & numeric_limits<unsigned char>::max();
carry = sum >> (sizeof(unsigned char) * 8);
v3.push_back(result);
i++;
}

if(carry != 0){
v3.push_back(carry);
}

WriteLargeNumIntoFile(outFileName, v3);
}

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

first reverse the content of both the file by doing following.

``````Reverse(FILE *fp){
char c;
Reverse(fp);
else
return;
fwrite(&c, 1, 1, fp);
}``````

then just read one digit from both the file1 & file2 and add them and put it in file3.

``````bool flag[2] = {0, 0};
Add(FILE *fp1, FILE *fp2, FILE *fp3, int carry){
char d1, d2, dsum = 0;
dsum = (d2 + carry) % 10;
carry = dsum / 10;
do{
fwrite(&dsum, 1, 1, fp3);
return;
}

dsum = (d1 + carry) % 10;
carry = dsum / 10;
do{
fwrite(&dsum, 1, 1, fp3);
return;
}

dsum = (d1 + d2 + carry) % 10;
carry = dsum / 10;
fwrite(&dsum, 1 , 1, fp3);
}``````

Then reverse the content of file3.

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.