While solving a problem on an online judge, I tried with these two implementations.
These two implementations do the same thing. Task is to report duplicate entry for a given set of data.
Implementation #1 : Converts input data to a String
and adds to a HashSet
. After all the input is read, appropriate message is displayed.
class Databse2 {
public static void main(String[] args) throws Exception{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int t=Integer.parseInt(br.readLine());//number of test cases
int N=0,R=0,C=1;
while(t-->0){ //while there are more test cases
HashSet<String> set=new HashSet<String>();
StringTokenizer st=new StringTokenizer(br.readLine());
while(st.hasMoreTokens()){
N=Integer.parseInt(st.nextToken());
R=Integer.parseInt(st.nextToken());//Number of Rows of data
}
int ID=0,SC=0;boolean haha=true;
for(int i=0;i<R;i++){ //for number of rows read each record in the row
st=new StringTokenizer(br.readLine());
while(st.hasMoreTokens()){
ID=Integer.parseInt(st.nextToken());
SC=Integer.parseInt(st.nextToken());
}
String key=ID+""+SC;//convert to string,this combo is used to check for duplicates
haha=haha && set.add(key);
}
if(haha)
System.out.println("Scenario #"+C+": possible");
else System.out.println("Scenario #"+C+": impossible");
C++;
}
}
}
Running time = 3.41 sec (for N number of test cases)
Implementation #2: Same task is accomplished as in Implementation #1 but in a different way. An object is created based on input type and added to HashSet
.
class Database {
private int ID;
private int SC;
public Database(int ID,int SC){
this.ID=ID;
this.SC=SC;
}
@Override
public boolean equals(Object obj) {
return (obj instanceof Database) ? ID==((Database)obj).ID:SC==((Database)obj).SC;
}
@Override
public int hashCode() {
return 31*(ID+SC);
}
public static void main(String[] args) throws Exception{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int t=Integer.parseInt(br.readLine());
int N=0,R=0,C=1;
while(t-->0){
HashSet<Database> set=new HashSet<Database>();
StringTokenizer st=new StringTokenizer(br.readLine());
while(st.hasMoreTokens()){
N=Integer.parseInt(st.nextToken());
R=Integer.parseInt(st.nextToken());
}
int ID=0,SC=0;boolean haha=true;
for(int i=0;i<R;i++){
st=new StringTokenizer(br.readLine());
while(st.hasMoreTokens()){
ID=Integer.parseInt(st.nextToken());
SC=Integer.parseInt(st.nextToken());
}
haha=haha?set.add(new Database(ID, SC)):false;
}
String str=haha?"Scenario #"+C+": possible":"Scenario #"+C+": impossible";
System.out.println(str);
C++;
}
}
}
Running Time #2 = 2.74 sec (for N number of test cases)
What causes implementation #2 to be faster? Is it the hashCode
method?