It took me another 1 full day and many try-n-error to get it perfect 100%
In the beginning, I’m using 2 Array of Integer as shown below. There are few test cases that failed because the time taken to process is more than the limit given.
 |
100% accuracy but the overall score is 18%
|
With an improvement in the code, I managed to improve the overall score to 54%. I managed to reduce some of the performance issues.
 |
| 100% accuracy but overall score is 54% |
It looks like Array.copyOf and Arrays.stream do take a longer time to process.
Another improvement has lessened the length of the code and improve the overall score to 63%
 |
| 63% overall score |
The code above simply set the C array to value one of the position indexes of A. Here are the list of test that it fails
▶medium_range
arithmetic sequences, X = 5,000✘TIMEOUT ERROR
running time: 0.112 sec., time limit: 0.100 sec.
1.0.112 sTIMEOUT ERROR, running time: 0.112 sec., time limit: 0.100 sec.
▶large_random
10 and 100 random permutation, X = ~10,000✘TIMEOUT ERROR
running time: 1.128 sec., time limit: 0.880 sec.
1.1.128 sTIMEOUT ERROR, running time: 1.128 sec., time limit: 0.880 sec.
2.0.200 sOK
▶large_permutation
permutation tests✘TIMEOUT ERROR
running time: 1.716 sec., time limit: 0.880 sec.
1.1.716 sTIMEOUT ERROR, running time: 1.716 sec., time limit: 0.880 sec.
2.6.000 sTIMEOUT ERROR, Killed. Hard limit reached: 6.000 sec.
▶large_range
arithmetic sequences, X = 30,000✘TIMEOUT ERROR
Killed. Hard limit reached: 6.000 sec.
1.6.000 sTIMEOUT ERROR, Killed. Hard limit reached: 6.000 sec.
I changed my strategy. Instead of using a normal Array of integer, I implement
List &
ArrayList.
 |
| Bad improvement - 54% overall |
Instead of getting better, it is getting worse. I google on it and found that List do have performance issues and found few suggestions on it. Either use Hashmap, HashSet, TreeSet or GapList.
I do improve the process on my laptop and surprisingly, it was way faster than List or ArrayList. Unfortunately, Codility does not support the library. Hence, I need to look for another alternative.
Based on the performance comparison between Hashmap, HashSet, and TreeSet, HashSet seems promising. And so it did. My final code is using HashSet and finally, the result shown is 100%. Here is part of the code:
1. Definition
HashSet list= new HashSet();
2. Used
for(int idx = 0; idx < A.length; idx++){
if ( !list.contains(A[idx]) ){
list.add(A[idx]);
}
if ( list.size() == X ){
return idx;
}
}
I also found a few solutions which score 100%
This solution was shared by someone and it claims score 100/100
public int solution(int X, int[] A) {
int[] B = A.Distinct().ToArray();
return (B.Length != X) ? -1 : Array.IndexOf(A, B[B.Length - 1]);
}
This solution was shared too and score 100/100 for correctness, task, and performance
public int solution(int X, int[] A) {
HashSet unique= new HashSet();
for (int i = 1; i<= X; i++){
unique.add(i);
}
for(int j = 0; j< A.length; j++){
if(unique.contains(A[j])){
unique.remove(A[j]);
if(unique.isEmpty()){
return j;
}
}
}
return -1;
}
Full source code is accessible at
- Bitbucket — git clone https://masteramuk@bitbucket.org/fullstacksdev/codility-frogriverone.git
- Github — git clone https://github.com/masteramuk/codility-lessoncode.git
