Sliding Window Frequency Queries - Nutanix Online Assessment MNNIT Allahabad

Problem Preview

"Design a data stream processor that maintains a sliding window of the last `N` elements and can answer queries about the most frequent element in the current window and elements that appear exactly twice in the current window. The processor receives a stream of operations. Elements are added to the window, and queries can be made on the current contents of the window. The supported operations are: * **`ADD element`** – Add an element to the current window. If the window size exceeds `N`, remove the oldest element from the window. * **`MOST_FREQUENT`** – Return the element with the highest frequency in the current window. If multiple elements have the same frequency, return the lexicographically smallest element. * **`EXACTLY_TWICE`** – Return all elements that appear exactly twice in the current window, sorted lexicographically. --- ## Example 1 ### Input ```text 4 9 ADD A ADD B ADD A MOST_FREQUENT EXACTLY_TWICE ADD C ADD A MOST_FREQUENT EXACTLY_TWICE ``` ### Output ```text A A A A C ``` ### Explanation After adding `A`, `B`, and `A`, the current window is: ```text [A, B, A] ``` The element `A` appears twice, making it the most frequent element and the only element that appears exactly twice. After adding `C` and then `A`, the window shifts and the oldest elements are removed. The current window becomes: ```text [A, C, A, C] ``` The most frequent elements and the elements appearing exactly twice are both `A` and `C`. Since `A` is lexicographically smaller, the `MOST_FREQUENT` query returns `A`, while `EXACTLY_TWICE` returns: ```text A C ``` --- ## Input Format * Line 1: Integer `N` — the size of the sliding window. * Line 2: Integer `Q` — the number of operations. * The next `Q` lines each contain one operation: * `ADD x` * `MOST_FREQUENT` * `EXACTLY_TWICE` --- ## Output Format Return a string array containing the outputs of all query operations (`MOST_FREQUENT` and `EXACTLY_TWICE`) in the order they appear. For `EXACTLY_TWICE`, output all qualifying strings in lexicographical order separated by a single space. --- ## Constraints * `1 ≤ N ≤ 100000` * `1 ≤ Q ≤ 200000` * `1 ≤ length(element) ≤ 20` * Elements contain English letters only. * The total number of characters in the expected output will not exceed `10^6`. --- ## Sample Case 0 ### Sample Input 0 ```text 4 9 ADD A ADD B ADD A MOST_FREQUENT EXACTLY_TWICE ADD C ADD A MOST_FREQUENT EXACTLY_TWICE ``` ### Sample Output 0 ```text A A A A C ``` --- ## Function Signature ```cpp vector<string> processOperations(int window_size, vector<string> operations) ``` ### Return Return a `vector<string>` containing the answers to all query operations in the order they occur."