We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Fraudulent Activity Notifications
Fraudulent Activity Notifications
Sort by
recency
|
1169 Discussions
|
Please Login in order to post a comment
I see an implementation with counting sort and no queues but it's really complex. Like you need to keep track of the indices of the median(s) so when you update the counting array you know what the new median is in all cases. It seems way more complicated than an interview question should ask though.
I watched the video in the editorial. Using 2 priority queues will work but insertion, deletion, and swapping are O(log(n)) for heaps. Overall time complexity is O(nlogn). So it's not as performant as just using the counting array. Counting sort is o(n). It's not like 2 priority queues is an elegant solution with all the rebalancing needed.
Most solutions here are O(n^2) worst case (d is half of n)
int n = expenditure.size(); if(n <= d) return 0;
for(int i=0; i
sort(v.begin(), v.end());
for(int i=d; i= (2*median)) notifications++; v.erase(find(v.begin(), v.end(),expenditure[i-d]));
}
return notifications; }
Simple C++ solution:
double calcMedian(vector v, int d) { if(d % 2 == 1) return v[d/2]; else return (v[d/2] + v[d/2 - 1])/2.0; }
int activityNotifications(vector expenditure, int d) { //multiset s; vector v; double median = 0; int notifications = 0;
}
Use binary search ranther than full sort of the trailing is the key point to improve performance.
Can anyone help to check where i miss. 1 test case is repeatedly failing due to time limit exceed
int activityNotifications(vector expenditure, int d) { vector med; int i,j,median,pos,s=expenditure.size(),c=0,c2=0; float m; median=d/2; for(i=0;i=d) { if(d%2==0) m=(float)(med[median]+med[median-1])/2.0; else m=(float)med[median]; if(expenditure[i]>=2*m) c2++;
auto ind=find(med.begin(),med.end(),expenditure[c]); med.erase(ind); c++; } if(med.empty()||med[0]>expenditure[i]) med.insert(med.begin(),expenditure[i]); else if(med[med.size()-1] } return c2; }