Find Two Added Integers
December 16, 2014
I saw this question at a popular interview-question site and got mad at the suggested answer:
You are given two lists containing identical sets of integers except that the first list contains two additional integers not present in the second set. For instance, with a = {1 4 9 2 7 3} and b = {9 7 4 1}, the two additional integers are 2 and 3. Write a program to find the two additional integers.
Your task is to write the requested program. 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 
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)
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";;
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..
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
{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}
“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.
In Python
a=[1,4,9,2,7,3]
b=[9,7,4,1]
set(b) ^ set(a)
Out[29]: {2, 3}
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]It was already asked on https://programmingpraxis.com/2014/02/18/ (2nd question).
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)
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;
}
In Racket (Scheme).
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.
If we want to allow duplicates:
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
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.