Computer Science Canada

Interview question: find common element in 3 arrays
Author:  cool dude [ Wed Jul 11, 2012 5:17 pm ]
Post subject:  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?
Author:  Zren [ Wed Jul 11, 2012 6:04 pm ]
Post subject:  RE:Interview question: find common element in 3 arrays
Your current idea is flawed.

Eg:
a1 = {}
a2 = {1}
a3 = {1, 1}
Author:  cool dude [ Wed Jul 11, 2012 6:36 pm ]
Post subject:  Re: RE:Interview question: find common element in 3 arrays
Zren @ Wed Jul 11, 2012 6:04 pm wrote:
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}
Author:  Dreadnought [ Wed Jul 11, 2012 7:22 pm ]
Post subject:  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.
Author:  chrisbrown [ Wed Jul 11, 2012 7:25 pm ]
Post subject:  Re: Interview question: find common element in 3 arrays
I think this works, generalized to N arrays:
code:
Keep N indexes, one for each array, all initialized to the beginning of their respective arrays.
Keep a counter commonCount initilaized to 0

Iterate over the first array only. For each element e {
        initialize a counter matchCount to 1
        for each other array {
                increment the respective index until the indexed element is not less than e
                if the value is equal to e, incremement matchCount
        }
        if matchCount is equal to N, increment commonCount
}


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.
Author:  cool dude [ Wed Jul 11, 2012 11:41 pm ]
Post subject:  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);
        }
}
Author:  wtd [ Thu Jul 12, 2012 12:36 am ]
Post subject:  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;;
Author:  Raknarg [ Thu Jul 12, 2012 10:44 am ]
Post subject:  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?
Author:  wtd [ Thu Jul 12, 2012 11:14 am ]
Post subject:  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) <- index;
                                i := !i + 1
                        done
        in
                (
                        while not (all_starts_equal ()) do
                                starting_indices.(0) <- starting_indices.(0) + 1;
                                remove_all_less ()
                        done;
                        arr_arr.(0).(starting_indices.(0))
                )
               
let data =
        [|
                [| 2; 4; 7; 9 |];
                [| 4; 5; 6; 11 |];
                [| 1; 3; 4; 7 |]
        |];;
       
Printf.printf "The common element is: %d\n" (solution data)
Author:  Amarylis [ Thu Jul 12, 2012 12:51 pm ]
Post subject:  RE:Interview question: find common element in 3 arrays
code:

e = 0
for i in li:
    if (i in l2) & (i in l3):
        e += 1

print (e)


Go go python power!
Author:  Tony [ Thu Jul 12, 2012 3:43 pm ]
Post subject:  Re: RE:Interview question: find common element in 3 arrays
Amarylis @ Thu Jul 12, 2012 12:51 pm wrote:
Go go python power!

Great. What's the runtime complexity of looking up an element by value in array?
Author:  wtd [ Thu Jul 12, 2012 7:30 pm ]
Post subject:  RE:Interview question: find common element in 3 arrays
If you're going to use Python, at least make use of sets.

code:
data = [[2, 4, 7, 9 ], [4, 5, 6, 11], [1, 3, 4, 7]]

print reduce(lambda x, y: set(x) & set(y), data)


Edit: I'm too tired to do the math, but shouldn't this scale reasonably well? The intersection gets simpler with each iteration of reduce, and we're not looping over each array more than once.
Author:  Amarylis [ Fri Jul 13, 2012 12:14 am ]
Post subject:  Re: RE:Interview question: find common element in 3 arrays
Tony @ Thu Jul 12, 2012 3:43 pm wrote:
Amarylis @ Thu Jul 12, 2012 12:51 pm wrote:
Go go python power!

Great. What's the runtime complexity of looking up an element by value in array?


O(N), which in three arrays would be O(N^3), I know, I was just trying to give the simple answer Razz Sorry.


(I might be completely wrong on my Big-O notation)
Author:  Brightguy [ Fri Jul 13, 2012 10:53 am ]
Post subject:  Re: RE:Interview question: find common element in 3 arrays
Raknarg @ Thu Jul 12, 2012 10:44 am wrote:
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?

Yes indeed! Nice thought.

Amarylis @ Fri Jul 13, 2012 12:14 am wrote:
O(N), which in three arrays would be O(N^3), I know, I was just trying to give the simple answer Razz Sorry.

As mentioned, since the third loop isn't nested it would only be O(n^2).

