Skip to content

Instantly share code, notes, and snippets.

@stzr1123
Created November 4, 2019 20:36
Show Gist options
  • Save stzr1123/52f8da32ba6f52140b1c091f7e7931ed to your computer and use it in GitHub Desktop.
Save stzr1123/52f8da32ba6f52140b1c091f7e7931ed to your computer and use it in GitHub Desktop.
Interview type problems
import scala.annotation.tailrec
object ShittySolution {
// Given an array of integers, return indices of the two numbers such that they add up to a specific target.
//
// You may assume that each input would have exactly one solution, and you may not use the same element twice.
// https://leetcode.com/problems/two-sum/
// NB: More efficient solution would iterate once over the array and keep a Map of values and indicies
def twoSum(nums: Array[Int], target: Int): Array[Int] = {
for (idx <- 0 until nums.length - 1) {
for (idy <- idx + 1 until nums.length) {
if (nums(idx) + nums(idy) == target) {
return Array(idx, idy)
}
}
}
throw new IllegalArgumentException("No solution exists")
}
def functionalTwoSum(nums: Array[Int], target: Int): Array[Int] = {
val numsList = nums.toList
recursiveTwoSum(numsList.zipWithIndex, target) match {
case Some((idx, idy)) => Array(idx, idy)
case None => throw new IllegalArgumentException("No solution exists")
}
}
@tailrec
def recursiveTwoSum(nums: Seq[(Int, Int)], target: Int): Option[(Int, Int)] = {
nums match {
case Nil => None
case head::tail => tail.find{
case (elem, _) => elem + head._1 == target
} match {
case Some((_: Int, idy: Int)) => Some(head._2, idy)
case None => recursiveTwoSum(tail, target)
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment