CSC 385 –Assignment 4 –Faster SortingAlgorithms .This problem is taken from a hackerrank programming challenge. The problem is tagged as having medium difficulty in hacker rank:(https://www.hackerrank.com/challenges/fraudulent-activity-notifications) Problem Description—Fraud DetectionHackerLand National Bank has a simple policy for warning clients about possiblefraudulent account activity. If the amount spent by a client on a particular day is greaterthan or equal to 2 ×the client's medianspending for the last d days, they send the client a notification about potential fraud. The bank doesn't send the client any notificationsuntil they have at least d prior days of transaction data.Given the value of d and a client's total daily expenditures for a period of n days (where n>d) write amethod which returns the number of times the client will receive a notification over all days.Note: Your algorithm time efficiency should not exceed O(nd) where n is the total number of daily expenditures and d is the number of prior day expenditures used for frauddetection.Your algorithm space complexity should not exceed O(n+d).where n is the total number of daily expenditures and d is the number of prior day expenditures used for frauddetection.Space complexity is defined as the input size + any auxiliary space that is used by the algorithm. The space complexity of a variable that holds a single item is of O(1) but the space complexity of a variable that holds a collection of n items is O(n). Often times we ignore the input size and only compare space complexity of algorithms based on the auxiliary space they use. For example, merge sort space complexity is O(n) because it uses an auxiliary array of size O(n) to store merged subarrays. The textbook does not talk much about space complexity. To learn more about space complexity please read this brief lecture from North Western University and watch this short Youtube video. What you need to do: To receive full credit, your method must have the following signature:public int getNumberOfFrauds(int[] dailyExpeditures, int d) For example:               getNumberOfFrauds({4,3,2,2,3,6,8,9,10}, 5)must return 3 Explanation: We must determine the total number of notifications the client receivesover a period of days. For the first five days, the customer receives no notificationsbecause the bank has insufficient transaction data and the number of notifications arezero.On the sixth day, the bank has 5 days of prior transaction data {4,3,2,2,3} and the medianis 3 dollars, the client spent 6 dollars on the sixth day which triggers a notificationbecause 6 >=2* median, so the number of notifications after sixth day is 1. On the seventh day, the bank has 5 days of prior transaction data {3,2,2,3,6} and themedian is 3 dollars, the client spent 8 dollars on the seventh day which triggers a notification because 8 >=2* median, so the number of notifications after seventh day is 2. On the eights day, the bank has 5 days of prior transaction data {2,2,3,6,8} and themedian is 3 dollars, the client spent 9 dollars on the eighth day which triggers a notification because 9>=2* median, so the number of notifications after eighth day is 3. On the ninth day, the bank has 5 days of prior transaction data {2,3,6,8,9} and themedian is 6 dollars, the client spent 10 dollars on the ninth day which does not triggersa notification because 10<2* median, so the number of notifications after ninth daystays at 3. We then return the final value of notifications which is 3. Hints: You can store the first d day spending in another array and sort this array using a fast sorting algorithm such as quick sort. For instance, for the above example, the sortedarray would be {2,2,3,3,4}. Compare the next day spending ( 6 dollars) with the medianand update the number of frauds. Then replace the first day spending (4 dollars) withd+1 day spending (6 dollars) in the sorted array, that is: {2,2,3,3,6}. If the resulting arrayis not sorted, shift array elements until it is sorted again. Find the median and compareit with d+2 day spending and update the number of frauds. Next, replace the second day spending ( 3 dollars) with d+2 day spending (8 dollars) in the sorted array, that is:{2,2,8,3,6}. If the resulting array is not sorted, shift the array elements until it is sorted again {2,2,3,6,8}. Find the median and compare it with d+3 day spending and updatethe number of frauds. Continue this process until you get to the last day spending and return the number of frauds.

Computer Networking: A Top-Down Approach (7th Edition)
7th Edition
ISBN:9780133594140
Author:James Kurose, Keith Ross
Publisher:James Kurose, Keith Ross
Chapter1: Computer Networks And The Internet
Section: Chapter Questions
Problem R1RQ: What is the difference between a host and an end system? List several different types of end...
icon
Related questions
Question
CSC 385 –Assignment 4 –Faster SortingAlgorithms .This problem is taken from a hackerrank programming challenge. The problem is tagged as having medium difficulty in hacker rank:(https://www.hackerrank.com/challenges/fraudulent-activity-notifications) Problem Description—Fraud DetectionHackerLand National Bank has a simple policy for warning clients about possiblefraudulent account activity. If the amount spent by a client on a particular day is greaterthan or equal to 2 ×the client's medianspending for the last d days, they send the client a notification about potential fraud. The bank doesn't send the client any notificationsuntil they have at least d prior days of transaction data.Given the value of d and a client's total daily expenditures for a period of n days (where n>d) write amethod which returns the number of times the client will receive a notification over all days.Note: Your algorithm time efficiency should not exceed O(nd) where n is the total number of daily expenditures and d is the number of prior day expenditures used for frauddetection.Your algorithm space complexity should not exceed O(n+d).where n is the total number of daily expenditures and d is the number of prior day expenditures used for frauddetection.Space complexity is defined as the input size + any auxiliary space that is used by the algorithm. The space complexity of a variable that holds a single item is of O(1) but the space complexity of a variable that holds a collection of n items is O(n). Often times we ignore the input size and only compare space complexity of algorithms based on the auxiliary space they use. For example, merge sort space complexity is O(n) because it uses an auxiliary array of size O(n) to store merged subarrays. The textbook does not talk much about space complexity. To learn more about space complexity please read this brief lecture from North Western University and watch this short Youtube video. What you need to do: To receive full credit, your method must have the following signature:public int getNumberOfFrauds(int[] dailyExpeditures, int d) For example:
 
 
 
 
 
 
 
getNumberOfFrauds({4,3,2,2,3,6,8,9,10}, 5)must return 3 Explanation: We must determine the total number of notifications the client receivesover a period of days. For the first five days, the customer receives no notificationsbecause the bank has insufficient transaction data and the number of notifications arezero.On the sixth day, the bank has 5 days of prior transaction data {4,3,2,2,3} and the medianis 3 dollars, the client spent 6 dollars on the sixth day which triggers a notificationbecause 6 >=2* median, so the number of notifications after sixth day is 1. On the seventh day, the bank has 5 days of prior transaction data {3,2,2,3,6} and themedian is 3 dollars, the client spent 8 dollars on the seventh day which triggers a notification because 8 >=2* median, so the number of notifications after seventh day is 2. On the eights day, the bank has 5 days of prior transaction data {2,2,3,6,8} and themedian is 3 dollars, the client spent 9 dollars on the eighth day which triggers a notification because 9>=2* median, so the number of notifications after eighth day is 3. On the ninth day, the bank has 5 days of prior transaction data {2,3,6,8,9} and themedian is 6 dollars, the client spent 10 dollars on the ninth day which does not triggersa notification because 10<2* median, so the number of notifications after ninth daystays at 3. We then return the final value of notifications which is 3. Hints: You can store the first d day spending in another array and sort this array using a fast sorting algorithm such as quick sort. For instance, for the above example, the sortedarray would be {2,2,3,3,4}. Compare the next day spending ( 6 dollars) with the medianand update the number of frauds. Then replace the first day spending (4 dollars) withd+1 day spending (6 dollars) in the sorted array, that is: {2,2,3,3,6}. If the resulting arrayis not sorted, shift array elements until it is sorted again. Find the median and compareit with d+2 day spending and update the number of frauds. Next, replace the second day spending ( 3 dollars) with d+2 day spending (8 dollars) in the sorted array, that is:{2,2,8,3,6}. If the resulting array is not sorted, shift the array elements until it is sorted again {2,2,3,6,8}. Find the median and compare it with d+3 day spending and updatethe number of frauds. Continue this process until you get to the last day spending and return the number of frauds.
 
 
 
 
 
 
 
Expert Solution
trending now

Trending now

This is a popular solution!

steps

Step by step

Solved in 2 steps

Blurred answer
Similar questions
Recommended textbooks for you
Computer Networking: A Top-Down Approach (7th Edi…
Computer Networking: A Top-Down Approach (7th Edi…
Computer Engineering
ISBN:
9780133594140
Author:
James Kurose, Keith Ross
Publisher:
PEARSON
Computer Organization and Design MIPS Edition, Fi…
Computer Organization and Design MIPS Edition, Fi…
Computer Engineering
ISBN:
9780124077263
Author:
David A. Patterson, John L. Hennessy
Publisher:
Elsevier Science
Network+ Guide to Networks (MindTap Course List)
Network+ Guide to Networks (MindTap Course List)
Computer Engineering
ISBN:
9781337569330
Author:
Jill West, Tamara Dean, Jean Andrews
Publisher:
Cengage Learning
Concepts of Database Management
Concepts of Database Management
Computer Engineering
ISBN:
9781337093422
Author:
Joy L. Starks, Philip J. Pratt, Mary Z. Last
Publisher:
Cengage Learning
Prelude to Programming
Prelude to Programming
Computer Engineering
ISBN:
9780133750423
Author:
VENIT, Stewart
Publisher:
Pearson Education
Sc Business Data Communications and Networking, T…
Sc Business Data Communications and Networking, T…
Computer Engineering
ISBN:
9781119368830
Author:
FITZGERALD
Publisher:
WILEY