Find Two Added Integers

December 16, 2014

My solution solves a slightly different problem: instead of integers, it takes a less-than ordering function so that it can use any data type; instead of limiting to two additional items, it finds all additional items; and instead of working from one list to the other, it works simultaneously in both directions, showing additional items in both lists. It works by sorting both lists, then running through them in order, accumulating all differences:

(define (diffs lt? xs ys)
  (let loop ((xs (sort lt? xs)) (ys (sort lt? ys)) (adds (list)) (subs (list)))
    (cond ((and (null? xs) (null? ys)) (values adds subs))
          ((null? xs) (loop xs (cdr ys) (cons (car ys) adds) subs))
          ((null? ys) (loop (cdr xs) ys adds (cons (car xs) subs)))
          ((lt? (car xs) (car ys)) (loop (cdr xs) ys adds (cons (car xs) subs)))
          ((lt? (car ys) (car xs)) (loop xs (cdr ys) (cons (car ys) adds) subs))
          (else (loop (cdr xs) (cdr ys) adds subs)))))

To use this for the interview question, say:

(define (interview a b)
  (call-with-values
    (lambda () (diffs < a b))
    (lambda (adds subs) subs)))

For example:

> (interview '(1 4 9 2 7 3) '(9 7 4 1))
(3 2)

That has time complexity O(n log n). There is a similar solution based on hashing instead of sorting (be careful of duplicate items!), which has a time complexity of O(n), but I imagine in practice there is little difference between the two algorithms unless n is large.

You can run the program at http://programmingpraxis.codepad.org/FDNaZZGG.

I got mad when I saw this exercise because the suggested solution utilized the facts that the list items were integers and there were exactly two additional items. A single scan through the list produces the two sums of the list items and the two products of the list items, then, since the sum of the first list will be x + y greater than the second list and the product of the first list will be x × y greater than the product of the second list, you can solve the diophantine equation and determine x and y. That takes O(n) time and O(1) space, ignoring problems of overflow of either the sum or the product.

Any candidate that came up with the suggested solution would leave me in awe of his cleverness, but probably wouldn’t be invited back for a second interview. In the first place, the solution is just too clever; I can imagine maintaining the program, finding that clever solution, being unable to understand it, and replacing it with the solution proposed above. And in the second place, the clever solution, specific to the desired task, is far less useful than the general solution proposed above that can handle any number of differences, in either direction, of any data type. That’s clever!

Pages: 1 2

