ak
BAN USERint main()
{
// Generate the first n numbers
const int n = 20;
std::vector<int> v(n);
v[0] = 1;
int i2 = 0; // Index for 2
int i5 = 0; // Index for 5
// Next two candidates
int x2 = 2 * v[i2];
int x5 = 5 * v[i5];
for (int i = 1; i != n; ++i)
{
int m = std::min(x2, x5);
std::cout << m << " ";
v[i] = m;
if (x2 == m)
{
++i2;
x2 = 2 * v[i2];
}
if (x5 == m)
{
++i5;
x5 = 5 * v[i5];
}
}
std::cout << std::endl;
return 0;
}
Yes. We can implement it with hash Table. So that Insert and delete could be in O(1).
For getRandomElement() we can use Doubly linked list, where we can store the number present in the set.
Hash table should have the <key,value> as <number, pointer to the node in DLL>. So in insert() and remove() also we insert and remove node from the DLL.
To Get the Random Element, We just generate Random number between 1 to num_element (say R) and fetch the Rth element from the DLL.
The problem here is how will you get the frequency of words without keep all the 200Gb data into the memory in one time.
- ak May 20, 2014