Amazon Interview Question
SDE1sCountry: India
Interview Type: In-Person
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.
@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
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.
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());
}
}
}
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
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.
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);
}
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.
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.
- dn June 23, 2013In 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.