passenger
BAN USERO(2^N) time and space:
private LinkedList<StringBuilder> getInOrderCombs(int[] arr, int i) {
// Recursion base case.
if (i == 0) {
LinkedList<StringBuilder> baseResult = new LinkedList<>();
baseResult.add(new StringBuilder("(").append(arr[i]).append(")"));
return baseResult;
}
List<StringBuilder> list = new LinkedList<>();
// Get previous result.
LinkedList<StringBuilder> result = getInOrderCombs(arr, i - 1);
for (StringBuilder sb : result) {
// Copy each result and add current element with parens (use a separate list for that).
list.add(new StringBuilder(sb).append("(").append(arr[i]).append(")"));
// Append the current element (inside the parens) to each result.
sb.insert(sb.length() - 1, arr[i]);
}
result.addAll(list);
// At the end remove the first element because it's not a combination.
if (i == arr.length - 1) {
result.removeFirst();
}
return result;
}
Call example: getInOrderCombs(new int[]{1, 2, 3, 4}, 3);
O(Nlogk) time, O(N) space
private class Entry {
private String username;
private int count;
private boolean inHeap;
private Entry(String username) {
this.username = username;
}
@Override
public String toString() {
return username + "(" + count + ")";
}
}
private static final Comparator<Entry> MIN_COMPARATOR = new Comparator<Entry>() {
@Override
public int compare(Entry o1, Entry o2) {
return o1.count - o2.count;
}
};
private static final Comparator<Entry> MAX_COMPARATOR = new Comparator<Entry>() {
@Override
public int compare(Entry o1, Entry o2) {
return o2.count - o1.count;
}
};
private List<String> getMaxUsernames(String str, int k) {
String[] users = str.split(",");
Map<String, Entry> map = new HashMap<>();
PriorityQueue<Entry> minHeap = new PriorityQueue<>(k, MIN_COMPARATOR);
for (String user : users) {
Entry entry = map.get(user);
if (entry == null) {
entry = new Entry(user);
map.put(user, entry);
}
entry.count++;
if (minHeap.size() < k) {
minHeap.add(entry);
entry.inHeap = true;
} else if (entry.inHeap) {
minHeap.remove(entry);
minHeap.add(entry);
} else if (entry.count > minHeap.peek().count) {
minHeap.poll().inHeap = false;
minHeap.add(entry);
entry.inHeap = true;
}
}
// Include usernames with the same count but use a binary heap here in order to to sort the results as well.
int min = minHeap.peek().count;
PriorityQueue<Entry> maxHeap = new PriorityQueue<>(k, MAX_COMPARATOR);
for (Map.Entry<String, Entry> e: map.entrySet()) {
if (e.getValue().count >= min) {
maxHeap.add(e.getValue());
}
}
List<String> result = new ArrayList<>();
while (!maxHeap.isEmpty()) {
result.add(maxHeap.poll().toString());
}
return result;
}
}
The best solution is logarithmic (the trivial one is linear).
My solution:
1. First I'd like to generalize the task a bit: Find all the numbers that occur more than n/k times (in the example, more than n/4 times)
2. Let's split the array on k*2 segments (in the example on 4*2 = 8 segments)
3. Compare every segment's start and end values. If they are equal, it means that we have a potential candidate (that occurs more than n/k times).
3.1 Now we need to find the beginning of the candidate. To do that take the previous segment and do a binary search in it.
3.2 Once we find a beginning of our candidate, time to check if its length is more than n/k. Just add a length (n/k) to the start position and check the value at the end. If the values are equal, then we have a solution and can add it to the result set.
Below is the sketch of my solution in Java. Its complexity is the following:
2k * log(n/2k) = k*log(n) - k*log(k), if we assume that k is relatively small or constant, the complexity becomes log(n).
- passenger March 25, 2017