Created
January 2, 2017 03:31
-
-
Save jianminchen/58a78b5736da5b79004278116ee5d0c9 to your computer and use it in GitHub Desktop.
Hackerearth - simple function - code review - https://www.hackerearth.com/problem/algorithm/simple-function/ - pass all test cases
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.Diagnostics; | |
using System.Linq; | |
using System.Text; | |
using System.Threading.Tasks; | |
namespace SimpleFunction_StudyCode | |
{ | |
class Program | |
{ | |
public static int DIGITS = 10; | |
public static int NO_BASKETS = 2; | |
public static int NUMBER_DIGITS = 1000; | |
public static int[][][] hashingResults = new int[NO_BASKETS][][]; // 2, 1000, 10 - 80KB | |
internal class QueryData | |
{ | |
public int n1, n2; | |
public string[] numbers1, numbers2; | |
} | |
static void Main(string[] args) | |
{ | |
ProcessSimpleFunction(); | |
//RunSampleTestcase(); | |
} | |
public static void RunSampleTestcase() | |
{ | |
IList<QueryData> input = new List<QueryData>(); | |
QueryData one = new QueryData(); | |
one.n1 = 2; | |
one.n2 = 2; | |
one.numbers1 = new string[] {"234526", "8345" }; | |
one.numbers2 = new string[] {"333564", "98847675" }; | |
input.Add(one); | |
IList<string> result = CalculateProbabilty(input); | |
Debug.Assert(result[0].CompareTo("0.750") == 0); | |
} | |
public static void ProcessSimpleFunction() | |
{ | |
IList<QueryData> input = ProcessInput(); | |
IList<string> result = CalculateProbabilty(input); | |
foreach (string s in result) | |
Console.WriteLine(s); | |
return; | |
} | |
/* | |
* 1. calculate even number's count | |
* 2. calculate probability | |
* 3. convert to string - a decimal data type with 3 decimals | |
* 4. put the return in a list | |
*/ | |
public static IList<string> CalculateProbabilty(IList<QueryData> input) | |
{ | |
IList<string> output = new List<string>(); | |
if (input == null || input.Count == 0) | |
{ | |
output.Add(0.ToString("N3")); | |
return output; | |
} | |
HashingResults_Declaration(); | |
foreach(QueryData data in input) | |
{ | |
HashingResults_Initialization(); | |
int n1 = data.n1; | |
int n2 = data.n2; | |
for (int i = 0; i < n1; i++) | |
{ | |
char[] current = data.numbers1[i].ToCharArray(); | |
Hash(current, i, 0); | |
} | |
for (int i = 0; i < n2; i++) | |
{ | |
char[] current = data.numbers2[i].ToCharArray(); | |
Hash(current, i, 1); | |
} | |
long count = 0; | |
for (int i = 0; i < n1; i++) | |
{ | |
for (int j = 0; j < n2; j++) | |
{ | |
count += CheckNumberIsEven(i, j); | |
} | |
} | |
float probability = (float)((float)(count) / (float)(n1 * n2)); | |
output.Add(probability.ToString("N3")); | |
} | |
return output; | |
} | |
/* | |
* return: IList<QueryData> | |
*/ | |
private static IList<QueryData> ProcessInput() | |
{ | |
int queries = Convert.ToInt32(Console.ReadLine()); | |
IList<QueryData> input = new List<QueryData>(); | |
while (queries > 0) | |
{ | |
QueryData data = new QueryData(); | |
int[] baskets = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse); | |
data.n1 = baskets[0]; | |
data.n2 = baskets[1]; | |
data.numbers1 = new string[data.n1]; | |
data.numbers2 = new string[data.n2]; | |
for (int i = 0; i < data.n1; i++) | |
{ | |
data.numbers1[i] = Console.ReadLine(); | |
} | |
for (int i = 0; i < data.n2; i++) | |
{ | |
data.numbers2[i] = Console.ReadLine(); | |
} | |
input.Add(data); | |
queries--; | |
} | |
return input; | |
} | |
/* | |
* hashing function will be applied to the data, the result is a jagged array called hashingResults | |
* hashing results: | |
* int[NO_BASKETS][][]; // 2, 1000, 10 - 80KB | |
*/ | |
private static void HashingResults_Declaration() | |
{ | |
for (int i = 0; i < NO_BASKETS; i++) | |
{ | |
hashingResults[i] = new int[NUMBER_DIGITS][]; | |
for (int j = 0; j < NUMBER_DIGITS; j++) | |
{ | |
hashingResults[i][j] = new int[DIGITS]; | |
} | |
} | |
} | |
/* | |
* hashing results: | |
* int[NO_BASKETS][][]; // 2, 1000, 10 - 80KB | |
*/ | |
private static void HashingResults_Initialization() | |
{ | |
for (int i = 0; i < NO_BASKETS; i++) | |
{ | |
for (int j = 0; j < NUMBER_DIGITS; j++) | |
{ | |
for (int k = 0; k < DIGITS; k++) | |
{ | |
hashingResults[i][j][k] = 0; | |
} | |
} | |
} | |
} | |
/* | |
* | |
* @cache - char[] | |
* @nthNumber - each basket has n numbers, n from 0 to N-1 | |
* @serialNo - two baskets, so two values: 0, 1 | |
* | |
* hash function - | |
* map data of arbitrary size to data of fixed size | |
* int[][][] cache = new int[2][][]; // 2, 1000, 10 | |
* size of cache is 2 * 1000 * 10 * 4 bytes = 80KB | |
* | |
* '0' ascii value is 48 | |
*/ | |
private static void Hash(char[] cache, int nthNumber, int serialNo) | |
{ | |
for (int i = 0; i < cache.Length; i++) | |
{ | |
int digit = cache[i] - 48; | |
hashingResults[serialNo][nthNumber][digit] = 1; | |
} | |
} | |
/* | |
* digits from 1 to 9 | |
* return: 1 - even number 0 - odd number | |
*/ | |
private static int CheckNumberIsEven(int first, int second) | |
{ | |
int digitValue = 9; | |
while (digitValue > 0) | |
{ | |
if (hashingResults[0][first][digitValue] == 1 && | |
hashingResults[1][second][digitValue] == 1) | |
{ | |
break; | |
} | |
digitValue--; | |
} | |
return (digitValue % 2 == 0)? 1 : 0; | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment