Lumberjack
BAN USERpublic static void printMaximumOccuringCharacter(String str) {
//Since the input string only contains ASCII characters, create an int array of length 256
int[] chars = new int[256];
//For each character in the string, increment the value that's in the position of the character's integer value
for (int i = 0; i < str.length(); i++) {
char ch = str.charAt(i);
chars[ch]++;
}
int maxPos = 0;
for (int i = 0; i < chars.length; i++) {
if (chars[i] > chars[maxPos]) {
maxPos = i;
}
}
//The maximum frequency
int maxFreq = chars[maxPos];
for (int i = 0; i < str.length(); i++) {
char ch = str.charAt(i);
if (chars[ch] == maxFreq) {
System.out.println(ch);
break;
}
}
}
- Lumberjack September 06, 2014import java.util.LinkedHashSet;
import java.util.Set;
public class Permutation {
public static void main(String[] args) {
String a = "abc";
for (String s : all_perm(a)) {
System.out.println(s);
}
}
public static Set<String> concat(String c, Set<String> lst) {
Set<String> ret_set = new LinkedHashSet<String>();
for (String s : lst) {
ret_set.add(s + c);
}
return ret_set;
}
public static Set<String> all_perm(String a) {
Set<String> set = new LinkedHashSet<String>();
if (a.length() == 1) {
set.add(a);
} else {
for (int i = 0; i < a.length(); i++) {
set.addAll(concat(a.charAt(i) + "", all_perm(a.substring(0, i)
+ a.substring(i + 1, a.length()))));
}
}
return set;
}
}
import java.util.*;
public class SortAnagramsNext {
public static List<String> sortWithAnagramsTogether(List<String> elements) {
List<String> sortedElements = sort(elements);
Map<String, List<String>> anagramMap = new LinkedHashMap<String, List<String>>();
for (String element : sortedElements) {
String sortedElement = sortChars(element);
if (anagramMap.get(sortedElement) == null) {
anagramMap.put(sortedElement, new ArrayList<String>());
}
anagramMap.get(sortedElement).add(element);
}
Map<String, List<String>> tmpMap = new LinkedHashMap<String, List<String>>();
for (String key : anagramMap.keySet()) {
tmpMap.put(anagramMap.get(key).get(0), anagramMap.get(key));
}
anagramMap = tmpMap;
List<String> sortedWithAnagrams = new ArrayList<String>();
List<String> mapKeys = new ArrayList<String>(anagramMap.keySet());
Collections.sort(mapKeys);
for (String mapKey : mapKeys) {
for (String element : anagramMap.get(mapKey)) {
sortedWithAnagrams.add(element);
}
}
return sortedWithAnagrams;
}
public static String sortChars(String str) {
char[] strChars = str.toCharArray();
Arrays.sort(strChars);
return String.valueOf(strChars);
}
public static List<String> sort(List<String> elements) {
List<String> sortedElements = new ArrayList<String>(elements);
Collections.sort(sortedElements);
return sortedElements;
}
public static void main(String[] args) {
List<String> elements = Arrays.asList("god", "dog", "abc", "cab", "man");
List<String> sortedElements = sortWithAnagramsTogether(elements);
System.out.println(sortedElements);
}
}
1. collapse all the spaces in the first array starting from the end (two indices needed to keep track of start and end of the continuous free space) - takes O(n) time.
2. merge two arrays - takes O(n) time.
Initially, the top 10 products should be calculated on the first pass. Then several threads may be started to check if any product has now a rating greater than the 10th popular product. If yes, then it should pass it to a synchronized method to update the top 10 popular products. I think this will handle real-time rating updates of a large number of products.
- Lumberjack May 12, 2011
Brute force approach would be to check for all possible outcomes. If there are n numbers, they could be combined in n! different ways. Now, we can sort these n! numbers in n!*log(n!) time using comparison based sorting. This probably isn't good enough for even a decent number of numbers. We need to find a better approach.
- Lumberjack November 21, 2015