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.
Programming Praxis 
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)@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.
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@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@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.
@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.
@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.
@Paul: could you please clarify why it doesn’t always work correctly with the empty check added? Many thanks
@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.
@matthew: your version is correct.
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
@Simon W: You are wellcome. One more advice: indent with 4 spaces; it makes the code easier to read.
Must my answers be in a specifc language?
You may use any language you like.
A Haskell version.
Isn’t this equivalent to the Set Difference operation?
Solution in Ruby using built-in stuff.
@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].
Ahh I see. In that case just need to remove the uniq method.
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.
List list_1 = new List(5,15,2,20,30,40,8,1);
List list_2 = new List(2,20,15,30,1,40,0,8);
List answer = new List();
bool found = false;
foreach (int x in list_1)
{
foreach (int y in list_2)
{
if (x == y)
{
found = true;
break;
}
}
if (found)
{
answer.add(x);
found = false;
}
}