Randomized Set Operations — Problem Statement & Solution Guide
Problem Description
Implement a data structure that supports insertion and deletion operations and calculates the total value after all operations are performed. The operations are represented as a string array where '1 val' indicates an insertion of value val and '2 val' indicates a deletion of value val.
Examples
Input
['1 1', '2 1', '1 3']
Output
4
Explanation: Step-by-step: 1. Insert 1: total value = 1. 2. Delete 1: total value = 0. 3. Insert 3: total value = 3. 4. Insert 1: total value = 4.
Input
['1 1', '1 2', '2 1']
Output
2
Explanation: Step-by-step: 1. Insert 1: total value = 1. 2. Insert 2: total value = 3. 3. Delete 1: total value = 2.
Constraints
- 1 <= ops <= 10^5
- -10^9 <= val <= 10^9
Optimal Approach & Strategy
HashMap + Array. To remove element E at index I, swap E with last element in array. Update last element's index in HashMap to I. Pop from array and remove E from map. Time O(1).
Brute Force Approach
Use an array and linear search for removal. Time O(N) per remove.
Verified Code Solutions
function RandomizedSet() { let set = new Set(); let total = 0; return { insert: function(val) { if (!set.has(val)) { set.add(val); total += val; } }, remove: function(val) { if (set.has(val)) { set.delete(val); total -= val; } }, getTotal: function() { return total; } }; }
// To handle duplicates, we can throw an error when trying to insert a duplicate value.
function RandomizedSet() { let set = new Set(); let total = 0; return { insert: function(val) { if (set.has(val)) { throw new Error('Cannot insert duplicate value'); } set.add(val); total += val; }, remove: function(val) { if (set.has(val)) { set.delete(val); total -= val; } }, getTotal: function() { return total; } }; }class Solution {
public int solution(String[] operations) {
int total_value = 0;
Set<Integer> values = new HashSet<>();
for (String op : operations) {
int val = Integer.parseInt(op.split(' ')[1]);
if (op.split(' ')[0].equals("1")) {
values.add(val);
total_value += val;
} else {
if (values.contains(val)) {
total_value -= val;
values.remove(val);
}
}
}
return total_value;
}
}def solution(operations):
total_value = 0
values = set()
for op in operations:
val = int(op.split(' ')[1])
if op.split(' ')[0] == '1':
values.add(val)
total_value += val
else:
if val in values:
total_value -= val
values.remove(val)
return total_valuefunction RandomizedSet() { let set = new Set(); let total = 0; return { insert: function(val) { if (!set.has(val)) { set.add(val); total += val; } }, remove: function(val) { if (set.has(val)) { set.delete(val); total -= val; } }, getTotal: function() { return total; } }; }
// To handle duplicates, we can throw an error when trying to insert a duplicate value.
function RandomizedSet() { let set = new Set(); let total = 0; return { insert: function(val) { if (set.has(val)) { throw new Error('Cannot insert duplicate value'); } set.add(val); total += val; }, remove: function(val) { if (set.has(val)) { set.delete(val); total -= val; } }, getTotal: function() { return total; } }; }Asked in Top Tech Interviews
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.