Meta Interview Coding Question: Multiset Implementation and Kth Largest Element

A multiset (also known as a bag) is a mutable, unordered collection of distinct objects that may appear more than once in the collection.

Implement a multiset that implements the following methods:

• add(element)
• remove(element)
• count(element)

Given an integer array and an integer k, return the kth largest element in the array.

Examples:

array = [5, -3, 9, 1]
k = 0 => return: 9
k = 1 => return: 5
k = 3 => return: -3

This problem combines two core interview skills: maintaining a multiset with a hash map for efficient add, remove, and count operations, and finding the kth largest element in an integer array. The examples show that k is zero-based, so k = 0 means the maximum element. A straightforward solution is sorting, while more optimized approaches use a heap or quickselect for the kth largest query. If repeated multiset operations are required, a frequency map is the key data structure.