-----------------------------------

cool dude

Wed Jul 11, 2012 5:17 pm


Interview question: find common element in 3 arrays

-----------------------------------

This is an algorithm question asked at an interview. 

You have 3 arrays and for simplicity we'll say they're equal length and SORTED. 
Example:

a1 = {2, 4, 7, 9}
a2 = {4, 5, 6, 11}
a3 = {1, 3, 4, 7}

The task is to find the number of common elements between all 3 arrays. So in this example the output will be 1 since there is only one common element in all 3 arrays which is 4. 

Obviously you can solve this using 3 for loops and iterate through each array. You can even solve with 2 for loops while iterating through the first array and the inner for loop iterates through the other 2 arrays... However, this is highly inefficient as this has time complexity of O(n^3) and O(n^2) respectively. 

Does anyone know of any good algorithms for solving this problem?

My only efficient algorithm I came up with as follows:
1. Iterate through each element in the array
2. Create Hashtable
3. check if the element is already in the Hashtable
    3.1 If it is then increment the value of that element 
    3.1.1 If that value is 3 then increment our local count since we found a common element in all 3 arrays
    3.2 if the element is not in the Hashtable then add it to the Hashtable
4. print count

However, this requires the use of a Hashtable meaning we increase our data space. Is there a better or easier way of doing this?


-----------------------------------

Zren

Wed Jul 11, 2012 6:04 pm


RE:Interview question: find common element in 3 arrays

-----------------------------------

Your current idea is flawed.

Eg:
a1 = {}
a2 = {1} 
a3 = {1, 1}


-----------------------------------

cool dude

Wed Jul 11, 2012 6:36 pm


Re: RE:Interview question: find common element in 3 arrays

-----------------------------------

Your current idea is flawed.

Eg:
a1 = {}
a2 = {1} 
a3 = {1, 1}

Your example is flawed as I said all 3 arrays must be same length. Also the elements in each array are unique so you won't have a3 = {1,1}


-----------------------------------

Dreadnought

Wed Jul 11, 2012 7:22 pm


Re: Interview question: find common element in 3 arrays

-----------------------------------

My first instinct would be to keep track of 3 indices, one for each array and a total of course.
Starting with the first value in each array, do the following

Check if all 3 values are equal, if so increment the total and all indices by 1.
Otherwise, increment the index of lowest value by 1.
Repeat until you reach the end of one list (at this point you are done)

This would use a single loop and at first glance seems reasonably efficient since each iteration guarantees that you advance in one of the lists. This means you have at most 3*n iterations of your loop.


-----------------------------------

chrisbrown

Wed Jul 11, 2012 7:25 pm


Re: Interview question: find common element in 3 arrays

-----------------------------------

I think this works, generalized to N arrays:

After reaching the end of the first array, commonCount contains the number of elements common to all arrays.

Indexes increase monotonically so the running time is O(L*N) for N arrays of length L.

Edit: Ha, three minutes too late.


-----------------------------------

cool dude

Wed Jul 11, 2012 11:41 pm


Re: Interview question: find common element in 3 arrays

-----------------------------------

Wow way simpler than I thought. I guess thinking under pressure is a bit different.

Thanks a lot Dreadnought here is the code I wrote using the algorithm you explained:

[code]public class commonNumber {
	public static void main (String[] args)
	{
		int[] arr1 = {2, 4, 7, 9};
		int[] arr2 = {4, 5, 6, 11};
		int[] arr3 = {1, 3, 4, 7};
		
		int cnt1 = 0, cnt2 = 0, cnt3 = 0;
		int common = 0;
		
		while (cnt1 < arr1.length && cnt2 < arr2.length && cnt3 < arr3.length)
		{
			if (arr1[cnt1] == arr2[cnt2] && arr1[cnt1] == arr3[cnt3])
			{
				common++;
				cnt1++;
				cnt2++;
				cnt3++;
			}
			else
			{
				int min = Math.min(arr1[cnt1], arr2[cnt2]);
				min = Math.min(min, arr3[cnt3]);
				if (min == arr1[cnt1])
					cnt1 = cnt1+1;
				else if (min == arr2[cnt2])
					cnt2 = cnt2 + 1;
				else
					cnt3 = cnt3 + 1;
			}
		}
		
		System.out.println(common);
	}
}
[/code]


-----------------------------------

wtd

Thu Jul 12, 2012 12:36 am


Re: Interview question: find common element in 3 arrays

-----------------------------------

[code]let in_list x lst =
   let rec f' x lst a =
      match lst with 
           [] -> a
         | (y::ys) when a -> a
         | (y::ys) -> f' x ys (x = y)
   in
      f' x lst false
	  
let rec all f lst =
   match lst with 
        [] -> true
      | (x::xs) when not (f x) -> false
      | (x::xs) -> all f xs
	  
let rec which f lst lst_lst =
   match lst with
        [] -> None
      | (x::xs) -> 
	   if all (fun y -> f x y) lst_lst then
              Some x
           else
              which f xs lst_lst
			  
let solution lst lst_lst =
   which in_list lst lst_lst;;[/code]


-----------------------------------

Raknarg

Thu Jul 12, 2012 10:44 am


RE:Interview question: find common element in 3 arrays

-----------------------------------

I had a thought. If they're aleady sorted, could you just mergesort them together and then use a single for loop to find three arrays elements that are the same in order?


-----------------------------------

wtd

Thu Jul 12, 2012 11:14 am


Re: Interview question: find common element in 3 arrays

-----------------------------------

I implemented Tony's algorithm as per our discussion of this, which scales to any size dataset, but requires that all arrays be sorted.  Arrays are never mutated, so there's a minimal, linearly scaling memory hit.  The program also never scrubs over any array element twice.

[code]open Printf
open Array
module A = Array

let solution arr_arr =
	let rec starting_indices = A.make (A.length arr_arr) 0
	and len = A.length arr_arr
	and all_starts_equal () =
		let first = arr_arr.(0).(starting_indices.(0))
		and i = ref 1
		and break = ref false
		and result = ref true
		in
			(
				while !i < len && not !break do
					if first  arr_arr.(!i).(starting_indices.(!i)) then (
						break := true;
						result := false);
					i := !i + 1
				done;
				!result
			)
	and find_index start f arr =
		let i = ref start
		and index = ref 0
		and found = ref false
		in
			(
				while !i < A.length arr && not !found do
					if f arr.(!i) then
						(
							index := !i;
							found := true
						);
					i := !i + 1
				done;
				!index
			)
	and remove_all_less () =
		let rec first = arr_arr.(0).(starting_indices.(0))
		and i = ref 1
		and f x = x >= first
		in
			while !i < len do
				let index = find_index starting_indices.(!i) f arr_arr.(!i) in
					starting_indices.(!i)