Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
since u said number of queues are not fixed you can take a linked list where each node will contain address to a queue so whenever u need a new queue you just create a new node ..
Pros ..
1) Flexibility of size
2) Max. space utilization
Cons ..
1) no random access
2) overhead of pointer
definition of node of linked list will depend on how queue is implemented ..
1) if size of queue is constant use array .. then node is defined as follows :
struct node
{
int * queue; // queue is name of pointer pointing to base address of queue
struct node * link // link to next node
};
2) if variable size of queue is required and u don't mind the pointer overhead you can use linked list ... then definition of node will be ..
struct Qnode // node of queue using linked list
{
int data; // store data at node
struct Qnode * next; // pointer to next node
};
struct node // node containing start address of queues
{
struct Qnode * queue; // stores address of first node of queue liked list
struct node * link; // link to next node of linked list
};
public class NQues {
public List<Integer>[] ques;
public NQues(int n){
ques = (ArrayList<Integer>[])new ArrayList[n];
for(int p=0;p<n;p++){
ques[p]=new ArrayList<Integer>();
}}
public void insert(int data, int queNum){
if(queNum>ques.length)
System.out.println("System has less than "+queNum+" Ques. Please enter valid Queue number");
ques[queNum-1].add(data);
}
public int peek(int queNum){
if(ques[queNum-1].size()==0){
System.out.println("Queue "+queNum+ " is empty");
return -1;
}
return ques[queNum-1].get(0);
}
public int poll(int queNum){
if(ques[queNum-1].size()==0){
System.out.println("Queue "+queNum+ " is empty");
return -1;
}
return ques[queNum-1].remove(0);
}
public int size(int queNum){
return ques[queNum-1].size();
}
}
I will consider this problem as a hashTable implementation, where we can imagine each hashed key will act as a head of n queues and linear chaining will represent data structure of each queue.
To solve this problem, i will use a hashing function which will convert all the keys(data) to n hashed values(n buckets) using the very basic concept of collision resolution in HashTable. For each hashed key collision, i will add value in a chain(queues) in relevant bucket out of those n buckets. I will also keep loading factor to be 90%.
We could use an allocator which allocates chunks of size x as required and maintain linked lists. Array lists would waste a lot of space since they allocate more than absolute required space.
- Noobie September 03, 2012