Navigation Menu

Skip to content

Instantly share code, notes, and snippets.

@jianminchen
Created March 29, 2018 05:05
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/f06a7c1d0ac3a2ff8b3cbfc8da2c999f to your computer and use it in GitHub Desktop.
Save jianminchen/f06a7c1d0ac3a2ff8b3cbfc8da2c999f to your computer and use it in GitHub Desktop.
Word count engine - 30 minutes practice - there are bugs, cannot pass any test case.
using System;
using System.Collections.Generic;
using System.Linq;
class Solution
{
public static string[,] WordCountEngine(string document)
{
if(document == null)
return new string[0,0];
string lower = document.ToLower();
var replaced = lower.Replace('\'', ' ');
var split = replaced.Split(". !".ToCharArray());
var dict = putToDictionary(split);
var buckets = applyBucketSort(document, dict);
return toDimensionArray(buckets);
}
private static string[,] toDimensionArray(List<string>[] buckets)
{
}
private static Dictionary<string, int> putToDictionary(string[] words)
{
var dict = new Dictionary<string, int>();
foreach(var word in words)
{
if(dict.ContainsKey(word))
{
dict[word]++;
}
else
{
dict.Add(word, 1);
}
return dict;
}
}
private static string[] applyBucketSort(string document, Dictionary<string, int> dict)
{
var maxValue = dict.Values.Max();
var sorted = new List<string>[maxValue + 1];
for(int i = 0; i < maxValue + 1; i++)
sorted[i] = new List<string>();
var split = replaced.Split(". !".ToCharArray());
var hashSet = new HashSet<string>();
foreach(var word in split)
{
if(hashSet.Contains(word))
continue;
hashSet.Add(word);
var value = dict[word];
sorted[value].Add(word);
}
return sorted;
}
static void Main(string[] args)
{
}
}
/*
lower case the char
strip out punctuation
split words using whitepsace
Sort by number of occurrence - descending order
output to two dimension array
time complexity - bucket sort -> count - max integer, 3,
count - 3 in one bucket,
3 - practice
1 - makes, youll, only, get, by, just - sort by the orginal order
keep the original order of sentence
Sort ->
Extra dictionary<int, string>
1 - practice
2 - makes
Dictionary<string, integer>
Sort by dictionary value
OrderedDictionary ->
output -> bucket sort
go through orginal string - parse word by word ->
keep the order of orginal order
space complexity - polynomial space complexity
n, n^2, n^3
*/
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment