2
\$\begingroup\$

I'm practicing for technical interviews and I'm looking for ways to improve my answers/code. Please point out the flaws you see and how I can make this better.

Task: Find pairs in an integer array whose sum is equal to 10 (bonus: do it in linear time)

Pairs.java

  //Container class that will hold the indices of the pairs found

    public class Pairs<T,K> {

        private T tval;
        private K kval;

        public Pairs(){

        }

        public Pairs(T tv, K kv){

            this.tval = tv;
            this.kval = kv;

        }

        public T getFirst() {

            return tval;

        }

        public void setFirst(T tval) {

            this.tval = tval;

        }

        public K getSecond() {

            return kval;

        }

        public void setSecond(K kval) {

            this.kval = kval;

        }

        public void clear(){

            this.tval = null;
            this.kval = null;

        }

    }

EqualPairs.java

    import java.util.ArrayList;
    import Utilities.Pairs;

    /**
     * Find pairs in an integer array whose sum is equal to 10
     * (bonus: do it in linear time)   
     * 
     */

    public class EqualPairs {

        //O(n^2). First solution I came up with. Debugging through this
        //method actually gave me the idea on how to attempt to solve this
        //problem in linear time.
        public static ArrayList<Pairs> equal(int[] array){

            int numComparisons = 0; //for big O analysis
            ArrayList<Pairs> pairsList = new ArrayList<Pairs>();
            for(int i = 0;i<array.length;i++){
                for(int j=0;j<array.length;j++){
                    if(array[i]+array[j]==10 && i!=j && i<j){
                        Pairs pair = new Pairs(i,j);
                        pairsList.add(pair);    
                    }
                    numComparisons++;
                }
            }
            log("Number of comparisons made for input of size "+array.length+": "+numComparisons);
            return pairsList;
        }

        public static void log(Object o){

            System.out.println(o);

        }

        //Asymptotic complexity unknown
        public static ArrayList<Pairs> equalInLinear(int[] array){

            int numComparisons = 0; //for big O Analysis
            ArrayList<Pairs> pairsList = new ArrayList<Pairs>();
            for(int i = 0;i<array.length;i++){
                //j=i+1 is the only difference between this method and
                //the previous one. 
                for(int j=i+1;j<array.length;j++){
                    if(array[i]+array[j]==10 && i!=j && i<j){
                        Pairs pair = new Pairs(i,j);
                        pairsList.add(pair);    
                    }
                    numComparisons++;
                }
            }
            log("Number of comparisons made for input of size "+array.length+": "+numComparisons);
            return pairsList;
        }
    }

EqualPairsTest.java

    import static org.junit.Assert.*;
    import java.util.ArrayList;
    import org.junit.Test;
    import Utilities.Pairs;
    import junit.framework.TestCase;

    public class EqualPairsTest extends TestCase {
        @Test
        public void testEqualSimpleOne() {

            int[] arr1={1,9};
            ArrayList<Pairs> p =EqualPairs.equal(arr1);

            assertEquals(1,p.get(0).getSecond());
            assertEquals(0,p.get(0).getFirst());
        }

        public void testEqualSimpleTwo(){

            int[] arr={3,5,6,7,5,-1,11};
            ArrayList<Pairs> p = EqualPairs.equal(arr);

            assertEquals(0, p.get(0).getFirst()); 
            assertEquals(3,p.get(0).getSecond());  

            assertEquals(1, p.get(1).getFirst());   
            assertEquals(4, p.get(1).getSecond()); 

            assertEquals(5, p.get(2).getFirst()); 
            assertEquals(6, p.get(2).getSecond());      
        }

        public void testEqualLinearSimple(){

            int[] arr1={1,9};
            ArrayList<Pairs> p =EqualPairs.equalInLinear(arr1);

            assertEquals(1,p.get(0).getSecond());
            assertEquals(0,p.get(0).getFirst());
        }

        public void testEqualInLinearSimpleTwo(){

            int[] arr={3,5,6,7,5,-1,11};
            ArrayList<Pairs> p = EqualPairs.equalInLinear(arr);

            assertEquals(0, p.get(0).getFirst()); 
            assertEquals(3,p.get(0).getSecond());  

            assertEquals(1, p.get(1).getFirst());   
            assertEquals(4, p.get(1).getSecond()); 

            assertEquals(5, p.get(2).getFirst()); 
            assertEquals(6, p.get(2).getSecond()); 

        }
    }
\$\endgroup\$
4
\$\begingroup\$

\$O(n^2)\$, not linear

The second algorithm is superior to the first, but is still an \$O(n^2)\$ algorithm. Furthermore, you have some redundant checks. This:

               if(array[i]+array[j]==10 && i!=j && i<j){

could be turned into this:

                if (array[i] + array[j] == 10) {

because j starts at i+1 so you know the last two conditions are always true.

Faster methods

One faster method would be to sort the array first. Then you can locate the pairs in linear time after that. This would be \$O(nlog(n))\$ total time. However, depending on how duplicates are handled, this could also degenerate to \$O(n^2)\$ time (for example an array of all 5's).

An even faster method would be to use a HashMap to store each value that you have seen so far. Then when you come across a new value such as 7, you use the HashMap to look up whether you have seen a 3 so far. If you have, then 7/3 is a valid pairing. This will run in \$O(n)\$ time if duplicates are not printed.

Keep in mind that if all duplicate pairs must be printed, no solution will do better than \$O(n^2)\$, because you will need to print every pair if the array consists of all 5's.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.