Find The Minimum Difference

October 15, 2013

We have today another exercise from our limitless supply of interview questions:

You are given two arrays of integers, where the integers do not repeat, the two arrays have no common integers, and both arrays are sorted in ascending order.

Let x be any integer in the first array and y be any integer in the second array. Find min(abs(xy)); i.e., find the smallest difference between any integers in the two arrays.

Your task is to write a program to find the smallest difference. 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.

About these ads

Pages: 1 2

14 Responses to “Find The Minimum Difference”

  1. mattharrison86 said

    def find_smallest array1, array2
    	min = Float::INFINITY
    	array1.each_with_index { |elem1,i|
    		array2.each_with_index{ |elem2, j|
    			diff = (elem1 - elem2).abs
    			min = diff unless diff > min
    		}
    	}
    	min
    end
    
    puts find_smallest array1, array2 # 57
    
  2. Paul said

    In Python:

    def min_abs(arrx, arry):
        itx, ity = iter(arrx), iter(arry)
        x, y = next(itx, None), next(ity, None)
        diff = float("inf")
        while not None in (x, y):
            diff = min(diff, abs(x - y))    
            if x < y:
                x = next(itx, None)
            else:
                y = next(ity, None)
        return diff
    
  3. Graham said

    While this won’t change the average complexity, can’t we shortcircuit if we find an absolute difference of zero?

  4. Paul said

    We can shortcuit if we find a difference of one. Zero is not possible, as the arrays do not have common numbers.

  5. Graham said

    Thanks @Paul, I didn’t read carefully enough!

  6. Graham said

    I hate to be a pain, but it’s not clear to me that the arrays have to be nonempty.
    Here’s a Haskell version that handles empty lists as well:

    import Data.Maybe (fromJust)
    
    mad :: [Integer] -> [Integer] -> Maybe Integer
    mad [] _ = Nothing
    mad _ [] = Nothing
    mad xs ys = Just $ m xs ys z
        where
            z = abs . head $ zipWith (-) xs ys
            m [] _ d = d
            m _ [] d = d
            m (a:as) (b:bs) d | d' == 1   = 1
                              | a < b     = m as (b:bs) d'
                              | otherwise = m (a:as) bs d'
                              where
                                  d' = min d (abs $ a - b)
    
    
    main :: IO ()
    main = mapM_ (print . uncurry mad) [([], [1..]),
                                        ([1..], []),
                                        ([19, 22, 24], [37, 28, 49, 88])]
    

    This could have been cleaner if infinity were included in the integers in Haskell;
    it’s true that 1/0 returns Infinity, but this isn’t an Integer.

  7. Graham said

    Sorry for spamming, but here’s a slightly cleaner version of my mad function:

    mad :: [Integer] -> [Integer] -> Maybe Integer
    mad [] _ = Nothing
    mad _ [] = Nothing
    mad (x:xs) (y:ys) = Just $ m xs ys (abs $ x - y)
        where
            m [] _ d = d
            m _ [] d = d
            m (a:as) (b:bs) d | d' == 1   = 1
                              | a < b     = m as (b:bs) d'
                              | otherwise = m (a:as) bs d'
                              where
                                  d' = min d (abs $ a - b)
    
  8. Mike said

    Python version. Like Paul’s, but i put the iterators in a separate generator that returns potential minimum pairs from the lists. Then maxdiff() is straight forward.

    def pairs(xs, ys):
    itx, ity = iter(xs), iter(ys)
    x, y = next(itx), next(ity)
    while True:
    yield x, y
    x, y = (next(itx),y) if x < y else (x, next(ity))

    def mindiff(xs, ys):
    return min(abs(x – y) for x,y in pairs(xs, ys))

  9. Mike said

    Sorry, forgot the formating.

    Python version. Like Paul’s, but i put the iterators in a separate generator that returns potential minimum pairs from the lists. Then maxdiff() is straight forward.

     
    
    def pairs(xs, ys):
        itx, ity = iter(xs), iter(ys)
        x, y = next(itx), next(ity)
        while True:
            yield x, y
            x, y = (next(itx),y) if x < y else (x, next(ity))
     
    def mindiff(xs, ys):
        return min(abs(x – y) for x,y in pairs(xs, ys))
    
    
  10. Eric said

    Here is my solution in groovy. I have a feeling there is a more efficient way to do this especially with the the def min at the start.

    static int minDiff(arr1, arr2){
    def min = Math.abs(arr1[0]-arr2[0])
    for(i in arr1){
    for(j in arr2){
    def diff = Math.abs(i-j)
    if(min>diff){
    min=diff
    }
    }
    }
    return min
    }

  11. Most of this stuff is well over my head, but I happen to be just starting to learn APL and so could’t resist. Using the example input from the first solution:

    f←{⌊/⌊/|⍺∘.-⍵}
    x←19 22 24
    y←37 38 49 88
    x f y
    13

    I don’t kow if there’s a clever mathy way to make it more efficient, but at least it has the virtue of simplicity. I guess this will run in O(n^2)… :-)

    As for empty vectors, I am not sure what the subtraction operator should yield without any arguments, but I get infinity when I feed it to my function:

    ⍬ f ⍬

  12. The Man From SQL said

    Here’s my version in C#. As a small optimization for large arrays, I’ve added a short-circuit that exits if the difference between x and y-currrent is positive and greater than the abs difference between x and y-previous (since the arrays are guaranteed to be sorted, this means we won’t find a smaller difference for x).

            public static int Find(int[] FirstArray, int[] SecondArray)
            {
                int minimum = Int32.MaxValue;
                int lastDiff;
    
                for (int i = 0; i < FirstArray.Length; i++)
                {
                    lastDiff = Int32.MaxValue;
    
                    for (int j = 0; j < SecondArray.Length; j++)
                    {   
                        int unAbsResult = SecondArray[j] - FirstArray[i];
                        int result = Math.Abs(unAbsResult);
                        if (result < minimum)
                        {
                            minimum = result;
                        }
                        if (result > lastDiff && unAbsResult > 0)
                        {
                            break;
                        }
                        
                        lastDiff = result;
                    }
                }
                return minimum;
            }
    
  13. Dakshin said

    Here is my version in C++:

    #include
    #include
    #include
    #include
    #include
    using namespace std;
    #define N 10

    struct small {
    int diff;
    int x;
    int i;
    int y;
    int j;
    } ;

    int get_num();
    int ascending(int *, int);

    int main(){

    int j,i=0;
    int n=N;
    int x[N];
    int y[N];
    int status;
    struct small sm;
    sm.x=sm.y=sm.i=sm.j=0;
    sm.diff=1000;

    while(i<n){
    x[i++] = get_num();
    }
    cout<<"X:"<<endl;
    for(i=0;i<n;i++)
    cout<<' '<<x[i];
    cout<<' '<<endl;

    i=0;
    while(i<n){
    int num = get_num();
    status = false;

    for(j=0;j<n&&num==x[j];j++)
    status =true;

    if(status == false)
    y[i++]
    =num;

    }

    cout<<"Y:"<<endl;
    for(i=0;i<n;i++)
    cout<<' '<<y[i];
    cout<<endl;

    cout<<"After ascending:"<<endl;
    ascending(x,n);
    cout<<"X:"<<endl;
    for(i=0;i<n;i++)
    cout<<' '<<x[i];
    cout<<endl;

    ascending(y,n);
    cout<<"Y:"<<endl;
    for(i=0;i<n;i++)
    cout<<' '<<y[i];
    cout<<endl;

    for(i=0;i<n;i++)
    for(j=0;j<n;j++) {

    if(abs(x[i]-y[j]) <sm.diff)
    {
    sm.diff=abs(x[i]-y[j]);
    sm.i=i;
    sm.j=j;
    sm.x=x[i];
    sm.y=y[j];
    }

    }

    cout<<"diff:"<<sm.diff<<endl;
    cout<<"nums:"<<sm.x<<' '<<sm.y<<endl;

    return 0;
    }

    int get_num(){

    num:

    int n = rand()%100;

    if(n!=0)
    return n;
    else
    goto num;
    }

    int ascending(int *num, int n){

    int temp=0;
    int j,i=0;

    for(i=0;i<n;i++)
    for(j=0;jnum[j+1]){
    temp=num[j];
    num[j]=num[j+1];
    num[j+1]=temp;
    }

    }

    return true;
    }

  14. jozefg said

    A shorter haskell solution

    import Control.Monad
    minDiff (x:xs) (y:ys) | x – y < 0 = choose (y-x) $ minDiff xs (y:ys)
    | otherwise = choose (x-y) $ minDiff (x:xs) ys
    where choose x m = fmap (min x) m `mplus` Just x
    minDiff _ _ = Nothing

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 576 other followers

%d bloggers like this: