Interview Question
Software Engineer / Developers<pre lang="" line="1" title="CodeMonkey54215" class="run-this">public class ReorderWordListInAppearingFrequncy {
public static String[] doIt(String[] input) {
HashMap<String, Integer> strToFreqMap = new HashMap<String, Integer>();
for (String word : input) {
Integer freq = strToFreqMap.get(word);
if (freq == null) {
strToFreqMap.put(word, 1);
} else {
strToFreqMap.put(word, freq + 1);
}
}
TreeMap<Integer, TreeSet<String>> freqToWordMap = new TreeMap<Integer, TreeSet<String>>();
for (String word : input) {
Integer freq = strToFreqMap.get(word);
TreeSet<String> sameFreqWordSet = freqToWordMap
.get(Integer.MAX_VALUE - freq);
if (sameFreqWordSet == null) {
TreeSet<String> newSet = new TreeSet<String>();
newSet.add(word);
freqToWordMap.put(Integer.MAX_VALUE - freq, newSet);
} else {
sameFreqWordSet.add(word);
}
}
ArrayList<String> result = new ArrayList<String>();
Integer[] freqs = new Integer[freqToWordMap.size()];
for (Integer freq : freqToWordMap.keySet().toArray(freqs)) {
TreeSet<String> wordSet = freqToWordMap.get(freq);
for (String word : wordSet) {
for (int i = Integer.MAX_VALUE - freq - 1; i >= 0; --i) {
result.add(word);
}
}
}
return result.toArray(new String[result.size()]);
}
public static void main(String[] args) {
String[] input = { "Dog", "Amar", "Abhishek", "Abhishek", "Amar",
"Abhishek", "Amar", "Boy", "Ball", "Dog" };
String[] expectedOutput = { "Abhishek", "Abhishek", "Abhishek", "Amar",
"Amar", "Amar", "Dog", "Dog", "Ball", "Boy" };
String[] result = doIt(input);
assert Arrays.equals(expectedOutput, result);
System.out.println(Arrays.toString(result));
}
}</pre>
<pre lang="" line="1" title="CodeMonkey78766" class="run-this">public class ReorderWordListInAppearingFrequncy {
- Anonymous April 25, 2011public static String[] doIt(String[] input) {
HashMap<String, Integer> strToFreqMap = new HashMap<String, Integer>();
for (String s : input) {
Integer f = strToFreqMap.get(s);
if (f == null) {
strToFreqMap.put(s, 1);
} else {
strToFreqMap.put(s, f + 1);
}
}
TreeMap<Integer, TreeSet<String>> freqToWordMap = new TreeMap<Integer, TreeSet<String>>();
String[] words = new String[strToFreqMap.size()];
for (String word : strToFreqMap.keySet().toArray(words)) {
Integer freq = strToFreqMap.get(word);
TreeSet<String> sameFreqWordSet = freqToWordMap
.get(Integer.MAX_VALUE - freq);
if (sameFreqWordSet == null) {
TreeSet<String> newSet = new TreeSet<String>();
newSet.add(word);
freqToWordMap.put(Integer.MAX_VALUE - freq, newSet);
} else {
sameFreqWordSet.add(word);
}
}
ArrayList<String> result = new ArrayList<String>();
Integer[] freqs = new Integer[freqToWordMap.size()];
for (Integer freq : freqToWordMap.keySet().toArray(freqs)) {
TreeSet<String> wordSet = freqToWordMap.get(freq);
for (String word : wordSet) {
for (int i = Integer.MAX_VALUE - freq - 1; i >= 0; --i) {
result.add(word);
}
}
}
return result.toArray(new String[result.size()]);
}
public static void main(String[] args) {
String[] input = { "Dog", "Amar", "Abhishek", "Abhishek", "Amar",
"Abhishek", "Amar", "Boy", "Ball", "Dog" };
String[] expectedOutput = { "Abhishek", "Abhishek", "Abhishek", "Amar",
"Amar", "Amar", "Dog", "Dog", "Ball", "Boy" };
System.out.println(Arrays.toString(doIt(input)));
assert Arrays.equals(expectedOutput, doIt(input));
}
}</pre>