Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Finds the elements shared by 2 lists, FP style, recursively
object Intersect extends App{
import scala.annotation.tailrec
// finds the elements shared by 2 lists, FP style, recursively
// O(n log n)
@tailrec
def scan(x: List[Int], y: List[Int], out: List[Int] = List.empty[Int]): List[Int] =
(x, y) match {
case (xhead :: xtail, yhead :: ytail) =>
if (xhead == yhead) scan(xtail, ytail, xhead :: out)
else if (xhead < yhead) scan(xtail, y, out)
else scan(x, ytail, out)
case _ => out
}
def intersect(x: List[Int], y: List[Int]): List[Int] =
scan(x.sorted, y.sorted).reverse
val li1 = List(3, 6, 7, 1, 2)
val li2 = List(4, 5, 1, 6, 3, 20, 0)
println(intersect(li1, li2))
// sanity check, here we use Scala's inbuilt Set functionality
println(li1.toSet.intersect(li2.toSet))
// sanity check, and in built intersect
println(li1.intersect(li2))
// all the above show that common elements are 1, 3 and 6
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment