[Linked Lists] interview questions #5

[rygh4775]

Sum Lists: You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in reverse order, such that the 1 's digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list. EXAMPLE Input: (7-) 1 -) 6) + (5 -) 9 -) 2) .Thatis,617 + 295. Output: 2 -) 1 -) 9. That is, 912. FOLLOW UP Suppose the digits are stored in forward order. Repeat the above problem. EXAMPLE Input: (6 -) 1 -) 7) + (2 -) 9 -) 5).Thatis,617 + 295. Output: 9 -) 1 -) 2. That is, 912.

[btakeya]

I tried to solve with translation, but calculate directly would be better (and I can't tried yet)

import scala.collection.mutable._

object Sum extends App {
  def getValue(a: Array[Int]): Int = {
    a.foldLeft(0)((acc, v) => acc * 10 + v)
  }

  def toArray(v: Int): Array[Int] = {
    var res = new ArrayBuffer[Int]
    var tmp = v
    while (tmp > 0) {
      res.prepend(tmp % 10)
      tmp /= 10
    }
    res.toArray
  }

  def getReverseValue(a: Array[Int]): Int = {
    a.foldRight(0)((v, acc) => acc * 10 + v)
  }

  def toReverseArray(v: Int): Array[Int] = {
    var res = new ArrayBuffer[Int]
    var tmp = v
    while (tmp > 0) {
      res += tmp % 10
      tmp /= 10
    }
    res.toArray
  }

  def sum(a1: Array[Int], a2: Array[Int]): Array[Int] = {
    val v1 = getValue(a1)
    val v2 = getValue(a2)
    toArray(v1 + v2)
  }

  def reverseSum(a1: Array[Int], a2: Array[Int]): Array[Int] = {
    val v1 = getReverseValue(a1)
    val v2 = getReverseValue(a2)
    toReverseArray(v1 + v2)
  }

  println(sum(Array(6, 1, 7), Array(2, 9, 5)).mkString("-"))
  println(reverseSum(Array(7, 1, 6), Array(5, 9, 2)).mkString("-"))
}

[btakeya]

TODO: calculate with list directly

[btakeya]

using reversed list only (456 -> List(6, 5, 4)) we can do sum and carry in one single step.

def sum(l1: List[Int], l2: List[Int]): List[Int] = {
  def naiveSum(longer: List[Int], shorter: List[Int]): List[Int] = {
    (for {
      index <- 0 until longer.size
    } yield longer(index) + (if (shorter.size > index) shorter(index) else 0)).toList
  }

  def carry(naive: List[Int]): List[Int] = {
    var carry = 0
    val buf = new ListBuffer[Int]
    for ((v, i) <- naive.view.zipWithIndex) {
      println(s"$v, $i")
      buf += v % 10 + carry
      carry = if (v > 10) 1 else 0
    }

    if (carry > 0) buf += 1

    buf.toList
  }

  val (l, s) = if (l1.size > l2.size) (l1, l2) else (l2, l1)

  val nSum = naiveSum(l, s)

  carry(nSum)
}

result:

println(sum(List(0, 2, 3), List(5, 5, 5))) // 5-7-8
println(sum(List(9, 2, 3), List(5, 0, 5))) // 4-3-8
println(sum(List(1, 2, 8), List(5, 5, 5))) // 6-7-3-1
println(sum(List(9, 9, 9), List(9, 9, 9))) // 8-9-9-1
=>
List(5, 7, 8)
List(4, 3, 8)
List(6, 7, 3, 1)
List(8, 9, 9, 1)

[btakeya]

using natural order list (123 -> List(1,2,3) we can do sum and carry in one single step also.

def reverseSum(l1: List[Int], l2: List[Int]): List[Int] = {
  def padding(r1: List[Int], r2: List[Int]): (List[Int], List[Int]) = {
    val (longer, shorter) = if (l1.size > l2.size) (l1, l2) else (l2, l1)
    val diff = longer.size - shorter.size
    (longer, List.fill(diff)(0) ::: shorter)
  }

  def naiveSum(l1: List[Int], l2: List[Int]): List[Int] = {
    (for {
      index <- 0 until l1.size
    } yield l1(index) + l2(index)).toList
  }

  def carry(naive: List[Int]): List[Int] = {
    val buf = new ListBuffer[Int]
    for ((v, i) <- naive.view.zipWithIndex) {
        if (v > 10) {
          if (i == 0) buf += 1
          else {
            val last = buf.last
            buf.remove(buf.size - 1)
            buf += last + 1
          }
        }
        buf += v % 10
    }

    buf.toList
  }

  val (first, second) = padding(l1, l2)

  val nSum = naiveSum(first, second)

  carry(nSum)
}

result:

println(reverseSum(List(2, 0, 3), List(5, 5, 5))) //7-5-8
println(reverseSum(List(9, 2, 3), List(5, 0, 5))) //1-4-2-8
println(reverseSum(List(1, 2, 8), List(5, 5, 5))) //6-8-3
println(reverseSum(List(9, 9, 9), List(9, 9, 9))) //1-9-9-8
println(reverseSum(List(1, 2, 3, 4), List(2, 2, 2))) // 1-4-5-6
println(reverseSum(List(2, 3, 4), List(2, 2, 2, 2))) // 2-4-5-6
=>
List(7, 5, 8)
List(1, 4, 2, 8)
List(6, 8, 3)
List(1, 9, 9, 8)
List(1, 4, 5, 6)
List(2, 4, 5, 6)

[btakeya]

reverseSum(list, list)에서 중간에 합이 10을 넘는 경우에는 해당 자리의 모든 윗자리에 재귀적으로 반영하는 스텝이 필요함