Ebay Interview Question
Software DevelopersTeam: OpenStack
Country: United States
Interview Type: In-Person
ListNode sumList(ListNode l1, ListNode l2) {
int BASE = 10000;
if(l1 == null) return l2;
if(l2 == null) return l1;
ListNode l1Rev = reverse(l1);
ListNode l2Rev = reverse(l2);
ListNode dummyNode = new ListNode(0);
ListNode prev = dummyNode;
int carry = 0;
while(l1Rev != null && l2Rev != null) {
int l1Val = (l1Rev != null) ? l1Rev.val : 0;
int l2Val = (l2Rev != null) ? l2Rev.val : 0;
int sum = l1Val + l2Val + carry;
if(sum >= BASE)
carry = sum / BASE;
prev.next = new ListNode(sum % BASE)
l1Rev = (l1Rev.next == null) ? l1Rev : l1Rev.next;
l2Rev = (l2Rev.next == null) ? l2Rev : l2Rev.next;
}
if(carry >0)
prev.next = new ListNode(1);
return reverse(dummyNode.next);
}
ListNode reverse(ListNode head) {
ListNode newHead = null;
while(head != null) {
ListNode nextNode = head.next;
head.next = newHead;
newHead = head;
head = nextNode;
}
return newHead;
}
//Language: Scala
object Add2HugeNumbers{
val NoCarry = 0
val FixedLength = 4
def fourDigitPerTerm(ls: List[Int]): Boolean = ls match {
case Nil => true
case h::t => if (h.toString.length == FixedLength) fourDigitPerTerm(t) else false
}
def addNumbers(ls1: List[Int], ls2: List[Int]) = {
require(fourDigitPerTerm(ls1++ls2))
val ls1Reversed = ls1.reverse
val ls2Reversed = ls2.reverse
def internalAddNumbers(ls1: List[Int],
ls2: List[Int],
carry: Int = NoCarry,
acc: List[String] = Nil): List[String] = (ls1, ls2) match {
case (Nil, Nil) if carry == NoCarry => acc
case (Nil, Nil) => s"000$carry"::acc
case (_, _) => val elem = carry +
ls1.headOption.getOrElse(0) +
ls2.headOption.getOrElse(0)
val elemLength = elem.toString.length
val (c, addedElem) =
if (elemLength > FixedLength) (1, elem.toString.tail)
else (NoCarry, elem.toString)
internalAddNumbers(
if(ls1.isEmpty) Nil else ls1.tail,
if(ls2.isEmpty) Nil else ls2.tail, c,
"0"*(FixedLength-elemLength)+addedElem::acc)
}
internalAddNumbers(ls1Reversed, ls2Reversed)
}
}
}
- kirillskiy October 18, 2015