Created
October 20, 2016 13:24
-
-
Save jianminchen/ed96f667ca20d4ce6e5da61315e17cd5 to your computer and use it in GitHub Desktop.
HackerRank - fraudulent activity notification - first submission - score zero, pass 2 test cases, 5 test cases runtime error.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
using System; | |
using System.Collections.Generic; | |
using System.Linq; | |
using System.Text; | |
using System.Threading.Tasks; | |
namespace FraudulentActivityNotifications | |
{ | |
class Program | |
{ | |
/* | |
* https://www.hackerrank.com/contests/openbracket/challenges/fraudulent-activity-notifications | |
* 7:45am | |
* start to read the problem statement | |
* 8:14am | |
* To save time, store first d days expenditures into the array, | |
* sort the array. O(dlogd) time complexity | |
* To iterate, how to use existing sorted result, remove first one | |
* in the array, and then, add a new one to the sorted result. | |
* | |
* Extra space - sort array -> LinkedList -> remove first one in the array, | |
* and then add one more in the LinkedList | |
* | |
* 8:25am start to write code | |
* Write first version - be careful on time complexity | |
* Avoid timeout issues | |
* | |
* | |
* 12:25pm | |
* Find the bug | |
* deadloop | |
* write a test function using test case | |
* 9 5 | |
* 2 3 4 2 3 6 8 4 5 | |
*/ | |
static void Main(string[] args) | |
{ | |
processing(); | |
//testing(); | |
} | |
/* | |
* test case: | |
* * 9 5 | |
* 2 3 4 2 3 6 8 4 5 | |
*/ | |
private static void testing() | |
{ | |
int n = 9; | |
int d = 5; | |
string[] expenditures = "2 3 4 2 3 6 8 4 5".Split(' '); | |
int result = calculateNotification(n, d, expenditures); | |
} | |
/* | |
* standalone function: | |
* 12:27am | |
*/ | |
private static void processing() | |
{ | |
string[] input = Console.ReadLine().Split(' '); | |
int n = Convert.ToInt32(input[0]); | |
int d = Convert.ToInt32(input[1]); | |
string[] expenditures = Console.ReadLine().Split(' '); | |
Console.WriteLine(calculateNotification(n, d, expenditures)); | |
} | |
/* | |
* start at 8:34am | |
* | |
* 8:52am | |
* http://stackoverflow.com/questions/2349589/is-this-a-good-way-to-iterate-through-a-net-linkedlist-and-remove-elements | |
* | |
* 9:05am | |
* exit the function | |
* Ready to do static analysis | |
* 9:11am | |
* first execution on HackerRank | |
* 9:18am | |
* score 0 out of 20 | |
* pass test case #0 and #6, | |
* timeout on test case #1 - #5 | |
* | |
* | |
* Second trial: | |
* use binary search to speed up, O(logd) instead of linear search O(d) | |
* work on code refactoring on 9:27am | |
* | |
* copy existing array | |
* http://stackoverflow.com/questions/943635/getting-a-sub-array-from-an-existing-array | |
* | |
* time complexity: | |
* set up the upper limit to (1) | |
* http://stackoverflow.com/questions/21122143/what-is-the-time-complexity-for-copying-list-back-to-arrays-and-vice-versa-in-ja | |
* LinkedList.ToArray() - C#, | |
* | |
* 10:11am | |
* start to review the code | |
* | |
* 10:24am | |
* Bug to avoid: | |
* Add position vs Remove position | |
* | |
* 10:40am | |
* Java AddRange | |
* C# bulk copy | |
* http://stackoverflow.com/questions/9836471/why-is-addrange-faster-than-using-a-foreach-loop | |
*/ | |
private static int calculateNotification( | |
int n, | |
int d, | |
string[] expenditures) | |
{ | |
// Extra space | |
int[] firstDDays = new int[d]; | |
for (int i = 0; i < d; i++) | |
firstDDays[i] = Convert.ToInt32(expenditures[i]); | |
Array.Sort(firstDDays); // assuming increasing order | |
int[] runner = new int[d]; | |
Array.Copy(firstDDays, runner, d); // O(n) | |
int count = 0; | |
for (int i = d; i < n; i++) | |
{ | |
int[] data = runner; // assuming that it can be O(1) | |
double medium = (d % 2 == 1) ? | |
data[d / 2] : | |
(data[d / 2 - 1] + data[d / 2]) / 2.0; | |
int toAdd = Convert.ToInt32(expenditures[i]); | |
if (toAdd >= 2 * medium) | |
count++; | |
int inc = i - d; | |
int toRemove = Convert.ToInt32(expenditures[0 + inc]); | |
int indexR = binarySearch(data, toRemove); | |
int indexAd = binarySearchAdd(data, toAdd); | |
runner = customizedArrayCopy(data, indexR, indexAd, toAdd, toRemove, d); | |
} | |
return count; | |
} | |
/* | |
* start at 12:13pm | |
* search in a sorted array in ascending order | |
* using binary search | |
* exit at 12:23pm | |
* | |
*/ | |
private static int binarySearch(int[] data, int toFind) | |
{ | |
int start = 0; | |
int end = data.Length - 1; | |
if (toFind < data[0] || toFind > data[end]) | |
return -1; | |
while (start <= end) | |
{ | |
int middle = start + (end - start) / 2; | |
int compare = data[middle]; | |
if (compare < toFind) | |
start = middle; | |
else if (compare > toFind) | |
end = middle; | |
else | |
return middle; | |
} | |
return -1; | |
} | |
/* | |
* 2 3 4 6 8 | |
* toFind is 5 | |
* need to return position: 3 | |
* | |
* Find position in sorted array to insert a new value, | |
* maintain the sorted order - ascending order after insertion. | |
* | |
*/ | |
private static int binarySearchAdd(int[] data, int toFind) | |
{ | |
int start = 0; | |
int end = data.Length - 1; | |
if (toFind < data[0] || toFind > data[end]) | |
return -1; | |
while (end - start > 1) | |
{ | |
int middle = start + (end - start) / 2; | |
int compare = data[middle]; | |
if (compare < toFind) | |
start = middle; | |
else if (compare > toFind) | |
end = middle; | |
else | |
return middle; | |
} | |
return end; | |
} | |
/* | |
* start from 10:46am | |
* reference: | |
* http://stackoverflow.com/questions/9836471/why-is-addrange-faster-than-using-a-foreach-loop | |
* | |
* bug to avoid: | |
* indexR vs indexAd | |
* | |
* if indexAd == -1, | |
* edge case, add one at the end of array; | |
* two sections | |
* | |
* otherwise, | |
* Arry will be divided into 3 section | |
* Section 0 / section 1 / section 2 | |
* one more to add - can be 0 and 1, or 1 and 2 | |
* one more to remove - can be 0 and 1, or 1 and 2 | |
* | |
* Analyze if the function can be splitted into two: | |
* | |
* 11:16am | |
* still work on the coding | |
* | |
* 11:43am | |
* complete the first writing | |
* need to review the code | |
* | |
* 12:12pm | |
* end of reasoning, | |
* start to write the function | |
* binarySearch | |
* | |
* 12:5pm | |
* indexR = indexAd | |
* for test case: | |
* 9 5 | |
* 2 3 4 2 3 6 8 4 5 | |
* last one, when i = 8 | |
* | |
* 1:20pm | |
* run time error | |
* need to work on this issue | |
* | |
*/ | |
private static int[] customizedArrayCopy( | |
int[] data, | |
int indexR, | |
int indexAd, | |
int toAdd, | |
int toRemove, | |
int size) | |
{ | |
int[] data2 = new int[size]; | |
if (indexAd == -1) | |
{ | |
bool isStart = toAdd < data[0]; | |
int start = 0; | |
if (isStart) | |
{ | |
start = 1; | |
data2[0] = toAdd; | |
} | |
Array.Copy(data, 0, data2, 0 + start, indexR); | |
int sourceIndex = indexR + 1; // skip one element - data[indexR] | |
int destinationIndex = indexR + start; | |
int length = size - sourceIndex; | |
Array.Copy(data, sourceIndex, data2, destinationIndex, length); | |
if (!isStart) | |
data2[size - 1] = toAdd; | |
} | |
else | |
{ | |
bool removeFirst = indexR < indexAd; | |
bool addFirst = indexAd > indexR; | |
bool samePos = indexAd == indexR; | |
int min = Math.Min(indexR, indexAd); | |
int max = Math.Max(indexR, indexAd); | |
Array.Copy(data, 0, data2, 0, min); | |
if (removeFirst) | |
{ | |
int index1 = indexR; | |
// section 1 | |
int sourceIndex = index1 + 1; // skip one element | |
int destinationIndex = index1; | |
int length = indexAd - sourceIndex; // give me a reason why it is correct: two positions | |
Array.Copy(data, sourceIndex, data2, destinationIndex, length); | |
// add position | |
int addPos = indexAd - 1; // adjust one, since one is removed; also, indexAd >=1, since indexAd > indexR | |
data2[addPos] = toAdd; | |
sourceIndex = addPos + 1; | |
destinationIndex = addPos; | |
length = size - sourceIndex; | |
Array.Copy(data, sourceIndex, data2, destinationIndex, length); | |
} | |
else if (addFirst) // add one element first | |
{ | |
int index1 = indexAd; | |
// add position | |
int addPos = indexAd; | |
data2[addPos] = toAdd; | |
// section 1 | |
int sourceIndex = index1; | |
int destinationIndex = index1 + 1; // one is added | |
int length = indexR - sourceIndex; | |
Array.Copy(data, index1 + 1, data2, destinationIndex, length); | |
sourceIndex = indexR + 1; | |
destinationIndex = indexR; | |
length = size - sourceIndex; | |
Array.Copy(data, sourceIndex, data2, destinationIndex, length); | |
} | |
else | |
{ | |
data[indexR] = toAdd; | |
Array.Copy(data, 0, data2, 0, size); | |
} | |
} | |
return data2; | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment