Find The Merge Point Of Two Lists

September 2, 2016

Given two lists, the merge point is the point after which the two lists are identical and can be merged. For instance, given the lists (a b c x y z) and (g h i x y z), the merge point is at (x y z). If the last items in the two lists differ, the merge point is null; if the two lists are the same, the entire list is the merge point.

Your task is to write a program that finds the merge point of two lists; it should return the unique prefix of the first list, the unique prefix of the second list, and the common suffix of the two lists. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

10 Responses to “Find The Merge Point Of Two Lists”

  1. Daniel said

    Here’s a solution in Java.

    import java.util.ArrayList;
    import java.util.Collections;
    import java.util.List;
    
    public class MergePoint {
      public static class Result<T> {
        public List<T> prefix1 = new ArrayList<>();
        public List<T> prefix2 = new ArrayList<>();
        public List<T> suffix = new ArrayList<>();
      }
      
      public static <T> Result<T> merge_point(List<T> l1, List<T> l2) {
        Result<T> result = new Result<>();
        int suffix_len = 0;
        while (true) {
          int index1 = l1.size() - 1 - suffix_len;
          int index2 = l2.size() - 1 - suffix_len;
          if (index1 < 0 || index2 < 0) break;
          if (!l1.get(index1).equals(l2.get(index2))) break;
          ++suffix_len;
        }
        for (int i = 0; i < l1.size() - suffix_len; ++i)
          result.prefix1.add(l1.get(i));
        for (int i = 0; i < l2.size() - suffix_len; ++i)
          result.prefix2.add(l2.get(i));
        for (int i = l1.size() - suffix_len; i < l1.size(); ++i) 
          result.suffix.add(l1.get(i));
        return result;
      }
    
      public static void main(String[] args) {
        List<Character> l1 = new ArrayList<>();
        Collections.addAll(l1, 'a', 'b', 'c', 'x', 'y', 'z');
        List<Character> l2 = new ArrayList<>();
        Collections.addAll(l2, 'g', 'h', 'i', 'x', 'y', 'z');
        Result<Character> result = merge_point(l1, l2);
        System.out.print("List 1 Unique Prefix\n" + result.prefix1 + "\n\n");
        System.out.print("List 2 Unique Prefix\n" + result.prefix2 + "\n\n");
        System.out.print("Common Suffix\n" + result.suffix + "\n");
      }
    }
    

    Output:

    List 1 Unique Prefix
    [a, b, c]
    
    List 2 Unique Prefix
    [g, h, i]
    
    Common Suffix
    [x, y, z]
    
  2. Zack said

    Here is one for Julia (0.000088 sec to execute, applying a total of 64 memory allocations).

    function main{T = ny
    x, y = x_, y_
    else
    x, y = y_, x_
    nx, ny = ny, nx
    end

    dn = ny – nx # negative difference of lengths

    for i = (nx – ny + 1):(nx – 1)
    j = dn + i

    if all(x[i:end] .== y[j:end])
    return x[1:(i-1)], y[1:(j-1)], x[i:end]
    end
    end

    return x_, y_, Array(T, 0)
    end

    This code is optimized for unequal lists, although it works quite fast on equal ones too. As usual, no external libraries were used.

  3. Zack said

    For some reason the code didn’t paste properly. Here it is again, this time on a .png file: https://app.box.com/s/0fhupoyexwx26dv6trb7ud8mgs30ntz9

  4. In Common Lisp :

    (defun merge-point (lst1 lst2)
      (let ((res (merge-point-helper (reverse lst1)
    				 (reverse lst2)
    				 nil)))
        (list (nreverse (car res))
    	  (nreverse (cadr res))
    	  (caddr res))))
    
    (defun merge-point-helper (lst1 lst2 common)
      (if (or (null lst1)
    	  (null lst2))
          (list lst1 lst2 common)
          (if (equal (car lst1) (car lst2))
    	  (diverge-point
    	   (cdr lst1)
    	   (cdr lst2)
    	   (cons (car lst1) common))
    	  (list lst1 lst2 common))))
    

    A few tests:

    CL-USER> (merge-point '(a b c x y z) '(g h i x y z))
    ((A B C) (G H I) (X Y Z))
    CL-USER> (merge-point '(y z) '(g h i x y z))
    (NIL (G H I X) (Y Z))
    
  5. An error in my last comment, the code is :

    (defun merge-point (lst1 lst2)
      (let ((res (merge-point-helper (reverse lst1)
    				 (reverse lst2)
    				 nil)))
        (list (nreverse (car res))
    	  (nreverse (cadr res))
    	  (caddr res))))
    
    (defun merge-point-helper (lst1 lst2 common)
      (if (or (null lst1)
    	  (null lst2))
          (list lst1 lst2 common)
          (if (equal (car lst1) (car lst2))
    	  (merge-point-helper
    	   (cdr lst1)
    	   (cdr lst2)
    	   (cons (car lst1) common))
    	  (list lst1 lst2 common))))
    
  6. Paul said

    In Python3.

    from itertools import zip_longest
    
    def merge_point(a, b):
        ita, itb = reversed(a), reversed(b)
        suffix, prefixa, prefixb = [], [], []
        for x, y in zip_longest(ita, itb):
            if x != y:
                if x: prefixa.append(x)
                if y: prefixb.append(y)
                break
            else:
                suffix.append(x)
        prefixa += ita
        prefixb += itb
        return prefixa[::-1], prefixb[::-1], suffix[::-1]
    
    r5 = [1, 2, 3, 4, 5]
    tests = [(r5, [6, 7, 3, 4, 5]), ([1, 2, 3, 4, 8], [6, 7, 3, 4, 5]),
             (r5, r5), (r5, [3, 4, 5]), ([3, 4, 5], r5), ([1, 3, 4, 5], r5)
             ]
    for t in tests:
        print("input:{:40s} output:{:s}".format(str(t), str(merge_point(*t))))
    """
    input:([1, 2, 3, 4, 5], [6, 7, 3, 4, 5])       output:([1, 2], [6, 7], [3, 4, 5])
    input:([1, 2, 3, 4, 8], [6, 7, 3, 4, 5])       output:([1, 2, 3, 4, 8], [6, 7, 3, 4, 5], [])
    input:([1, 2, 3, 4, 5], [1, 2, 3, 4, 5])       output:([], [], [1, 2, 3, 4, 5])
    input:([1, 2, 3, 4, 5], [3, 4, 5])             output:([1, 2], [], [3, 4, 5])
    input:([3, 4, 5], [1, 2, 3, 4, 5])             output:([], [1, 2], [3, 4, 5])
    input:([1, 3, 4, 5], [1, 2, 3, 4, 5])          output:([1], [1, 2], [3, 4, 5])
    """
    
  7. Scott said

    (defun merge-point (lst1 lst2)
    (do ((l1 (reverse lst1) (cdr l1))
    (l2 (reverse lst2) (cdr l2))
    (merge-point ‘()))
    ((or (and (null l1) (null l2)) (not (eq (car l1) (car l2))))
    (values (reverse l1) (reverse l2) merge-point))
    (push (car l1) merge-point)))

  8. akshaya pandey said

    package test;

    public class MergePoint {
    public static int mergePoint(int a[],int b[]){
    int aMergePoint=a.length;
    int bMergePoint=b.length;
    int alength=a.length;
    int blength=b.length;

    for(int i=alength-1,j=blength-1;i>=0 && j>=0 && a[i]==b[j]; i–,j–){
    aMergePoint–;bMergePoint–;
    }
    System.out.println(“\n aMergePoint”+ aMergePoint);
    System.out.println(“Suffix”);
    for(int i=aMergePoint;i<a.length;i++){
    System.out.print(a[i]);
    }
    System.out.println("\nAPrefix");
    for(int i=0;i<aMergePoint;i++){
    System.out.print(a[i]);
    }
    System.out.println("\nBPrefix");
    for(int i=0;i<bMergePoint;i++){
    System.out.print(b[i]);
    }
    for(int i=aMergePoint;i<aMergePoint;i++){
    System.out.print(a[i]);
    }
    return aMergePoint ;
    }
    public static void main(String args[]){
    int a[]={1,2,3,4,5,6,7,8,9};
    int b[]={5,6,7,4,5,6,7,8,9};
    mergePoint(a,b);
    }
    }

  9. Zack said

    @Jérôme. Great job implementing this in Lisp; not many people could handle that! This reminds me of my university days when I scribbled a few Lisp scripts myself. I’m quite curious about the performance of this language for this task, so any information about that would be very much appreciated.

  10. Johan said

    In Common Lisp, using the built-in functions MISMATCH and SUBSEQ:

    (defun merge-point (xs ys &key (test #'eql))
      (let ((m (length xs))
            (n (length ys))
            (i (mismatch (reverse xs) (reverse ys) :test test)))
        (if (null i)
            (values () () xs)
            (values (subseq xs 0 (- m i))
                    (subseq ys 0 (- n i))
                    (subseq xs (- m i))))))
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: