Amazon Coding Test - Product Ratings for n days given in a list. Find consecutive days when product rating is decreased by 1 in O(n) .
There are n number of rating in a list for a product, representing rating for n consecutive days.
Find the consecutive number of ratings such that rating is fallen from previous day by 1.
ex:
input List: 4,3,5,4,3
Output: 9
explaination:
there are days: [4], [3], [5], [4], [3]
pairs: [4,3], [5,4], [4,3]
3 days: [5,4,3]
Total: 9
I was asked this question in amazon online assessment, and I couldn't solve it in efficient manner in time.
After the test I tried to come up with the algorithm:
Algorithm:
Start with the sequence, and count the sequence length till we get an element which is not in the desired sequence.
start from 4, then 3, then 5 (which is not appropriete) in the sequence.
we have current sequence length as 2 (4 and 3).
so we calculate possible number of consecutive combination of this sequence of length 'seq_len'
possible_consecutive_combinations = seq_len*(seq_len+1)/2.
Once we have the inappropriete element, then reset the sequence_len =0, and do this till the end of the list.
Below is my implementation of the same.
import java.util.Arrays;
import java.util.List;
public class Test {
public static void main(String[] args) {
List<Integer> list = Arrays.asList(8,7,2,9,8,5,4,3,2,6,5);
System.out.println(getRatingCount(list));
}
public static int getRatingCount(List<Integer> ratings) {
int seqLength = 0;
int count = 0;
boolean seq = false;
for(int i = 0;i<ratings.size();i++) {
count++;
if(i==0) continue;
seq = ratings.get(i-1) - ratings.get(i) ==1;
if(!seq) {
count += (seqLength*(seqLength+1)/2);
seqLength=0;
} else {
seqLength++;
}
}
if(seqLength>0) {
count += (seqLength*(seqLength+1)/2);
}
return count;
}
}