jaks
BAN USERUse HashMap<Friend, Frequency & Index in MinHeap > & MinHeap<Friend with Frequency>. MinHeap has size k. Whenever a friend has more frequency, update the count in hashmap. Then check the count with top of minheap. If count is more than minheap's top, remove top item and insert the new friend. Whenever you do heapify, maintain the index in hashmap. If existing friend's frequency is increased, increase it using heap-increase-key.
- jaks September 20, 2016Above solutions are not O(n). The optimal runtime is O(n logn). Here min heap is used to store the departure times.
public static int find(int[] arr, int[] dep) {
Heap heap = new MinHeap(arr.length);
int gates = 1;
heap.add(dep[0]);
for (int i = 1; i < dep.length; i++) {
if (arr[i] < heap.peek()) {
gates++;
} else {
heap.extractTop();
}
heap.add(dep[i]);
}
return gates;
}
public class BaloonShooting {
public static int findScore(List<Integer> weightages) {
int score = 0;
if (weightages.size() == 0)
return 0;
else if (weightages.size() == 1) {
return weightages.get(0);
} else if (weightages.size() == 2) {
int a = weightages.get(0);
int b = weightages.get(1);
if (a > b)
return (b + 1) * a;
else
return (a + 1) * b;
} else if (weightages.size() == 3) {
score = weightages.get(0) * weightages.get(1) * weightages.get(2);
weightages.remove(1);
return score + findScore(weightages);
} else {
int index = 0;
for (int i = 1; i < 3 && i < weightages.size() - 1; i++) {
int current = weightages.get(i - 1) * weightages.get(i) * weightages.get(i + 1);
if (current > score) {
score = current;
index = i;
}
}
// Shoot the baloon
weightages.remove(index);
return score + findScore(weightages);
}
}
}
I thought the question was about to choose the best data structure. Recommendation can be done in many factors. e.g. A has friends (B,C,D)
- jaks September 21, 2016B -> E, C->E, D->F. Get the friends who are also friends with more than one friend (E). So with hashmap, you can have the count. If there is a tie, choose the oldest friend.