Find the nearest repeated entries in an array
NearestRepetition.javapublic static int findNearestRepetition(List<String> s) {
Map<String, Integer> stringToLocation = new HashMap<>();
int closestDis = Integer.MAX_VALUE;
for (int i = 0; i < s.size(); ++i) {
if (stringToLocation.containsKey(s.get(i))) {
closestDis = Math.min(closestDis, i - stringToLocation.get(s.get(i)));
}
stringToLocation.put(s.get(i), i);
}
return closestDis;
}
Find the longest subarray with distinct entries
LongestSubarrayWithDistinctEntries.javapublic static int longestSubarrayWithDistinctEntries(List<Integer> A) {
// Records the last occurrences of each entry.
Map<Integer, Integer> lastOccurrence = new HashMap<>();
int startingIdx = 0, ans = 0;
for (int i = 0; i < A.size(); ++i) {
Integer result = lastOccurrence.put(A.get(i), i);
if (result != null) { // A[i] appeared before. Check its validity.
if (result >= startingIdx) {
ans = Math.max(ans, i - startingIdx);
startingIdx = result + 1;
}
}
}
ans = Math.max(ans, A.size() - startingIdx);
return ans;
}
Compute all string decompositions SubstringWithConcatenationOfAllWords.java
public static List<Integer>
findAllSubstrings(String s, List<String> words) {
Map<String, Integer> dict = new HashMap<>();
for (String word : words) {
increment(word, dict);
}
int unitSize = words.get(0).length();
List<Integer> result = new ArrayList<>();
for (int i = 0; i + unitSize * words.size() <= s.length(); ++i) {
if (matchAllWordsInDict(s, dict, i, words.size(), unitSize)) {
result.add(i);
}
}
return result;
}
private static boolean
matchAllWordsInDict(String s,
Map<String, Integer> dict,
int start, int numWords, int unitSize) {
Map<String, Integer> currDict = new HashMap<>();
for (int i = 0; i < numWords; ++i) {
String currWord = s.substring(start + i * unitSize, start + (i + 1)
* unitSize);
Integer iter = dict.get(currWord);
if (iter == null) {
return false;
}
increment(currWord, currDict);
if (currDict.get(currWord) > iter) {
return false;
}
}
return true;
}
private static void increment(String word, Map<String, Integer> dict) {
Integer count = dict.get(word);
if (count == null) {
count = 0;
}
count++;
dict.put(word, count);
}
Find a highest affinity pair HighestAffinityPairs.java
public static Pair<String, String> highestAffinityPair(InputStream ifs) {
// Creates a mapping from pages to distinct users.
Map<String, Set<String>> pageUsersMap = new HashMap<>();
try {
ObjectInputStream ois = new ObjectInputStream(ifs);
while (true) {
String page = ois.readUTF();
String user = ois.readUTF();
Set<String> users = pageUsersMap.get(page);
if (users == null) {
users = new HashSet<>();
}
users.add(user);
pageUsersMap.put(page, users);
}
} catch (IOException e) {
}
Pair<String, String> result = null;
int maxCount = 0;
// Compares all pairs of pages to users maps.
List<String> keys = new ArrayList<>(pageUsersMap.keySet());
for (int i = 0; i < keys.size(); i++) {
for (int j = i + 1; j < keys.size(); ++j) {
Set<String> intersectUsers =
new HashSet<>(pageUsersMap.get(keys.get(i)));
intersectUsers.retainAll(pageUsersMap.get(keys.get(j)));
// Updates result if we find larger intersection.
if (intersectUsers.size() > maxCount) {
maxCount = intersectUsers.size();
result = new Pair<>(keys.get(i), keys.get(j));
}
}
}
return result;
}
