Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Suppose you are supplied with a file containing a list of words like ABC, BCD , CAB
( say each word in new line ). now you have to suggest algorithm for this problem -
When a user type some character, we have to suggest him next character and basis of
suggestion is that the character you are going to suggest should have maximum occurrence at that position among all these words.
For example , Let's say words are
ABC
BCD
CBA
Now if user types 'A' we have to suggest him 'B' as next character because if you see at second position
in all words 'B' is occurring most number of times ( 2 times ).
similarly if he types 'AB' then we need to suggest him third character as 'C' as in third index all words
have same occurrence but 'C' comes first.
KEYWORDS:
maximum count -> list the character
second criteria: first
QUESTION:
A, NEXT B
AB -> C
words: list of stream
A, -> B
AC, -> B
ABC
BC
CB
-> A - Z,
counting sort
index -> count
countSorting save each char at same position -> O(26) -> countingSort[index][char] char occurrences in all word at the same position at index = i
char[] maximumCount[index]
time complexity: 26 * n
first occurence char at each index[] ->
void preprocess(string[] arr);
char suggest(string input);
// keep original order ->
public static char[] saveMaximumCount(string[] words)
{
if(words == null)
return new char[0];
var maxLength = getMaxLength(words);
var countingSort = new int[26,maxLength]; // first char showing index is saved in third //dimension
var countingSortOrderIndex = new int[26,maxLength]; // first char showing index is saved in third //dimension
ABC
ACB
BCD
// 1 O(26) array
// 1 O(n) array
n strings
// maxLength = m
int[] freq = new int[] freq(26);
char[] firstChar = new char[maxLength];
for (int i = 0; i < m; i++)
{
reset(freq);
// a-z 0
int maxFreq = 0;
for (int j = 0; j < n; j++)
{
// arr[j] 在index out of range
if (arr[j].Length >= i+1)
{
freq[arr[j][i] - 'a']++;
if (freq[arr[j][i] - 'a'] > maxFreq)
{
// update maxFreq
firstChar[j] = arr[j][i];
}
}
}
}
// 2 2-dimension array
// 1 n*1 array
// size
int orderIndex = 0;
foreach(var item in words)
{
for(int i = 0 ; i < item.length; i++)
{
var visit = item[0];
if(countingSort[visit - 'a', i][0] == 0)
countingSort[visit - 'a', i][1] = orderIndex;
countingSort[visit - 'a', i][0]++; // count number
}
orderIndex++;
}
var selectedMax = new char[maxLength]; // sort - max value/ orderIndex
for(int i = 0; i < maxLength; i++)
{
// please sort countSort, and then consider orderIndex
var maxCount = 0;
var maxOrderIndex = -1;
for(int charIndex = 0; charIndex < 26; charIndex++)
{
var current = countingSort[char,i][0];
var currentOrderIndex = countingSort[char,i][1];
var bigger = current > maxCount;
maxCount = bigger? current : maxCount;
maxOrderIndex = bigger? current : maxOrderIndex ;
if(current == maxCount && currentOrderIndex < maxOrderIndex)
{
maxOrderIdnex = currentOrderIndex ;
}
}
}
return selectedMax;
}
private static char[] findFirstCharAtEachIndex(string[] words)
8:00 am - 9:46 am
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.