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?

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]