Amazon Interview Question for SDE1s


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.

- dn June 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Sunny June 24, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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

- Dsa June 25, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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

- Dsa June 25, 2013 | Flag
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.

- Vin June 24, 2013 | Flag Reply
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.

- subahjit June 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you please provide the coded solution??

- Sibendu June 24, 2013 | Flag
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.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.Iterator;
import java.util.LinkedList;

/*
* Read two files and store into the link lists and add these link list.
* Complexity O(m+n).
*/

public class sumNumbersFromFiles {
public static void main(String[] args) throws IOException {
File file1 = new File("number1.txt");
BufferedReader readFile1 = new BufferedReader(new FileReader(file1));
String s1 = null;
LinkedList<String> list1 = new LinkedList<String>();
while((s1 = readFile1.readLine()) != null ) {
list1.add(s1);
}

s1 = null;
File file2 = new File("number2.txt");
BufferedReader readFile2 = new BufferedReader(new FileReader(file2));
LinkedList<String> list2 = new LinkedList<String>();
while((s1 = readFile2.readLine()) != null ) {
list2.add(s1);
}
//add numebrs from list1 and list2.
LinkedList<String> list3 = new LinkedList<String>();
for(int i = 0 ; i < list1.size(); i++) {
int res = Integer.parseInt(list1.get(i))+Integer.parseInt(list2.get(i));
list3.add(Integer.toString(res));
}

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

- Sharma June 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- TechTycoon June 24, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Sharma June 24, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Please review my updated code.
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");
BufferedReader readFile1 = new BufferedReader(new FileReader(file1));
String s1 = null;
StringBuffer sb1 = new StringBuffer();
while((s1 = readFile1.readLine()) != null ) {
sb1.append(s1);
}

s1 = null;
File file2 = new File("number2.txt");
BufferedReader readFile2 = new BufferedReader(new FileReader(file2));
StringBuffer sb2 = new StringBuffer();
while((s1 = readFile2.readLine()) != null ) {
sb2.append(s1);
}

String padding = null;
if(sb1.length() != sb2.length()) {
if(sb1.length() > sb2.length()) {
padding = padding(sb1,sb2);
sb2.insert(0,padding);
}
else {
padding = padding(sb2,sb1);
sb1.insert(0,padding);
}
}

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.

- Sharma June 24, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

sites.google.com/site/spaceofjameschen/home/file-and-iostream/add-these-two-numbers-and-write-in-third-file-with-the-help-of-given-functions-only

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

ReadLargeNumIntoVec(inFileName1, v1);
ReadLargeNumIntoVec(inFileName2, v2);

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);
}

- Anonymous June 24, 2013 | Flag Reply
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;
	if(read(fp, &c, 1))
		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;
	if(!read(fp1, &d1, 1)){
		read(fp2, &d2, 1);
		dsum = (d2 + carry) % 10;
		carry = dsum / 10;
		do{
			fwrite(&dsum, 1, 1, fp3);
		}while(read(fp2, &dsum, 1));
		return;
	}

	if(!read(fp2, &d2, 1)){
		read(fp1, &d1, 1);
		dsum = (d1 + carry) % 10;
		carry = dsum / 10;
		do{
			fwrite(&dsum, 1, 1, fp3);
		}while(read(fp1, &dsum, 1));
		return;
	}
	
	dsum = (d1 + d2 + carry) % 10;
	carry = dsum / 10;
	fwrite(&dsum, 1 , 1, fp3);
        Add(fp1, fp2, fp3, carry);
}

Then reverse the content of file3.

- sanjay.rajputcse September 08, 2013 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More