Top K Elements veya Top K Frequent Elements - System Design Sorusu Olabilir

Giriş
Top K Element algoritmaları bana en uzun, en kısa en X ölçütüne uyan ilk K elemanı ver anlamına gelir. Algoritma kabaca şöyle. Yani önce elemanları bir ölçüte göre sayıyoruz ve daha sonra bunları bir minheap veri yapısına ekleyip, Top K elemanı buluyoruz.

1. We first go through the array and count each element’s frequency, creating a distribution map.

2. We then go through the key-value pairs in the distribution map, and maintain a min-heap of size k based on frequency.

Dağıtık (Distributed) Top K

Burada MapReduce kullanmak gerekiyor. Bu algoritmanın biraz daha gelişmiş hali "Top K Frequent Elements in a Time Window"

Top K Değerini Bilmiyorsak

Eğer en uzun elemanların tamamını ver deseydi, Top K eleman algoritmaları kullanılamaz çünkü, ölçütü sağlayan kaç tane nesne olduğunu bilmiyoruz.

Top K Elements Çözümleri

Bu algoritmaların bir çok çözümü var

Örnek - Listeyi Dolaşarak PriorityQueue İle Sıralamak

En uzun 2 string'i bulmak isteyelim. Şöyle yaparız. 

int topK = 2;
PriorityQueue<String> pq = new PriorityQueue<>(String::length);

for (String word : wordList){
  pq.offer(word);
  if (pq.size() > topK){
    pq.poll(); //En kısayı sil
  }
}

while (!pq.isEmpty()){
 pq.remove(); 
}

Örnek - Tree'yi Dolaşarak PriorityQueue İle Sıralamak

Şöyle yaparız

public List<Integer> closestKValues(TreeNode root, double target, int k) {
  // 1. Create a Priority Queue, sorted on diffs
  PriorityQueue<double[]> pq = new PriorityQueue<double[]>(
    Comparator.comparing(a -> a[1]));
  Stack<TreeNode> stack = new Stack<>();
        
  stack.push(root);
        
  // 2. Traverse tree iteratively and place items in PQ
  while (!stack.isEmpty()) {
    TreeNode current = stack.pop();
            
    pq.add(new double[] {current.val /* value */,
      Math.abs(current.val - target /* diff */ )});
            
    if (current.left != null) {
      stack.push(current.left);
    }
            
    if (current.right != null) {
      stack.push(current.right);
    }        
  }
        
  // 3. Prepare the output with needed K-values.
  List<Integer> result = new ArrayList<>();
        
  for (int i = 0; i < k; ++i) {
    if (!pq.isEmpty()) {
      result.add((int) pq.poll()[0]);
    }
  }
  return result;
}

Örnek - Girdi Olan Dizi Sıralı Olmalı

En yüksek frekans (frequency) değerine sahip K elementi bulmak isteyelim. Dizi sıralı olduğu için şöyle yaparız. process() metodu her değerden kaç tane olduğunu bulur ve addOrReplace() metodunu çağırır. countMap içinde Top K Elements sırasız biçimde bulunur

class TopN {
  private final int maxSize;
  private Map<Long, Long> countMap;

  public TopN(int maxSize) {
    this.maxSize = maxSize;
    this.countMap = new HashMap(maxSize);
  }

  private void addOrReplace(long value, long count) {
    if (countMap.size() < maxSize) {
      countMap.put(value, count);
    } else { //Top K sınırına geldik
      Optional<Entry<Long, Long>> opt = countMap.entrySet().stream()
        .min(Entry.comparingByValue()); //En küçük frekansa sahip elemanı bul
      Entry<Long, Long> minEntry = opt.get();
      if (minEntry.getValue() < count) { //Eğer mevcut frekans daha küçükse, sil
        countMap.remove(minEntry.getKey());
        countMap.put(value, count);
      }
    }
  }
  public void process(long[] data) {
    long value = data[0];
    long count = 0;
    for (long current : data) {
      if (current == value) {
        ++count;
      } else {
        addOrReplace(value, count);
        value = current;
        count = 1;
      }
    }
    addOrReplace(value, count);
  }
}