2
\$\begingroup\$

The problem is:

Intersection: Given two (singly) linked lists, determine if the two lists intersect. Return the intersecting node. Note that the intersection is defined based on reference, not value.

That is, if the kth node of the first linked list is the exact same node (by reference) as the jth node of the second linked list, then they are intersecting. Below is an example:

enter image description here The code I wrote is as following, may I know any improvement can be done?

  def intersecton[A](alist: List[A], blist:List[A]): Option[A]= (alist.last, blist.last)match{
    case (a,b) if (a!=b) => None
    case (_,_) if (alist.size>1 && blist.size>1 && alist(alist.size-2) != blist(blist.size-2)) => Some(alist.last)
    case (a,b) if (alist.size ==1||blist.size ==1)&& a==b => Some(a)
    case (_,_) => intersecton(alist.dropRight(1), blist.dropRight(1))
  }

Below is the test case I already run:

val list1: List[Int]=List(5,6, 1, 1, 4)
val list2: List[Int]=List(6, 1, 1,4)
>>6 

val list1: List[Int]=List(3,2,4)
val list2: List[Int]=List(5,6,7)
>>None


val list1: List[Int]=List(4,6,7)
 val list2: List[Int]=List(5,6,7)
>>6
\$\endgroup\$
  • \$\begingroup\$ Have you tested this code? If you believe that it works correctly, please show a few test cases. \$\endgroup\$ – 200_success Dec 4 '16 at 9:34
  • \$\begingroup\$ I have tested @200_success \$\endgroup\$ – sweetyBaby Dec 4 '16 at 9:36
  • \$\begingroup\$ Also, what is an "intersecton"? \$\endgroup\$ – 200_success Dec 4 '16 at 9:36
  • \$\begingroup\$ I have updated the description, let me know it is clear, thanks \$\endgroup\$ – sweetyBaby Dec 4 '16 at 9:40
  • 1
    \$\begingroup\$ @Vogel612 The code was broken, but the test cases demonstrate that the author was unaware of the bug. It's OK to discuss correctness in unanticipated cases. \$\endgroup\$ – 200_success Dec 4 '16 at 17:38
6
\$\begingroup\$

intersecton(List(1, 2, 4), List(4, 5, 6)) incorrectly returns None.


You've asked several questions recently, and I keep seeing similar issues:

You are welcome to use Code Review as a learning resource, but it would be a good idea to show some improvement between questions.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ intersecton(List(1, 2, 4), List(4, 5, 6)) incorrectly returns Non? Then, what do you think it should return? \$\endgroup\$ – sweetyBaby Dec 4 '16 at 10:41
  • \$\begingroup\$ @sweetyBaby it should return 4. because the 2nd index in list one is reference-equal to the 0th index in list two. I have elaborated a bit in a comment on your question \$\endgroup\$ – Vogel612 Dec 4 '16 at 11:37
  • \$\begingroup\$ @Vogel612, nope, maybe I did not describe very clearly, it should be none , I edited the problem description, thanks \$\endgroup\$ – sweetyBaby Dec 4 '16 at 11:40
  • \$\begingroup\$ Even with your added explanation, the answer should still be 4. The lists still intersect, and the question doesn't say that degenerate intersections should be prohibited. \$\endgroup\$ – 200_success Dec 4 '16 at 17:42
  • \$\begingroup\$ @200_success I thought you misunderstand the problem, Note that the intersection is defined based on reference, not value, it is the reference not just the value, if it should be 4, then following part should be the same, thanks \$\endgroup\$ – sweetyBaby Dec 5 '16 at 6:27
0
\$\begingroup\$

Here is my updated code for this problem:

def intersection[A](alist: List[A], blist:List[A]): List[A]= {
    alist.intersect(blist)
}
\$\endgroup\$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.