Missing Items

November 22, 2016

We have today a simple exercise; we’ve seen variants of it previously.

Given two lists, find all the items in the first list that are not present in the second list. For instance, if (5 15 2 20 30 40 8 1) is the first list and (2 20 15 30 1 40 0 8) is the second list, the item 5 is present in the first list but not in the second list.

Your task is to write a program to find missing items. 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

19 Responses to “Missing Items”

  1. Simon W said

    My attempt at rewriting your sort and search in python… not sure how great it is.

    def missing2(list1, list2):
      list1 = (sorted(list1))
      list2 = (sorted(list2))
      missing = []
      y=0
      for x in list1:
        # take item from list2
        # if < x get another one
        # if = x we have a match (discard
        # if > x this number is missing from list2
        print ("x " + str(x))
        print("y was " + str(y))
        while (y < x):
          y = list2.pop(0)
            # could still exist
        if y > x:
          # x is missing
          missing.append(x)
        else:
          #match
          print ("matched x " + str(x))
        return(missing)
    
  2. Paul said

    @Simon W. Here some remarks that may improve your code. It is pretty good already. I see one difficulty: on line 14 you pop list2, but it is important to check if list2 is not empty. So line 13 should read: while list2 and y < x:. A small point is that you seem to like brackets. In lines 2, 3, 13, and 22 you can remove some. I hope this helps.

  3. Paul said

    Method 2 and 3 in Python.

    def missing3(a, b):
        setb = set(b)
        return [ai for ai in a if ai not in setb]
    
    def missing2(list1, list2):
        list1 = sorted(list1)
        list2 = sorted(list2)
        missing = []
        while list1 and list2:
            if list1[0] <= list2[0]:
                x = list1.pop(0)
                if x < list2[0]:
                    missing.append(x)
            else:
                list2.pop(0)
        return missing + list1
    
  4. matthew said

    @Paul: One advantage of Simon’s approach (with a check for an empty list2 added) is that it avoids checking both lists each time around the inner loop, so it will be somewhat more efficient (assuming the compiler doesn’t do anything very clever). Here’s one possibility:

    def missing3(list1, list2):
        list1 = sorted(list1)
        if len(list2) == 0: return list1
        list2 = sorted(list2)
        missing = []
        while list1:
            x = list1[0]
            while list2[0] < x:
                list2.pop(0)
                if not list2: return missing + list1
            if x < list2[0]: missing.append(x)
            list1.pop(0)
        return missing
    
  5. matthew said

    @Simon: I’ve just noticed that the @praxis missing2 solution doesn’t check for end of second list either, so you are in good company.

  6. Paul said

    @matthew, @Simon W: Simon’s code with the empty check added, does not always work correctly (give the same results as my missing3). In my version I can cache list1[0] and list2[0], of course. Btw, it is faster to test the last element and pop from the high side and reverse the resulting missing list.

  7. matthew said

    @Paul: Is my version up above correct? Can’t find any difference with your function. I’d be inclined to use indexes for something like this if performance really was an issue.

  8. Simon W said

    @Paul: could you please clarify why it doesn’t always work correctly with the empty check added? Many thanks

  9. Paul said

    @Simon W: on ideone you find some code that tests your function. You can see there examples, that do not work. I see two problems. The first is probably some type of typo: your return statement is shifted two spaces to the right. After repairing that I see that your method does not work if the missing value has the highest value. So you should check when list2 is empty, if there are entries left in list1.

  10. Paul said

    @matthew: your version is correct.

  11. Simon W said

    Thanks @Paul – much appreciated. I’ve decided to tackle a few of these problems a week to “sharpen my saw” and the input from yourself and @matthew is very helpful and appreciated

  12. Paul said

    @Simon W: You are wellcome. One more advice: indent with 4 spaces; it makes the code easier to read.

  13. Must my answers be in a specifc language?

  14. programmingpraxis said

    You may use any language you like.

  15. Globules said

    A Haskell version.

    import Data.List.Ordered (minus, nubSort)
    
    omit :: Ord a => [a] -> [a] -> [a]
    omit xs ys = nubSort xs `minus` nubSort ys
    
    main :: IO ()
    main = do
      print $ [5, 15, 2, 20, 30, 40, 8, 1] `omit` [2, 20, 15, 30, 1, 40, 0, 8]
      -- Duplicates are handled, too.
      print $ [2, 1, 1, 2] `omit` [1, 3, 5, 3, 1]
    
    $ ./missing 
    [5]
    [2]
    
  16. V said

    Isn’t this equivalent to the Set Difference operation?

    Solution in Ruby using built-in stuff.

    
    [5, 15, 2, 20, 30, 40, 8, 1].uniq  - [2, 20, 15, 30, 1, 40, 0, 8].uniq 
    => [5]
    
    [2, 1, 1, 2]. uniq - [1, 3, 5, 3, 1].uniq
    => [2]
      
    
  17. Paul said

    @V: It almost is. You have to list all the elements in a, which are not in b. If a=[1,1,2] and b=[2], the correct answer is [1,1] and a set difference gives [1].

  18. V said

    Ahh I see. In that case just need to remove the uniq method.

      
    [5, 15, 2, 20, 30, 40, 8, 1] - [2, 20, 15, 30, 1, 40, 0, 8]
    => [5]
    
    [2, 1, 1, 2] - [1, 3, 5, 3, 1]
    => [2, 2]
    
    [1,1,2] - [2]
    => [1, 1]
      
    
  19. vyusfire said
    function missingItems(xs, ys) {
      return xs.reduce(function(acc, elt) {
        ys.indexOf(elt) < 0 || acc.push(elt)
        return acc;
      }, []);
    }
    
    console.log(missingItems([5, 3, 12, 9, 8], [3, 9, 8]))
    

    Hi, I’d like to post my quick-hand solution,
    i haven’t made full test, this code may be buggy,
    hope for your comments & advices.

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: