Common Elements Of Three Arrays

March 17, 2015

We have another interview question today. There are several different ways to approach this task, so it makes for an interesting exercise:

Given three arrays of integers in non-decreasing order, find all integers common to all three arrays. For instance, given arrays [1,5,10,20,40,80], [6,7,10,20,80,100] and [3,4,15,20,30,70,80,120] the two common integers are 20 and 80. If an integer appears multiple times in each of the arrays, it should appear multiple times in the output, so with input arrays [1,5,5,5], [3,4,5,5,10] and [5,5,10,20] the correct output is [5,5].

Your task is to write a program to solve the interview question. 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.

Posted by programmingpraxis

Filed in Exercises

12 Comments »

12 Responses to “Common Elements Of Three Arrays”

klettier said

March 17, 2015 at 11:31 AM

My solution is to find shortest two arrays to process biggest one only one time.
This allows for searching for only common integers from the two shortest arrays in bigest one.

void Main()
{
	var ar1 = new[]{1,5,10,20,40,80,999,999};
	var ar2 = new[]{6,7,10,20,80,100,5,999,999};
	var ar3 = new[]{3,4,15,20,30,70,80,120,999,999};
	
	var bigestAndShortestArrays = FindBigestAndShortestArrays(new int[][]{ar1,ar2,ar3});
	
	List<int> numberToFindInBigestArray = new List<int>();
	
	for(int a = 0; a < bigestAndShortestArrays.Item2[0].Length; a++)
		for(int aa = 0; aa < bigestAndShortestArrays.Item2[1].Length; aa++)
			if(bigestAndShortestArrays.Item2[0][a] == bigestAndShortestArrays.Item2[1][aa])
				numberToFindInBigestArray.Add(bigestAndShortestArrays.Item2[0][a]);
	
	numberToFindInBigestArray = numberToFindInBigestArray.Distinct().ToList();
	
	List<int> numbersInAllArrays = new List<int>();
	
	for(int a = 0; a < bigestAndShortestArrays.Item1.Length; a++)
		for(int aa = 0; aa < numberToFindInBigestArray.Count; aa++)
			if(bigestAndShortestArrays.Item1[a] == numberToFindInBigestArray[aa])
				numbersInAllArrays.Add(bigestAndShortestArrays.Item1[a]);
	
	numbersInAllArrays.Dump();
}

Tuple<int[], int[][]> FindBigestAndShortestArrays(int[][] arrs)
{
	if(arrs.Length != 3)
	throw new InvalidOperationException("tabs must be an array of 3 arrays");

	var shortests = new int[2][];
	int[] biggest = null;
	
	if(arrs[0].Length <= arrs[1].Length)
	{
		if(arrs[1].Length <= arrs[2].Length)
		{
			shortests[0] = arrs[0];
			
			if(arrs[1].Length <= arrs[2].Length)
			{
				shortests[1] = arrs[1];
				biggest = arrs[2];
			}
			else
			{
				shortests[1] = arrs[2];
				biggest = arrs[1];
			}
		}
		else
		{
			shortests[0] = arrs[1];
			
			if(arrs[0].Length <= arrs[2].Length)
			{
				shortests[1] = arrs[0];
				biggest = arrs[2];
			}
			else
			{
				shortests[1] = arrs[2];
				biggest = arrs[0];
			}
		}
	}
	
	return Tuple.Create(biggest,shortests);
}

Output:

20
80
999
999

Francesco said

March 17, 2015 at 12:06 PM

Haskell:

f a b c                         | any null [a, b, c] = []
f la@(a:as) lb@(b:bs) lc@(c:cs) | all (==a) [b, c]   = a : f as bs cs
                                | otherwise          = f (d la) (d lb) (d lc)
    where d cs = if head cs == maximum [a,b,c] then cs else tail cs

There is probably a more concise solution using lists comprehension, but alas it eludes me

Scott said

March 17, 2015 at 1:47 PM

public class ThreeArrays {
	
