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());
}
}
