I was asked this question during an interview.
Print the pattern of characters from the given word by arranging the characters in ascending order based on the number of occurrencies.
Input:
"abbccbddddeeeee"Output:
a cc bbb dddd eeeee
I was not able to solve it on the spot, and I can't make my solution working for now.
Specifically, I'm having trouble with arranging in ascending order after populating a HashMap.
My code:
String test = "abbccbdddddddeeeee";
List<Character> orderedList = new ArrayList<Character>();
List<Integer> orderedNumber = new ArrayList<Integer>();
char[] testing = test.toCharArray();
int value = 1;
Map<Character, Integer> pattern = new HashMap<>();
for (int i = 0; i < testing.length; i ) {
value = 1;
if (!pattern.containsKey(testing[i])) {
pattern.put(testing[i], value);
for (int j = i 1; j < test.length(); j ) {
if (testing[i] == testing[j]) {
value = pattern.get(testing[i]);
value = 1;
pattern.replace(testing[i], value);
}
}
orderedList.add(testing[i]);
orderedNumber.add(value);
}
}
This is for the printing part, but as you can see. I have little success in it.
System.out.println(orderedList);
System.out.println(orderedNumber);
int minNumber = 0;
int minIndex = 0;
for (int i = 0; i < orderedList.size(); i ) {
minNumber = pattern.get(orderedList.get(i));
int maxNumber = 0;
for (int j = i 1; j < orderedList.size(); j ) {
if (minNumber > pattern.get(orderedList.get(j))) {
minNumber = pattern.get(orderedList.get(j));
maxNumber = pattern.get(orderedList.get(i));
}
}
System.out.println(minNumber);
}
CodePudding user response：
With your idea of using Map you were on the right track.
Imperative approach
Main steps:
Generate a map of frequencies for each symbol in the given string.
Sort the map entries based on values. Obviously, it's not doable withing a map, we need a different collection for that. We can dump map entries into a
Listand sort it.Print the contents of the list.
That's how it can be implemented:
public static void printFrequencyPattern(String str) {
Map<Character, Integer> frequencies = getFrequencies(str);
List<Map.Entry<Character, Integer>> sortedEntries = toSortedEntryList(frequencies);
for (Map.Entry<Character, Integer> entry: sortedEntries) {
System.out.println(entry.getKey().toString().repeat(entry.getValue()));
}
}
public static Map<Character, Integer> getFrequencies(String str) {
Map<Character, Integer> frequencies = new HashMap<>();
for (int i = 0; i < str.length(); i ) {
frequencies.merge(str.charAt(i), 1, Integer::sum);
}
return frequencies;
}
public static List<Map.Entry<Character, Integer>> toSortedEntryList(Map<Character, Integer> frequencies) {
List<Map.Entry<Character, Integer>> sortedEntries = new ArrayList<>(frequencies.entrySet());
sortedEntries.sort(Map.Entry.comparingByValue());
return sortedEntries;
}
main()
public static void main(String[] args) {
String test = "abbccbdddddddeeeee";
printFrequencyPattern("abbccbdddddddeeeee");
}
Output:
a
cc
bbb
eeeee
ddddddd
Stream-based Solution
In case if you're comfortable with using Stream IPA, here's a one-liner which everything as the code above within a single statement.
The idea behind the code is mostly the same, collector toMap() generates a map of frequencies. Then a stream of its entries gets created and sorted by value of each entry.
str.codePoints()
.boxed()
.collect(Collectors.toMap(
Function.identity(),
ch -> 1,
Integer::sum
))
.entrySet().stream()
.sorted(Map.Entry.comparingByValue())
.forEachOrdered(entry ->
System.out.println(Character.toString(entry.getKey()).repeat(entry.getValue()))
);
CodePudding user response：
Here is one way.
First, create some random data. I wanted there to be the same number of some elements to allow for sorting in lexical order if the counts were equal.
String s = "abbcccddddeeeeffffffggggggg";
List<String> list =
new ArrayList<>(Arrays.stream(s.split("")).toList());
Collections.shuffle(list);
Now define a comparator to use in the sort - first on count, then on lexical key. Doing it outside the stream avoids clutter.
Comparator<Entry<String, Long>> comp = Entry
.<String, Long>comparingByValue()
.thenComparing(Entry.comparingByKey());
Then stream the list and do a frequency count. The key will be the letter and the count will be its frequency of occurrences. Take the resulting entrySet of the map and sort first based on count, then based on lexical order. Then print using the Entry fields.
list.stream()
.collect(Collectors.groupingBy(a -> a,
Collectors.counting()))
.entrySet().stream().sorted(comp)
.forEach(e -> System.out.println(
e.getKey().repeat(e.getValue().intValue())));
prints
a
bb
ccc
dddd
eeee
ffffff
ggggggg
CodePudding user response：
One way you can do this is by storing occurrence number per character in a map and then sort the map. After that you can print the map as your pattern.
You have already stored the occurrences in a map.
// sort the map. You can do it in any way you like
Map<Character, Integer> sortedMap = pattern.entrySet().stream()
.sorted(Map.Entry.comparingByValue())
.collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue,(e1, e2) -> e1, LinkedHashMap::new));
//print the pattern
System.out.println(sortedMap);
for(Character key : sortedMap.keySet()){
for(int i=1; i<= sortedMap.get(key);i ){
System.out.print(key);
}
System.out.println();
}
CodePudding user response：
This is a basic counting sort. You use an array of int to count the occurrence of each character. Then use the array to print them in ascending order. The indices 0-26 map to 'a' to 'z'.
Then use counting sort again to sort by occurrence. This works well only if your string isn't too long.
import java.util.*;
public class Main{
public static void main(String[] args) {
String s = "abbccbddddeeeee";
int[] count = new int[26];
for(char c: s.toCharArray())
count[c-'a'] ;
char[] sort = new char[s.length()];
for(int i=0; i<count.length; i )
sort[count[i]]=(char)(i 'a');
for(int i=0; i<sort.length; i ){
if ('a' <= sort[i] && sort[i] <= 'z'){
for(int j=0; j<i; j )
System.out.print(sort[i]);
System.out.println();
}
}
}
}