	public static void main(String[] args){
		System.out.println(commonNumbers(new Integer[]{1,5,10,20,40,80}, 
				new Integer[]{6,7,10,20,80,100}, new Integer[]{3,4,15,20,30,70,80,120}));

		System.out.println(commonNumbers(new Integer[]{1,5,5,5}, 
				new Integer[]{3,4,5,5,10}, new Integer[]{5,5,10,20}));
	}

	public static List<Integer> commonNumbers(Integer[]... arrays){
		
		if(arrays.length < 2)
			return null;
		
		List<Integer> common = new ArrayList<Integer>();
		int[] matches = new int[arrays[0].length];

		for(int i = 1; i < arrays.length; i++){
			int x = 0, y = 0;

			while(x < arrays[0].length && y < arrays[i].length){
				if(arrays[0][x] < arrays[i][y]){
					x++;
				}
				else if(arrays[0][x] > arrays[i][y]){
					y++;
				}
				else{
					matches[x++] += 1;
					y++;
				}
			}
		}

		for(int i = 0; i < matches.length; i++){
			if(matches[i] == arrays.length-1){
				common.add(arrays[0][i]);
			}
		}
		return common;
	}
}

mcmillhj said
March 17, 2015 at 5:22 PM
Similar solution in SML:

fun intersect (xs, ys) = let
fun loop(out, _, []) = List.rev out
| loop(out, [], _) = List.rev out
| loop(out,left as x::xs, right as y::ys) =
if x < y then loop(out, xs, right)
else if y < x then loop(out, left, ys)
else loop(x::out, xs, ys)
in
loop([], xs, ys)
end

fun nintersect [] = []
| nintersect (xs::xss) = List.foldl intersect xs xss;
[/sourcecode]

mcmillhj said

March 17, 2015 at 5:23 PM

Sorry, issue with formatting:

fun intersect (xs, ys) = let
    fun loop(out, _, [])      = List.rev out
      | loop(out, [], _)      = List.rev out
      | loop(out,left as x::xs, right as y::ys) =
           if x < y then loop(out, xs, right)
           else if y < x then loop(out, left, ys)
           else loop(x::out, xs, ys)
in
    loop([], xs, ys)
end

fun nintersect []  = []
  | nintersect (xs::xss) = List.foldl intersect xs xss;

matthew said

March 17, 2015 at 7:15 PM

This one is like Scott’s – for each element in the first array, discarding lower elements in the other arrays, moving on to the next element if no match is found. A nice flourish is to use a sentinel element at the end of each array, when a match is found and it’s the sentinel element we break the loop. No other bounds checking is needed:

#include <stdio.h>
#include <limits.h>
int a[] = { 0,10,20,30,40,40,50,60,70,80,100,MAXINT };
int b[] = { 5,20,20,40,40,80,MAXINT};
int c[] = { 10,20,30,40,40,45,50,60,80,MAXINT};
int main()
{
  int ai = 0, bi = 0, ci = 0;
  for ( ; ; ai++) {
    while (b[bi] < a[ai]) bi++;
    if (b[bi] > a[ai]) continue;
    while (c[ci] < a[ai]) ci++;
    if (c[ci] > a[ai]) continue;
    if (a[ai] == MAXINT) break;
    printf("%d ", a[ai]);
    bi++; ci++;
  }
  printf("\n");
}

Paul said

March 17, 2015 at 8:10 PM

In Python. This works for an arbitrary number of arrays.

def common_n(*arrays):
    """ make a sorted array with (value, iter) tuples
        as long as the first value is lower than the last:
            increase the first value and keep the array sorted
    """
    def common(*arrays):
        its = [iter(a) for a in arrays]
        while 1:
            vals = sorted([(next(it), it) for it in its])
            while vals[0][0] < vals[-1][0]:
                v, it = vals.pop(0)
                while v < vals[-1][0]:
                    v = next(it)
                vals.append((v, it)) # now v >= last value in array, so we can append
            yield vals[0][0]
    return list(common(*arrays))

Mike said

March 17, 2015 at 9:54 PM

The Python standard library collections.Counter acts like a multi-set, making this problem a one-liner.

from collections import Counter
from functools import reduce
from operator import and_

def find_common(*args):
	return sorted(reduce(and_, map(Counter, args)).elements())

