Missing Test Case - 380. Insert Delete GetRandom O(1) #19455
Description
LeetCode Username
tredsused70
Problem number, title, and link
- Insert Delete GetRandom O(1) https://leetcode.com/problems/insert-delete-getrandom-o1/
Category of the bug
- [.] Missing test Case (Incorrect/Inefficient Code getting accepted because of missing test cases)
Description of the bug
Code that uses unordered_map when number of insertions can be up to 2e5 and max value of numbers that are being inserted is 2^31 - 1 getting "Accepted" verdict.
Language used for code
C++
Code used for Submit/Run operation
class RandomizedSet {
public:
unordered_map<int, bool> ump;
unordered_map<int, bool>::iterator it;
RandomizedSet() {
ump.clear();
}
bool insert(int val) {
if(ump.find(val) != ump.end())
return 0;
ump[val] = 1;
if(ump.size() == 1)
it = ump.begin();
return 1;
}
bool remove(int val) {
if(ump.find(val) == ump.end())
return 0;
ump.erase(val);
if(ump.size() == 0)
it = ump.end();
else
it = ump.begin();
return 1;
}
int getRandom() {
for(int i = rand() % 5 % 3; i >= 0; i--) {
it++;
if(it == ump.end())
it = ump.begin();
}
return it -> first;
}
};
/**
* Your RandomizedSet object will be instantiated and called as such:
* RandomizedSet* obj = new RandomizedSet();
* bool param_1 = obj->insert(val);
* bool param_2 = obj->remove(val);
* int param_3 = obj->getRandom();
*/
Expected behavior
Unordered map is implemented in such way that there exist some sets of numbers, which are causing a lot of collisions when inserted into unordered_map, so it rebuilds very often, which causes TLE, as the complexity becomes O(n^2). The test below is one of these sets, the code gets TLE on this test when used in "Run" operation. The code gets "Accepted" verdict when submitted, using only 200ms.
Screenshots
Additional context
Here is the test:
test.txt
Also this code doesn't really return random element, instead it uses formula with rand() to change iterator, and still gets "Accepted" verdict.