Atlassian Interview Experience : Content Popularity Tracker

Round 1

Questions: Implement a system to track the popularity of content based on user interactions (thumbs up or thumbs down). Your task is to design an interface called ContentPopularity with the following methods:

1. increasePopularity(contentId: int) -> None: Increases the popularity of the specified content ID by one (representing a thumbs up).
2. decreasePopularity(contentId: int) -> None: Decreases the popularity of the specified content ID by one (representing a thumbs down).
3. mostPopular() -> int: Returns the content ID with the highest popularity. If there are ties, return any one of them. -1 if no content.

Solution:

class Node:
    def __init__(self, val=0):
        self.val = val
        self.prev = None
        self.next = None
        self.keys = set() # {content_ids}

class Popularity:
    def __init__(self):
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head
        self.cache = defaultdict(Node) # {content_id: Node}

    def increase_popularity(self, content_id) -> None:
        if content_id in self.cache:
            node = self.cache[content_id]
            val = node.val
            node.keys.remove(content_id)

            nex = node.next
            if nex == self.tail or nex.val != val + 1:
                new_node = Node(val + 1)
                new_node.keys.add(content_id)
                self._insert(new_node, node, nex)
                self.cache[content_id] = new_node
            else:
                nex.keys.add(content_id)
                self.cache[content_id] = nex

            if len(node.keys) == 0:
                self._remove(node)
        else:
            first = self.head.next
            if first == self.tail or first.val > 1:
                new_node = Node(1)
                self._insert(new_node, self.head, first)
                new_node.keys.add(content_id)
                self.cache[content_id] = new_node
            else:
                first.keys.add(content_id)
                self.cache[content_id] = first

    def decrease_popularity(self, content_id) -> None:
        if content_id not in self.cache:
            return

        node = self.cache[content_id]
        prev = node.prev
        nex = node.next
        node.keys.remove(content_id)

        if node.val == 1:
            del self.cache[content_id]
        else:
            if prev is self.head or node.val - 1 != prev.val:
                new = Node(node.val - 1)
                self._insert(new, prev, node)
                new.keys.add(content_id)
                self.cache[content_id] = new
            else:
                prev.keys.add(content_id)
                self.cache[content_id] = prev
        if len(node.keys) == 0:
            self._remove(node)

    def most_popular(self) -> int:
        if self.tail.prev == self.head:
            return -1
        return next(iter(self.tail.prev.keys))

    def _remove(self, node):
        prev = node.prev
        nex = node.next
        prev.next = nex
        nex.prev = prev

    def _insert(self, node, prev, nex):
        node.prev = prev
        node.next = nex
        prev.next = node
        nex.prev = node

popularity = Popularity()
print(popularity.most_popular())
print(popularity.increase_popularity(3))
print(popularity.most_popular())
print(popularity.decrease_popularity(3))
print(popularity.most_popular())
print(popularity.increase_popularity(4))
print(popularity.increase_popularity(4))
print(popularity.most_popular())
print(popularity.decrease_popularity(3))
print(popularity.decrease_popularity(3))
print(popularity.decrease_popularity(3))
print(popularity.most_popular())