Interview Question
SDE1sCountry: United States
Logic
1). list1 == 9 -> 9 -> 9 -> x
list2 == 1 -> 2 -> 3 -> x
2). Extract the number from any list, for our example say 123
3). Store results in list1
999*1 -> 999*2 -> 999*3 -> x
|
V
999 -> 1998 -> 2997 -> X
4). Process it like this
1). Reverse The linked list
2997 -> 1998 -> 999 -> x
7 -> (1998+299) -> 999 -> x
7 -> 2297 -> 999 -> x
7 -> 7 -> (999+229) -> x
5). Reverse The list(Result) 1228 -> 7 -> 7 -> x
Answer = 122877
Sample Program In Java
public class MultLists<T extends Comparable> {
public MultLists() {
super();
}
public static void main(String[] args) {
MultLists multLists = new MultLists();
MultLists.MultList list1 = multLists.new MultList();
MultLists.MultList list2 = multLists.new MultList();
for (int i = 1; i <= 3; i++) {
list1.insert(9);
// list2.insert(9);
}
// list1.insert(5);
// list1.insert(0);
// list1.insert(0);
list2.insert(1);
list2.insert(2);
list2.insert(3);
list1 = multLists.multiply(list1, list2);
list1.traverse();
}
public MultList<Integer> multiply(MultList<Integer> list1, MultList<Integer> list2) {
int s = 0;
LinkedNode<Integer> head = list1.getHead();
while (head != null) {
s = s * 10 + head.getData();
head = head.getNext();
}
head = list2.getHead();
while (head != null) {
head.setData(head.getData() * s);
head = head.getNext();
}
list2.traverse();
list2 = process(list2);
return list2;
}
public MultList<Integer> process(MultList<Integer> list) {
list = reverse(list);
list.traverse();
LinkedNode<Integer> head = list.getHead();
if (head == null)
return null;
int c = 0;
int i = 0;
while (head != null && head.getNext() != null) {
i = head.getData();
head.setData((i + c) % 10);
c = (i+c) / 10;
head = head.getNext();
}
head.setData(head.getData() + c);
list = reverse(list);
return list;
}
public MultList<Integer> reverse(MultList<Integer> list) {
if (list == null)
return null;
LinkedNode<Integer> head = list.getHead();
if (head == null)
return null;
LinkedNode<Integer> prev = null;
LinkedNode<Integer> temp = null;
while (head != null) {
temp = head;
head = head.getNext();
temp.setNext(prev);
prev = temp;
}
list.setHead(prev);
return list;
}
class MultList<T extends Comparable> {
private LinkedNode<T> head;
private LinkedNode<T> tail;
public int length() {
LinkedNode<T> head = this.getHead();
int i = 0;
while (head != null) {
i++;
head = head.getNext();
}
return i;
}
public void insert(T data) {
LinkedNode<T> item = new LinkedNode<T>(data);
if (this.getHead() == null) {
this.setHead(item);
this.setTail(item);
return;
}
this.getTail().setNext(item);
this.setTail(item);
}
public void traverse() {
LinkedNode<T> head = this.getHead();
while (head != null) {
System.out.print(head.getData() + "\t");
head = head.getNext();
}
System.out.println("\n");
}
public void setHead(LinkedNode<T> head) {
this.head = head;
}
public LinkedNode<T> getHead() {
return head;
}
public void setTail(LinkedNode<T> tail) {
this.tail = tail;
}
public LinkedNode<T> getTail() {
return tail;
}
}
class LinkedNode<T extends Comparable> {
private LinkedNode<T> next;
private T data;
public LinkedNode(T data) {
this.setData(data);
}
public int value(T data) {
return data instanceof Integer ? Integer.parseInt(data.toString()) : 0;
}
public void setNext(LinkedNode<T> next) {
this.next = next;
}
public LinkedNode<T> getNext() {
return next;
}
public void setData(T data) {
this.data = data;
}
public T getData() {
return data;
}
}
}
An alternative approach that avoids the need to first convert the 2 lists into integers. While that's probably more efficient, the interviewer will probably prohibit you because of its simplicity.
Here I am traversing the 2nd list once. For each iteration, I first multiply the existing total by 10. Then I traverse the first list to calculate the current product, and add it to the total. The O(n * m) where n & m are the list lengths.
public class MultiplyLists {
static class Node{
int value;
Node next;
public Node(int _value) {
value = _value;
}
static Node createList(String s) {
Node head = new Node(s.charAt(0) - '0');
Node prev = head;
for(int i=1; i<s.length(); i++) {
Node n2 = new Node(s.charAt(i) - '0');
prev.next = n2;
prev = n2;
}
return head;
}
}
static int multiply(Node n, Node n2) {
int total = 0;
while(n2 != null) {
Node head = n;
total *= 10;
int product = 0;
while(n != null) {
product *= 10;
product += n.value * n2.value;
n = n.next;
}
total += product;
n = head;
n2 = n2.next;
}
return total;
}
static public void main(String[] args) {
Node n = Node.createList(args[0]);
Node n2 = Node.createList(args[1]);
System.out.println(multiply(n, n2));
}
}
public static void multiplyLL(Node l1, Node l2)
{
Node rs = null;
Node mul = null;
int cnt = 0;
int[] cry = {0};
l2 = reverseLLUtil(l2);
while(l2 != null)
{
rs = multiplyLLUtil(l1, l2.data, cnt, cry);
if (cry[0] > 0)
{
Node tmp = new Node(cry[0]);
tmp.next = rs;
rs = tmp;
}
if (mul == null)
{
mul = rs;
}
else
{
mul = addLinkedList(mul, rs);
}
l2 = l2.next;
cry[0] = 0;
cnt++;
}
printLLUtil(mul);
}
public static void printLLUtil(Node node)
{
while(node != null)
{
System.out.print(node.data + " ");
node = node.next;
}
}
private static Node multiplyLLUtil(Node l1, int data, int cnt, int[] cry)
{
if (l1 == null)
{
Node tmp = null;
int i = 0;
while(i < cnt)
{
Node tmp1 = new Node(0);
if (tmp == null)
{
tmp = tmp1;
}
else
{
tmp1.next = tmp;
tmp = tmp1;
}
i++;
}
return tmp;
}
Node rs = null;
Node more = null;
more = multiplyLLUtil(l1.next, data, cnt, cry);
int d = l1.data * data + cry[0];
rs = new Node(d%10);
rs.next = more;
cry[0] = d/10;
return rs;
}
public static Node addLinkedList(Node l1, Node l2)
{
int l1Len = sizeOfLL(l1);
int l2Len = sizeOfLL(l2);
int[] cry = {0};
Node rs = null;
if (l1Len >= l2Len)
{
rs = addLinkedListRec(l1, l2, l1Len, l2Len, cry);
}
else
{
rs = addLinkedListRec(l2, l1, l2Len, l1Len, cry);
}
if (cry[0] > 0)
{
Node c = new Node(cry[0]);
c.next = rs;
rs = c;
}
return rs;
}
private static Node addLinkedListRec(Node l1, Node l2, int l1Len, int l2Len, int[] cry)
{
if (l1 == null && l2 == null)
{
cry[0] = 0;
return null;
}
Node result = null;
Node more = null;
int val = 0;
if (l1Len == l2Len)
{
more = addLinkedListRec(l1.next, l2.next, l1Len-1, l2Len-1, cry);
val = l1.data + l2.data + cry[0];
}
else
{
more = addLinkedListRec(l1.next, l2, l1Len-1, l2Len, cry);
val = l1.data + cry[0];
}
result = new Node(val %10);
result.next = more;
cry[0] = val/10;
return result;
}
Suppose 1234 * 567 answer is 699678
Represent 1234 and 567 as
x <-1 <- 2 <- 3<- 4
x<- 5 <- 6<- 7
Note numbers are represented in reverse order in the linked list.
Multiply 1234 * 7 and result linked list is
x <- 8 <- 6<- 3 <- 8
Multiply 1234 * 60 and result linked list is
x <- 7 <- 4 <- 0 <- 4 <- 0
Add these two linked list,
x<- 8 <- 2 <- 6 <- 7<- 8
Now, multiply 1234 * 500
x<-6<-1<-7<-0<-0<-0
Now add these two linked list to get
x<-6<-9<-9<-6<-7<-8
Answer is 699678
import java.util.*;
public class Multiply {
static List<Integer> l1 = new LinkedList<>();
static List<Integer> l2 = new LinkedList<>();;
static{
l1.add(1);
l1.add(0);
l1.add(0);
l2.add(9);
l2.add(9);
l2.add(9);
l2.add(9);
}
static List prod = new ArrayList<Integer>();
static List temp = new ArrayList<Integer>();
public static void main(String[] args)
{
int s1 = l1.size() -1, s2=l2.size() -1;
for(int i = s2; i>=0 ; i--)
{
temp = new ArrayList<Integer>();
for(int fill = s2; fill > i ; fill--)
temp.add(0);
int p = l2.get(i);
int carry = 0;
for(int j = s1; j >= 0 ; j--)
{
int prod = l1.get(j)*p + carry;
temp.add(0, prod%10);
carry = prod/10;
}
if(carry > 0)
temp.add(0, carry);
System.out.print(temp.toString());
System.out.print(" + ");
System.out.print(prod.toString());
addList(prod, temp);
System.out.print(" = ");
System.out.print(prod.toString());
System.out.println();
}
}
static void addList(List<Integer> result, List<Integer> l2)
{
int carry = 0, i = l2.size() -1, j = result.size() -1;
for(; i >= 0 && j >= 0; i--,j--)
{
int sum = result.get(j) + l2.get(i) + carry;
result.set(j, sum%10);
carry = sum/10;
//System.out.println(result.toString());
}
while(i >= 0)
{
int sum = l2.get(i--) + carry;
result.add(0, sum%10);
carry = sum/10;
}
while(j >= 0 && carry > 0)
{
int sum = result.get(j) + carry;
result.add(j, sum%10);
carry = sum/10;
j--;
}
if(carry > 0)
result.add(0, carry);
}
}
Use Recursion
Space complexity O(n)
n is the lenght of output
- dmrastogi July 06, 2015