ArticleVoteService

import java.util.*;

public class ArticleVoteService {

    class Bucket {
        int score;
        Set<Integer> articles = new HashSet<>();

        Bucket prev;
        Bucket next;

        Bucket(int score) {
            this.score = score;
        }
    }

    private int nextArticleId = 1;

    private Map<Integer, String> articles = new HashMap<>();

    // articleId -> current score
    private Map<Integer, Integer> articleScores = new HashMap<>();

    // score -> bucket
    private Map<Integer, Bucket> buckets = new HashMap<>();

    // user -> (article -> vote)
    private Map<Integer, Map<Integer, Integer>> userVotes = new HashMap<>();

    // bucket linked list
    private Bucket head;
    private Bucket tail;

    public int addArticle(String title) {
        int id = nextArticleId++;
        articles.put(id, title);
        articleScores.put(id, 0);

        addToBucket(id, 0);

        return id;
    }

    public void upvoteArticle(int articleId, int userId) {
        vote(articleId, userId, 1);
    }

    public void downvoteArticle(int articleId, int userId) {
        vote(articleId, userId, -1);
    }

    private void vote(int articleId, int userId, int newVote) {

        userVotes.putIfAbsent(userId, new HashMap<>());

        Map<Integer, Integer> voteMap = userVotes.get(userId);

        Integer oldVote = voteMap.get(articleId);

        int oldVoteValue = oldVote == null ? 0 : oldVote;

        if (oldVoteValue == newVote) {
            return;
        }

        int delta = newVote - oldVoteValue;

        int oldScore = articleScores.get(articleId);
        int newScore = oldScore + delta;

        moveArticle(articleId, oldScore, newScore);

        articleScores.put(articleId, newScore);

        voteMap.put(articleId, newVote);
    }

    private void moveArticle(int articleId, int oldScore, int newScore) {

        Bucket oldBucket = buckets.get(oldScore);

        oldBucket.articles.remove(articleId);

        if (oldBucket.articles.isEmpty()) {
            removeBucket(oldBucket);
            buckets.remove(oldScore);
        }

        addToBucket(articleId, newScore);
    }

    private void addToBucket(int articleId, int score) {

        Bucket bucket = buckets.get(score);

        if (bucket == null) {

            bucket = new Bucket(score);

            buckets.put(score, bucket);

            insertBucket(bucket);
        }

        bucket.articles.add(articleId);
    }

    // keep linked list sorted by score
    private void insertBucket(Bucket bucket) {

        if (head == null) {
            head = tail = bucket;
            return;
        }

        Bucket curr = head;

        while (curr != null && curr.score < bucket.score) {
            curr = curr.next;
        }

        // insert at tail
        if (curr == null) {
            tail.next = bucket;
            bucket.prev = tail;
            tail = bucket;
        }
        // insert at head
        else if (curr == head) {
            bucket.next = head;
            head.prev = bucket;
            head = bucket;
        }
        // insert middle
        else {
            Bucket prev = curr.prev;

            prev.next = bucket;
            bucket.prev = prev;

            bucket.next = curr;
            curr.prev = bucket;
        }
    }

    private void removeBucket(Bucket bucket) {

        if (bucket.prev != null) {
            bucket.prev.next = bucket.next;
        } else {
            head = bucket.next;
        }

        if (bucket.next != null) {
            bucket.next.prev = bucket.prev;
        } else {
            tail = bucket.prev;
        }
    }

    // O(k)
    public List<String> getTopK(int k) {

        List<String> result = new ArrayList<>();

        Bucket curr = tail;

        while (curr != null && result.size() < k) {

            for (int articleId : curr.articles) {

                result.add(articles.get(articleId));

                if (result.size() == k) {
                    return result;
                }
            }

            curr = curr.prev;
        }

        return result;
    }
}