Ebay Interview Question for Software Developers


Team: OpenStack
Country: United States
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
0
of 0 vote

//Lets have 0th elements of lists containing lower digits.
//Otherwise start with rotating lists e.g with a stack.
public static Short BASE = 10000

public List<Short> addTwoHugeNumbers(List<Short> a, List<Short> b) {
	Iterator<Short> iterA = a.iterator();
	Iterator<Short> iterB = b.iterator();
	
	List<Short> result = new LinkedList<>(); 
	Short overflow = 0;

	while(true) {
		Short nextA = null;
		Short nextB = null;
		if (iterA.hasNext()) {
			nextA = iterA.next();
		}
		if (iterB.hasNext()) {
			nextB = iterB.next();
		}
		if (nextA == null && nextB == null) {
			//no more digits to add, worl done
			break;
		}
		if (nextA == null) {
			nextA = 0;
		}
		if (nextB == null) {
			nextB = 0;
		}
		Short nextSum = nextA + nextB + overflow;
		Short nextDigit = nextSum % BASE;
		result.add(nextDigit);
		overflow = nextSum / BASE;
	}
	if (overflow != 0) {
		result.add(overflow);
	}
	return result;
}

}

- kirillskiy October 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Reverse both linked lists.
Add the node values and send the carry over to the next node.
Reverse the result list

- zd October 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- hivehome June 13, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//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)
  }
  
}

- sidproquo August 28, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Stores values in separate stacks and then keep popping elements. We should use stacks in order to keep original LinkedLists intact. (if that's the business rule!)

- Rush February 06, 2017 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More