Randomized Set Operations — Problem Statement & Solution Guide

HashingMediumHash Map / Dynamic Array

TimeO(m) where m is number of operations

SpaceO(u) where u is number of distinct values

Problem Description

You are given an array of strings ops. Each string is formatted as "type value" where type is either 1 (insert) or 2 (delete) and value is a signed 32‑bit integer. Process the operations sequentially on a multiset that can store duplicate values. An insert adds one occurrence of value; a delete removes one occurrence of value if it exists, otherwise it does nothing. After all operations are applied, return the arithmetic sum of all numbers currently present in the multiset. The sum may be zero if the multiset is empty.

DSA Pattern Breakdown

"Randomized Set Operations"

medium

WHY DOES IT MATTER?

Hash‑based counting is a fundamental pattern for frequency tracking, enabling constant‑time updates in streaming or real‑time systems where latency matters.

OPTIMIZATION CHALLENGE

The key insight is to store only the count per distinct value instead of the entire list of occurrences, collapsing potentially linear‑size data into a compact O(k) structure where k is the number of unique values.

REAL-WORLD CONNECTION

Think of a cache server tracking request counts per key; each hit increments a counter, and stale entries are decremented or evicted—exactly the same hash‑map counting logic.

During coding, always guard the delete path with a check for existence; using map.getOrDefault(value,0) avoids NullPointerExceptions and keeps the code concise.

COMPLEXITY AT A GLANCE

⏱ Time:O(m) where m is number of operations

💾 Space:O(u) where u is number of distinct values

Core Theory — Why This Approach?

In this problem we maintain a dynamic multiset of 32‑bit integers under two operations: insert and delete. A naïve solution would scan a list to count occurrences, leading to O(n) per operation and O(n²) total for large input streams. The optimal paradigm leverages hashing: a hash table (e.g., unordered_map) stores each distinct value as a key and its current multiplicity as the value, allowing both insertion and deletion in expected O(1) time. This approach exploits the constant‑time average performance of hash‑based dictionaries for look‑ups, updates, and deletions, which is essential when the operation count can reach 10⁵ or more.

Interview Questions on This Problem

Q1How would you modify the solution if the delete operation must remove all occurrences of a given value instead of just one?

Simply delete the key from the hash map entirely (or set its count to zero). This still remains O(1) average because hash table removal is constant time.

Q2Can you achieve the same amortized O(1) performance without using a built‑in hash map in a language that only provides arrays?

Yes, by implementing a custom open‑addressing hash table or using a balanced binary search tree with O(log n) operations; however, the constant factors are higher than a native hash map.

Q3What changes are needed if the multiset must also support a "getRandom" operation that returns a random element with probability proportional to its multiplicity?

Maintain an auxiliary dynamic array of all elements (including duplicates) alongside the hash map; on insert push the value, on delete swap‑pop the removed occurrence, and getRandom becomes O(1) by picking a random index.

Examples

Example 1

Input

["1 5","1 3","2 5","1 -2"]

Output

Explanation: Insert 5 → {5}. Insert 3 → {5,3}. Delete 5 → {3}. Insert -2 → {3,-2}. Sum = 3 + (-2) = 1.

Example 2

Input

["2 10","1 10","1 10","2 10","2 10"]

Output

Explanation: Delete 10 does nothing (set empty). Insert 10 twice → {10,10}. Delete 10 removes one occurrence → {10}. Delete 10 removes the remaining one → {}. Sum of empty set is 0.

Example 3

Input

["1 1000000000","1 -1000000000","2 0","1 0"]

Output

Explanation: Insert 1e9 → {1e9}. Insert -1e9 → {1e9,-1e9}. Delete 0 does nothing. Insert 0 → {1e9,-1e9,0}. Sum = 1e9 + (-1e9) + 0 = 0.

Constraints

1 <= ops.length <= 200000
Each ops[i] follows the pattern "type value
type is either 1 or 2
-2^31 <= value <= 2^31-1
The final sum fits in a 64‑bit signed integer

Optimal Approach & Strategy

Use a hash map from value to its frequency; insert increments the count, delete decrements if present, both in O(1) average time.

Brute Force Approach

Store all numbers in a list and on each delete scan the list to find and remove one occurrence, leading to O(n) per operation.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(m) where m is number of operations

/**
 * @param {string[]} ops
 * @return {number}
 */
var processOperations = function(ops) {
    const countMap = new Map();
    let totalElements = 0;
    
    for (const op of ops) {
        // Parse the operation string
        const [typeStr, valueStr] = op.split(' ');
        const type = parseInt(typeStr, 10);
        const value = parseInt(valueStr, 10);
        
        if (type === 1) {
            // Insert: add one occurrence
            countMap.set(value, (countMap.get(value) || 0) + 1);
            totalElements++;
        } else if (type === 2) {
            // Delete: remove one occurrence if it exists
            const currentCount = countMap.get(value) || 0;
            if (currentCount > 0) {
                if (currentCount === 1) {
                    countMap.delete(value);
                } else {
                    countMap.set(value, currentCount - 1);
                }
                totalElements--;
            }
        }
    }
    
    return totalElements;
};