wtd @ Thu Jul 12, 2012 7:30 pm wrote:
Edit: I'm too tired to do the math, but shouldn't this scale reasonably well? The intersection gets simpler with each iteration of reduce, and we're not looping over each array more than once.

Python uses hash tables to implement sets, so in the worst case (maximum number of collisions) intersection will be O(n^2). It should perform better in practice, though.
Author:  Raknarg [ Fri Jul 13, 2012 4:56 pm ]
Post subject:  RE:Interview question: find common element in 3 arrays
@Bightguy I really don't know how the math works at all, but I'm assuming it would change the complexity from O(n^3) to O(n)*3.

I really should look this stuff up...
Author:  Brightguy [ Fri Jul 13, 2012 5:49 pm ]
Post subject:  Re: RE:Interview question: find common element in 3 arrays
Raknarg @ Fri Jul 13, 2012 4:56 pm wrote:
@Bightguy I really don't know how the math works at all, but I'm assuming it would change the complexity from O(n^3) to O(n)*3.

Sure, it would be O(3n). But constant factors are irrelevant to Big O, so it's just O(n).
Author:  wtd [ Mon Jul 16, 2012 1:24 am ]
Post subject:  RE:Interview question: find common element in 3 arrays
The algorithm as seen in my last submission, but implemented without mutable state.

code:
open Printf

open List
module L = List

let rec trim f lst =
        match lst with
                  [] -> []
                | (x :: _) when not (f x) -> lst
                | (_ :: xs) -> trim f xs
       
let rec all_firsts_equal lst = 
        match lst with
                  [] -> true
                | (first :: rest) ->
                        let rec helper v lst =
                                match lst with
                                          [] -> true
                                        | (x :: xs) when (L.hd x) <> v -> false
                                        | (x :: xs) -> helper v xs
                        in
                                helper (L.hd first) rest
                               
let rec solve data =
        match data with
                  [] -> None
                | (x :: xs) when x = [] -> None
                | (x :: xs) when all_firsts_equal data -> Some (L.hd x)
                | (x :: xs) ->
                        let v = L.hd x in
                        let t = L.map (fun y -> trim (fun x -> x < v) y) xs
                        in
                                if all_firsts_equal (x :: t) then
                                        Some v
                                else
                                        solve (L.tl x :: t);;
                               
match solve [[1;2;3]; [2;3;4;5]; [0;1;3;5]] with
          None -> print_endline "No solution!"
        | Some x -> Printf.printf "Found it! %d\n" x


If we actually look at the required calls to solve.

code:
solve [[1;2;3]; [2;3;4;5]; [0;1;3;5]]
solve [[2;3]; [2;3;4;5]; [1;3;5]]
solve [[3]; [2;3;4;5]; [3;5]]


If we modify the program slightly...

code:
open Printf

open List
module L = List

let rec trim f lst =
        match lst with
                  [] -> []
                | (x :: _) when not (f x) -> lst
                | (_ :: xs) -> trim f xs
       
let rec all_firsts_equal lst = 
        match lst with
                  [] -> true
                | (first :: rest) ->
                        let rec helper v lst =
                                match lst with
                                          [] -> true
                                        | (x :: xs) when (L.hd x) <> v -> false
                                        | (x :: xs) -> helper v xs
                        in
                                helper (L.hd first) rest
                               
let rec solve data =
        match data with
                  [] -> None
                | (x :: xs) when x = [] -> None
                | (x :: xs) when all_firsts_equal data -> Some (L.hd x)
                | (x :: xs) ->
                        let v = L.hd x in
                        let t = L.map (fun y -> trim (fun x -> x < v) y) xs
                        in
                                if all_firsts_equal (x :: t) then
                                        Some v
                                else
                                        let t' = L.map (fun y -> trim (fun x -> x <= v) y) xs
                                        in
                                                solve (L.tl x :: t');;
                               
match solve [[1;2;3]; [2;3;4;5]; [0;1;3;5]] with
          None -> print_endline "No solution!"
        | Some x -> Printf.printf "Found it! %d\n" x


Then it breaks down like so:

code:
solve [[1;2;3]; [2;3;4;5]; [0;1;3;5]]
solve [[2;3]; [2;3;4;5]; [3;5]]
solve [[3]; [3;4;5]; [3;5]]
Some 3


Essentially now we check to see if removing everything less than the leading number of the first list makes all first elements equal. But, if it doesn't, we remove everything equal to or less than the first element. This saves us some work the next time around.

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy