Closest 3Sum in Scala
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.
interview-questions functional-programming comparative-review scala k-sum
edited 19 mins ago
200_success
128k15150412
asked 57 mins ago
vikrant
717
add a comment |
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.
interview-questions functional-programming comparative-review scala k-sum
edited 19 mins ago
200_success
128k15150412
asked 57 mins ago
vikrant
717
add a comment |
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.
interview-questions functional-programming comparative-review scala k-sum
edited 19 mins ago
200_success
128k15150412
asked 57 mins ago
vikrant
717
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.
interview-questions functional-programming comparative-review scala k-sum
interview-questions functional-programming comparative-review scala k-sum
edited 19 mins ago
200_success
128k15150412
asked 57 mins ago
vikrant
717
edited 19 mins ago
200_success
128k15150412
asked 57 mins ago
vikrant
717
edited 19 mins ago
200_success
128k15150412
edited 19 mins ago
200_success
128k15150412
edited 19 mins ago
200_success
128k15150412
128k15150412
asked 57 mins ago
vikrant
717
asked 57 mins ago
vikrant
717
asked 57 mins ago
vikrant
717
717
add a comment |
add a comment |
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
});
});
}, "mathjax-editing");
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "196"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f210522%2fclosest-3sum-in-scala%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Code Review Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f210522%2fclosest-3sum-in-scala%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