15 Responses to “Find Two Added Integers”

  1. Andras said

    Scala. It handles if the lists are not sets…
    val list1 = List(1, 4, 9, 2, 7, 3, 1, 4, 9, 2, 7, 3)
    val list2 = List(9, 7, 4, 1,9, 7, 4, 1)
    list1.toSet–list2.toSet //> res0: scala.collection.immutable.Set[Int] = Set(2, 3)

  2. Includes counts of missing numbers…

    my @list1 = (1, 4, 9, 2, 7, 3, 1, 4, 9, 2, 7, 3);
    my @list2 = (9, 7, 4, 1, 9, 7, 4, 1);
    my %x;
    $x{$_}++ foreach @list1;
    $x{$_}-- foreach @list2;
    print join q(; ), map { "$x{$_} x $_" } grep {$x{$_}} keys %x;
    print "\n";
    

    ;

  3. Forgot to say… this returns -ve values if the entry is in list2 but not in list1!

    my @list1 = (1, 4, 9, 2, 7, 3, 1, 4, 9, 2, 7, 3);
    my @list2 = (9, 7, 4, 1, 9, 7, 4, 1);
    my %x;
    $x{$_}=1 foreach @list1;
    $x{$_}=0 foreach @list2;
    print join q(; ), {$x{$_}} keys %x;
    print "\n";
    

    This one ignores duplicates… question is ambiguous..

  4. Rahul Chandna said

    import java.util.List;

    public class TwoAddedIntegers {

        private List listOne;
        private List listTwo;

        public TwoAddedIntegers(List listOne, List listTwo) {
            this.listOne = listOne;
            this.listTwo = listTwo;
        }

        public String getAdditionalIntegers(){
            for(Integer number:listTwo){
                if(listOne.contains(number)){
                    listOne.remove(number);
                }
            }
            return listOne.toString();
        }
    }Code Formatted by ToGoTutor

  5. informatimago.com said

    {sourcecode lang= “lisp”}
    cl-user> (defun equa2 (a b c)
    (let ((delta (- (* b b) (* 4 a c))))
    (/ (+ (- b) (sqrt delta)) 2 a)))

    equa2
    cl-user> (let ((a ‘(1 4 9 2 7 3))
    (b ‘(9 7 4 1)))
    (let ((s (- (reduce ‘+ a) (reduce ‘+ b)))
    (p (/ (reduce ‘* a) (reduce ‘* b))))
    (let* ((y (equa2 1 (- s) p))
    (x (- s y)))
    (list x y))))
    (2 3)
    cl-user>
    {/sourcecode}

  6. informatimago.com said

    “Any candidate that came up with the suggested solution would leave me in awe of his cleverness, but probably wouldn’t be invited back for a second interview.”

    Any enterprise having such an interview question would leave me in awe of their cleverness, but probably wouldn’t be invited back for a second interview either.

  7. Shankar said

    In Python

    a=[1,4,9,2,7,3]

    b=[9,7,4,1]

    set(b) ^ set(a)

    Out[29]: {2, 3}

  8. Mike said

    Python version. I believe it works in O(n) time and O(n) space.

    import collections
    
    def delta(a, b):
        ctr = collections.Counter(a)
        ctr.subtract(b)
    
        return [k for k,v in ctr.items() if v]
    
    
  9. informatimago.com said

    It was already asked on https://programmingpraxis.com/2014/02/18/ (2nd question).

  10. Kevin Melillo said

    Python:

    a = [1,2,3,4,5]
    b = [1,2,3,4,5,6,7]

    for index in b:
    if index not in a:
    print(index)

  11. Utpal Singh said

    In C Programming Language:

    #include
    int main(void)
    {
    int a,b,i,j,flag=0;
    printf(“Enter the no. of terms you want in first set:”);
    scanf(“%d”,&a);
    int seta[a];
    printf(“Enter the no. of terms you want in second set:”);
    scanf(“%d”,&b);
    int setb[b];

    printf(“Enter the nos. for set 1:\n”);

    for (i=0 ; i<a ; i++)
    {
    scanf("%d",&seta[i]);
    }

    printf("Enter the nos. for set 2:\n");

    for (j=0 ; j<b ; j++)
    {
    scanf("%d",&setb[j]);
    }
    printf("The extra nos. are:\n");
    for (i=0 ; i<a ; i++)
    {
    for (j=0 ; j<b ; j++)
    {
    if (seta[i]==setb[j])
    {
    break;
    }
    else
    {
    flag=flag+1;
    }

    if (flag==b)
    printf("%d\n",seta[i]);

    }
    flag=0;
    }
    return 0;
    }

  12. r. clayton said

    In Racket (Scheme).

  13. Globules said

    Haskell versions chosen for their conciseness, not efficiency. They use
    the \\ function from the standard Data.List module. The only constraint
    on the types of elements is that they can be tested for equality.

    λ> let (x, y) = ([1, 4, 9, 2, 7, 3], [9, 7, 4, 1]) in x \\ y
    [2,3]
    λ> 
    

    If we want to allow duplicates:

    λ> let (x, y) = ([1, 4, 9, 9, 2, 7, 3], [4, 9, 7, 4, 1]) in nub x \\ nub y
    [2,3]
    λ> 
    
  14. Sree said

    Simple C# solution:

    void Main()
    {
    var a = new int[] {1, 4, 9, 2, 7, 3};
    var b = new int[] { 9, 7, 4, 1};

    var result = a.Concat(b).Except(a.Intersect(b));

    Console.WriteLine(result);
    }

    //result: 2,3

  15. Richard A. O'Keefe said

    Smalltalk: if the two collections are xs and ys, use (xs asBag difference: ys asBag).
    Uses hashing, so average cost is proportional to xs size + ys size.

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s

%d bloggers like this: