Amazon Interview Question
SDE-2sCountry: India
Interview Type: In-Person
take an array, a, of size=10
initialize array to 0;
now whenever u enter a number, check if a[num]==1, if not then enter the number in the queue and put a[num]=1, else check the next number.
deletion operation can be done normally!
For eg:Assume the input of 8 elements is coming from array and n is 6
#include<unordered_map>
#include<iostream>
using namespace std;
int a[8]={3,8,12,9,-1,2,1,0};
int main()
{
int i=0;
unordered_map<int ,int> s;
while(i<8)
{
if(i>5)
{
s.erase(i%6);
}
s.insert(pair<int ,int >(i,a[i]));
i++;
}
for(auto d=s.begin();d!=s.end();++d)
{
cout<<d->first<<"\t"<<d->second<<"\n";
}
}
Here's one possibility:
We need to maintain the following ensemble of structures:
1. Queue: it stores all the elements that are unique as per their order of arrivals.
2. Hash_Counter: it maintains the total number of elements received so far, including the duplicates.
3. Hash_Table[Value]=Frequencies.
Then we can implement the following (pseudo code):
for every new element, value, do
{
if(Hash_Counter +1 != n)
{
Hash_Counter++;
if(Hash_Table[value]==0)
addQ(value);
Hash_Table[value]++;
}
else // once we are at this point, we don't need to manipulate the Hash_Counter anymore as it will equal n. In other words, we remove the first inserted and then add the new value, hence the counter remains constant
{
v=DeleteQ();
Hash_Table[v]--;
if(Hash_Table[value]==0)
addQ(value);
hash_Table[value]++;
}
}
Queue insertion and deletion is O(1). Hash table insertion, key increase, and key decrease is also O(1). Furthermore, searching a new value can be done in O(1) since we are using the actual values as keys to insert them to the hash table. However, space requirement is an issue particularly if these values are coming from a very broad range.
Implement your own doubly linked list. Use this as a queue with elements in front as oldest and elements at back as newest.
- MK August 11, 2013Then implement your own data structure which contains the list as a member variable. It also contains a hashmap with key as integer and value as pointer to node in the list.
To insert, simply check in map if the variable exists.If it doesn't add to the end of linked list. If it exists, then simply return.
To delete, check in map if the integer exists. If it does, then get the pointer to the node in the linked list and directly access the linked list node and remove it.