Keval said
March 18, 2015 at 3:00 AM
for(p=0;p<a.length;p++)
{
for(q=0;q<b.length;q++)
{
if(b[q]==a[p])
{
// System.out.println("matching values found in array a and b:::"+b[q]);
for(r=0;r<c.length;r++)
{
if(c[r]==b[q])
{
common[common_ite]=c[r];
System.out.println("common integer found:::"+common[common_ite]);
common_ite++;
break;
}
//ends for loop r….for c array
}
break;
//end if of b array…
}

//end for loop of q …for b array…
}
//ends main foor loop..of array a…
}
Keval said
March 18, 2015 at 3:01 AM
It can be made more efficient by using common array with length of shortest array…use of break is not encouraged…but its fast and in any interview..it maybe helpful in time constraint..

matthew said

March 18, 2015 at 10:15 PM

OK, here’s another one, same trick with sentinels. Iterate down all 3 lists, if the current element in list i is less than the current element in list i+1 (mod 3), skip it. If no element is skipped, they must all be the same. Possibly does more comparisons than my other solution, but at least uses INT_MAX properly:

#include <stdio.h>
#include <limits.h>
int a[] = { 0,10,20,30,40,40,50,60,70,80,100,INT_MAX };
int b[] = { 5,20,20,40,40,80,INT_MAX };
int c[] = { 10,20,30,40,40,45,50,60,80,INT_MAX };
int main()
{
  int ai = 0, bi = 0, ci = 0;
  while (true) {
    if (a[ai] < b[bi]) ai++;
    else if (b[bi] < c[ci]) bi++;
    else if (c[ci] < a[ai]) ci++;
    else if (a[ai] == INT_MAX) break;
    else {
      printf("%d ", a[ai]);
      ai++; bi++; ci++;
    }
  }
  printf("\n");
}

Rutger said

March 19, 2015 at 1:26 PM

Wrote my own Bag implementation in Python, for the heck of it. Although obviously I should have used collections.Counter :)

class Bag():
    def __init__(self, l=None):
        self.data = {}
        if l:
            for e in l:
                self.insert(e)

    def __str__(self):
        result = '_'*4+'bag'+ '_'*4 + '\n'
        for e in sorted(self.data.keys()):
            result += ("[%s%sx] %s\n"%(" "*(3-len(str(self.data[e]))), self.data[e], e))
        return result
        
    def insert(self, e):
        try:
            self.data[e] += 1
        except KeyError:
            self.data[e] = 1

    def remove(self, e):
        try:
            self.data[e] -= 1
        except KeyError:
            raise Exception("Bag.remove(): %s not found."%e)

    def get(self, e):
        try:
            return (e, self.data[e])
        except KeyError:
            return ()

    def clear(self):
        self.__init__()

    def union(self, bag):
        result = Bag()
        for e in self.data:
            result.data[e] = self.data[e]
            try:
                result.data[e] += bag.get(e)[1]
            except:
                result.data[e] = bag.get(e)[1]
        return result

    def intersection(self, bag):
        result = Bag()
        for e1 in self.data:
            try:
                n = bag.get(e1)[1]
                result.data[e1] = min(self.data[e1], n)
            except:
                pass
        return result

    @staticmethod
    def test():
        b1 = Bag()
        for x in range(7):
            b1.insert(3)
        b1.insert(849401284)
        print b1
        print b1.get(3)
        b1.remove(3)
        try:
            b1.remove(4)
        except Exception, e:
            print e
        b1.insert("asdf'")
        print "-"*30, "Result", "-"*30
        print b1
        print "-"*30, "Union self", "-"*30
        b2 = b1.union(b1)
        print b2
        print "-"*30, "intersection self with union", "-"*30
        b3 = b1.intersection(b2)
        print b3


# Bag.test()
b1 = Bag([1,5,10,20,40,80])
b2 = Bag([6,7,10,20,80,100])
b3 = Bag([3,4,15,20,30,70,80,120])
print b1.intersection(b2).intersection(b3)
b1 = Bag([1,5,5,5])
b2 = Bag([3,4,5,5,10])
b3 = Bag([5,5,10,20])
print b1.intersection(b2).intersection(b3)

Programming Praxis