Skip to content

Instantly share code, notes, and snippets.

Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jianminchen/58a78b5736da5b79004278116ee5d0c9 to your computer and use it in GitHub Desktop.
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
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