Created
March 29, 2018 05:05
-
-
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.
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; | |
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