1
\$\begingroup\$

This question is taken from Leet code.

Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

Given array nums = [-1, 2, 1, -4], and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

I need feedback on my solution from programming interview perspective (where they rate you on quality of solution).

My first solution is this (and preferred)

scala> ((List(-1,2,1,-4).combinations(3).map(_.sum) map (sum => (sum,Math.abs(1-sum))) toList) sortWith(_._2 < _._2)).head._1
res166: Int = 2

But I expect interviewer might ask me to implement combinations (and use one provided by library) . So I implemented the same like this

def combinations(l: List[Int], c: Int): List[List[Int]] = {
    if (c == 1) { l map { r => List(r) } }else {
      l match {
        case Nil => List.empty
        case head::tail =>
          (combinations(tail, c-1) map { r => head :: r }) ++ combinations(tail, c)
      }
    }
  }

I think this one is good enough to solve this problem (from point of view of interview).

But after solving this I came across a question on SO where folks are trying to solve it without getting in O(n3) complexity. Kindly suggest me how you would solve it.

Also please suggest me how I should handle this scenario where I think solution I gave is best for the problem.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.