// Driver code for local testing
const ops = ["1 5", "1 3", "2 5", "1 -2"];
console.log(processOperations(ops));

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>

using namespace std;

class Solution {
public:
    int processOperations(vector<string>& ops) {
        unordered_map<int, int> countMap;
        int totalElements = 0;
        
        for (const string& op : ops) {
            // Parse the operation string
            // Format: "type value"
            int spaceIndex = op.find(' ');
            int type = stoi(op.substr(0, spaceIndex));
            int value = stoi(op.substr(spaceIndex + 1));
            
            if (type == 1) {
                // Insert: add one occurrence
                countMap[value]++;
                totalElements++;
            } else if (type == 2) {
                // Delete: remove one occurrence if it exists
                if (countMap.find(value) != countMap.end() && countMap[value] > 0) {
                    countMap[value]--;
                    totalElements--;
                    // Optional: clean up zero counts to keep map small
                    if (countMap[value] == 0) {
                        countMap.erase(value);
                    }
                }
            }
        }
        
        return totalElements;
    }
};

int main() {
    vector<string> ops = {"1 5", "1 3", "2 5", "1 -2"};
    Solution sol;
    cout << sol.processOperations(ops) << endl;
    return 0;
}

import java.util.*;

class Solution {
    public int processOperations(List<String> ops) {
        Map<Integer, Integer> countMap = new HashMap<>();
        int totalElements = 0;
        
        for (String op : ops) {
            // Parse the operation string
            String[] parts = op.split(" ");
            int type = Integer.parseInt(parts[0]);
            int value = Integer.parseInt(parts[1]);
            
            if (type == 1) {
                // Insert: add one occurrence
                countMap.put(value, countMap.getOrDefault(value, 0) + 1);
                totalElements++;
            } else if (type == 2) {
                // Delete: remove one occurrence if it exists
                Integer currentCount = countMap.get(value);
                if (currentCount != null && currentCount > 0) {
                    if (currentCount == 1) {
                        countMap.remove(value);
                    } else {
                        countMap.put(value, currentCount - 1);
                    }
                    totalElements--;
                }
            }
        }
        
        return totalElements;
    }
    
    public static void main(String[] args) {
        List<String> ops = Arrays.asList("1 5", "1 3", "2 5", "1 -2");
        Solution sol = new Solution();
        System.out.println(sol.processOperations(ops));
    }
}

from typing import List

class Solution:
    def processOperations(self, ops: List[str]) -> int:
        count_map = {}
        total_elements = 0
        
        for op in ops:
            # Parse the operation string
            parts = op.split(' ')
            op_type = int(parts[0])
            value = int(parts[1])
            
            if op_type == 1:
                # Insert: add one occurrence
                count_map[value] = count_map.get(value, 0) + 1
                total_elements += 1
            elif op_type == 2:
                # Delete: remove one occurrence if it exists
                if value in count_map and count_map[value] > 0:
                    count_map[value] -= 1
                    total_elements -= 1
                    if count_map[value] == 0:
                        del count_map[value]
        
        return total_elements

# Driver code for local testing
if __name__ == "__main__":
    ops = ["1 5", "1 3", "2 5", "1 -2"]
    sol = Solution()
    print(sol.processOperations(ops))

/**
 * @param {string[]} ops
 * @return {number}
 */
var processOperations = function(ops) {
    const countMap = new Map();
    let totalElements = 0;
    
    for (const op of ops) {
        // Parse the operation string
        const [typeStr, valueStr] = op.split(' ');
        const type = parseInt(typeStr, 10);
        const value = parseInt(valueStr, 10);
        
        if (type === 1) {
            // Insert: add one occurrence
            countMap.set(value, (countMap.get(value) || 0) + 1);
            totalElements++;
        } else if (type === 2) {
            // Delete: remove one occurrence if it exists
            const currentCount = countMap.get(value) || 0;
            if (currentCount > 0) {
                if (currentCount === 1) {
                    countMap.delete(value);
                } else {
                    countMap.set(value, currentCount - 1);
                }
                totalElements--;
            }
        }
    }
    
    return totalElements;
};

// Driver code for local testing
const ops = ["1 5", "1 3", "2 5", "1 -2"];
console.log(processOperations(ops));

Asked in Top Tech Interviews

Razorpay

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.

Randomized Set Operations Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Constraints

More Hashing

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Randomized Set Operations — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Asked in Top Tech Interviews

Solve in Interative Editor