SumList Cracking the coding Interview

Question

Sum of 2 numbers, represented with linked lists, where digits are in backward order or forward order.

Backward order Example

• INPUT:(7->1->6) + (5->9->2) = 617+295
• OUTPUT: 2->1->9 = 912

Forward order Example

• INPUT:(7->1->6) + (5->9->2) = 716+592
• OUTPUT: 1>-3->0->8 = 1308

I'm starting with this method. I'm giving it list and size and I'm extrapolating each digit with base 10 notation. Time complexity should be O(n) for each list, and Space complexity should be O(1). Am I right?

public static int getNumber(LinkedList<Integer> num_list,int size){
 int number= 0;
 int pow = 0;//size-1 if it's in forward order
 for (int d: num_list){
 number += d * Math.pow(10.0, pow);
 pow++;//pow-- if it's in forward order
 }
 return number;
 }

Main

LinkedList<Integer> num1 = new LinkedList<>();
 LinkedList<Integer> num2 = new LinkedList<>();
 int sum,temp;
 int count_digit = 0;
 num1.add(7);
 num1.add(1);
 num1.add(6);
 num2.add(5);
 num2.add(9);
 num2.add(2);
 sum = getNumber(num1,num1.size()) + getNumber(num2,num2.size());
 temp = sum;
 
 //Counting the number of digits
 while(temp!=0){
 temp /= 10;
 count_digit++;
 }
 LinkedList<Integer> result = new LinkedList<>();

Backward Solution

In that case, Space complexity should be O(1) and time O(n). Right?

for (int i = 0; i < count_digit;i++){
 temp = sum % 10;
 sum/= 10;
 result.add(temp);
 }
 for(int d: result)
 System.out.print(d);//Print node
 System.out.println();
 System.out.println(getNumber(result, result.size())); //print result

Frontward Solution

I didn't find any way to not implement another Structure. In that case, I changed getNumber method, using commented code.

int[] digit = new int[count_digit];
 for(int i = digit.length-1; i >= 0; i--){
 temp = sum % 10;
 digit[i]= temp;
 sum/= 10;
 }
 for(int d: digit){
 System.out.print(d);
 result.add(d);
 }
 //Just checking
 System.out.println();
 for (int d: result)
 System.out.println(d);

At the end time complexity should be O(3n) (first list+ second list + array population) and, if I'm right, it should be considered like O(n). Space complexity should be O(n). There is a way to reduce space complexity?

• dariosicily: Hello, are you sure your code is working as expected ?
• Uomolepre: @dariosicily I've fixed the code. Can you answer my question?
• dariosicily: You wrote OUTPUT: 1>-3->0->8 = 1308. This for me means you have to create a List as output, there's no trace of it in your code, if the output was just a number , there wouldn't need to specify the list.
• Uomolepre: @dariosicily I'm sorry, but I didn't get what you mean. I've created the list result as output. In backward, I've populated it during the extrapolation of each digit. In forward I've created in a first moment an array, and later I've filled the list
• dariosicily: To put it simply, I executed your code and it prints something traceable to what you expect. Have you code I can execute obtaining the expected output ? If not, Code Review users can review just working code as expected and at the moment this is not your case.

Answer 1

(I've read the book, solved the problems and passed the interview)

The purpose of this exercise is to use the properties of lists to your advantage, and show your understanding of them; as well as teaching you to ask the right questions: How big can the numbers be? Will they overflow an int/long? Can they be negative? Will both of the lists fit in memory? Is the input guaranteed to be well formed? Converting to int and back is kind of missing the point...

For example here I do a solution for positive values where both lists and the output will fit in memory but overflow int/long:

List<Integer> revsum(Iterator<Integer> a, Iterator<Integer> b){
 var ans = new LinkedList<Integer>();
 int carry = 0;
 while(a.hasNext() || b.hasNext()){
 int A = a.hasNext() ? a.next() : 0;
 int B = b.hasNext() ? b.next() : 0;
 int S = A + B + carry;
 ans.add(S%10);
 carry = S /10;
 }
 if(carry > 0){
 ans.add(carry);
 }
 return ans;
}
List<Integer> forward(List<Integer> a, List<Integer> B){
 return revsum (a.descendingIterator(), b.descendingIterator()).reverse();
}
List<Integer> backward(List<Integer> a, List<Integer> B){
 return revsum (a.iterator(), b.iterator());
}
 

You should practice and build a better version that can handle negative numbers and bad inputs as well.

The best case conceivable time complexity is O(n) as you have to iterate all inputs. Likewise additional space complexity in addition to inputs and outputs is O(1) .

Answer 2

There are two main suggestions I would recommend:

1. Use separate methods to reuse code when able to.
2. Take advantage of the tools already in the Java library.

LinkedList already has a method built in to return a descendingIterator() which can be used to handle the backwards read. You can also take advantage of various capabilities in the String and Integer classes to handle the combination and separation of list values.

Here's an example of one way you could leverage the library tools and better take advantage of code reuse:

import java.util.Arrays;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;
public class LinkedListTest {
 public static void main(String[] args) {
 //Build data
 var num1 = new LinkedList<Integer>(Arrays.asList(7, 1, 6));
 var num2 = new LinkedList<Integer>(Arrays.asList(5, 9, 2));
 
 //Convert list to whole integer
 var num1Forward = convertToInt(num1.iterator());
 var num2Forward = convertToInt(num2.iterator());
 
 //Sum integers and convert back to list
 var sumForward = convertToLinkedList(num1Forward + num2Forward);
 
 System.out.println("Forward: " + num1Forward + " + " + num2Forward + " = " + sumForward);
 
 //Convert list to whole integer in reverse order
 var num1Backward = convertToInt(num1.descendingIterator());
 var num2Backward = convertToInt(num2.descendingIterator());
 
 //Sum integers and convert back to list
 var sumBackward = convertToLinkedList(num1Backward + num2Backward);
 
 //Reverse the returned list using library tool
 Collections.reverse(sumBackward);
 
 System.out.println("Backward: " + num1Backward + " + " + num2Backward + " = " + sumBackward);
 }
 
 public static int convertToInt(Iterator<Integer> numberIterator) {
 var combine = "";
 
 //Concatenate values feed from iterator into a String
 while(numberIterator.hasNext())
 combine += numberIterator.next();
 
 //Use Integer class to parse the String back to a whole Integer
 return Integer.parseInt(combine);
 }
 
 public static LinkedList<Integer> convertToLinkedList(int value) {
 var list = new LinkedList<Integer>();
 
 //Convert value to String and use split() to break value into individual digits
 var splitValues = Integer.toString(value).split("");
 
 //Use Integer to parse digits into Integers and add to the list
 Arrays.stream(splitValues).map(Integer::parseInt).forEach(list::add);
 
 return list;
 }
 
}

Output:

Forward: 716 + 592 = [1, 3, 0, 8]
Backward: 617 + 295 = [2, 1, 9]