## Amazon Interview Question for Software Engineer / Developers

Country: India

Comment hidden because of low score. Click to expand.
4
of 4 vote

This comment has been deleted.

Comment hidden because of low score. Click to expand.
0

I think that it is not a complete solution, because you forgot about duplicate values, what are you going to do if you need to add a value that already presented. Also we want to delete let's say value A and if our queue contains several As which one will we have to delete?

Comment hidden because of low score. Click to expand.
0

To handle duplicate values we can implement each hash table entry as linked list.
As two same A's are indistinguishable, we can delete any one of them. We have to update the hash table index's linked list as well ( delete its first element ).

Comment hidden because of low score. Click to expand.
0

Updated Approach :
Queue ( linked list ) + hash table ( each entry is a linked list ).
Implement queue as linked list. Always save its head and tail pointer.
For each element i inserted in queue add a new node in the hash[i] linked list. This node contains two values i.e. pointer to position of value in queue + pointer to previous element in the queue ( for deletion previous pointer is required ).

Enqueue : O(1) : add at hash[i] a new node with two pointers as explained above + enqueue value in queue ( linked list ) using tail pointer
Dequeue : O(1) : delete in queue using head pointer + remove first node of hash[i]
Search : O(1) : check if hash[i] is NULL or not
Delete any element O(1): first search then delete.

Comment hidden because of low score. Click to expand.
0

Some missing details. To delete, we need to remember to (1) look up the value to be deleted in the hash table, (2) find the pointer to the corresponding node in the queue, (3) find the pointer to the previous node in the queue, (4) update the previous node's next pointer to point to the node following the deleted node, (5) remove the entry from hash table for the deleted value, (6) look up the value of the node following the deleted node in the hash table, (7) update it's previous pointer to point to the node before the deleted node in the queue.

For dequeue, we also need to look up the value of the node following the deleted node in the hash table and assign its previous pointer to null.

Comment hidden because of low score. Click to expand.
0

Why the comment is deleted???

Comment hidden because of low score. Click to expand.
0

I accidentaly deleted my comment while editing. But dont know why its showing Administrator instead of my tag_name.

Comment hidden because of low score. Click to expand.
0

Can you post up comment again?

Comment hidden because of low score. Click to expand.
0

I've already posted the updated approach above.

Comment hidden because of low score. Click to expand.
3
of 3 vote

HashTable: Key=value, Value=some structure (containing one pointer to store the address of the value, one "count" variable - to store the number of duplicate values in the list and one linkedlist to store the address of the duplicate values).

1. Enqueue : into hash table and list.
If the value to be inserted is a duplicate value then increment the count(in the structure of the HashValue O(1)). Insert the value in the linkedlist and store tohis address into the pointer(in the structure of the HashValue). O(1) - Thus u can keep track of even the duplicate values easily.

2. Dequeue: Remove the value from the linked list. - O(1)
- Find the value in the Hash and check the value of the count -O(1). If it is >0 then decrement it and delete the respective address from the linkedList(in the structue of the HAshValue) - O(1).

3. Delete: First find the element in the HashTable - O(1). And the follow the same procedure as above(Dequeue). O(1)

4.IsNumberPresent: can be found from the HashTable. O(1)

Comment hidden because of low score. Click to expand.
0

Nice solution.
It will be efficient while deleting if we use Double linkedlist instead of Linkedlist. In hash Table insert the value with all the nodes which has same values. Using one node we can find its previous and next nodes efficiently.

Comment hidden because of low score. Click to expand.
0

Comment hidden because of low score. Click to expand.
2
of 4 vote

HashTable + Doubly Linked List implementation of Queue.

Comment hidden because of low score. Click to expand.
0

@Anonymous: Why are you using a doubly linked list?

Comment hidden because of low score. Click to expand.
0

@Anonymous: And, please also tell me how is the delete operation O(1). You will need to locate the element in the linked list to delete it.

Comment hidden because of low score. Click to expand.
0

@alex: Here is a hint: The values in the hashtables are pointers.

Comment hidden because of low score. Click to expand.
0

Oh right! Very foolish of me to ask..Thank you!

Comment hidden because of low score. Click to expand.
0

hi,
I still didn't get how it would be deleted in O(1) if you keep pointers in hashtables ?

Comment hidden because of low score. Click to expand.
0

hey annonymous couldnt understand clearly..please elaborate your logic..why doubly linked list and how delete operation in O(1) ?

Comment hidden because of low score. Click to expand.
0

Would you give the link to it plz?

Comment hidden because of low score. Click to expand.
0

Linked list isto maintain the order fifo.so that the elemnt come first remove first from both map and doubly linked list .so delete operation will also take o(1) time

Comment hidden because of low score. Click to expand.
0

why are we using doubly linked list..?

Comment hidden because of low score. Click to expand.
0

1> DLL :- so that delete operation for arbitrary number takes O(1) time since , for deletion you need to set pointers for previous and next nodes.
2> hastable :- it will map <Int,LinkedListNode> for O(1) retrieval.

Comment hidden because of low score. Click to expand.
0

For the benefit of others: we use hash table to look up the elements. To support delete, enqueue and dequeue operations also, we need to know which element is "before" and which one is "after"

We keep track of latest inserted element of hash table [ head ], as well as the the next element to be dequeued [ tail ]

So when we want to enqueue/dequeue, we insert the element in hash table at random position mapped by "hash key" and update the next, previous & also head and tail.

for delete, look up hash table & remove the element entry and update the next, previous pointers ( also head, tail if necessary ).

O(1) complexity depends on the "good"ness of hash algorithm followed. We assume that hash algo is good enough to guarantee O(1) lookup operations.

Doubly linked list is used because, an element need inform its predecessor of insertion as well as successor when it is chosen to be deleted.

Comment hidden because of low score. Click to expand.
0

These may be stupid questions but I have to get it clarified

1. We maintain hashtable with number and their pointer references, so that any random number can be deleted in O(1).

2. We maintain a doubly linked list to actually maintain the data structure holding the data.

3. If we want to delete a number in O(1), we get the reference for the same in O(1) and then delete it from our main data structure and update head and tail.

Is this correct? Or I have totally misunderstood the concept here?

Also, wouldn't it help to enqueue and dequeue if we keep track of head and tails pointers in Singly Linked List?

Comment hidden because of low score. Click to expand.
0

@Anonymous:

by using a double linked list, you are holding the reference to the previous node and next node.
previous<->current<->next
once u get the pointer for the current node from hashtable,
u can update the pointers easily. (de-reference the CURRENT node)
current.previous.next = current.next
current.next.previous = current.previous
so that would be a constant time = O(1)

if u have a singly linked list, u need to travel all the way from the head to your current node in order to make a single update
previous.next = current.next. in the worst case, if you are always deleting the middle node in that list, you will end up travelling half the list every time. O(n/2) = O(n) for each deletion

correct me if I am wrong

Comment hidden because of low score. Click to expand.
0
of 2 vote

Queue + hashtable

only thing to notice is that when you dequeue, you need to check the hashtable to check if the item to be dequeued is valid or not

Comment hidden because of low score. Click to expand.
0

Exactly You are right.

Comment hidden because of low score. Click to expand.
0

@Evan what is the benefit of using Queue along with Hashtable ?

Comment hidden because of low score. Click to expand.
0

How do you delete a number which is present at middle of the queue in O(1) time? if you remove from hash table that is not enough, you need to remove it from queue also.

Comment hidden because of low score. Click to expand.
0

Implement Queue with double linked list & hashtable will have key & queue element prev & next element pointer. From hash table get exact element & pre & next pointer which help to delete particular element from queue. I hope yo aware of deleting a element from double linked list.

Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0

Using circular double linked list and hash table will make it more easier.
In circular double linked list we need not to store the address of tail node.
1>enqueue is O(1).
2>dequeue is O(1).
3>deleteion can be done using hash table which will store value and address of node.
4>searching can be done using hash table in O(1).

Comment hidden because of low score. Click to expand.
0

Do you think overhead in circular doubly linked list will be less than overhead of storing a single tail pointer ?

Comment hidden because of low score. Click to expand.
0
of 0 vote

Array....
a long array...where index will be used as hashing.
and it will also take care of duplicate elements, because for that we can increase array[number]
1. enqueue and dequeue will be O(1)---> array[number]++ for enqueue; array[number]-- for dequeue
2. IsNumberPresent --> array[number] > 0 present else not
3. delete--> array[number] =0 to remove all duplicate of this number and itself

Comment hidden because of low score. Click to expand.
0
of 0 vote

I think something like this could help

The so called DS will have a queue (implemented using Double linked list) and a map (number being the key and address being the value), a head and a tail pointers

1. enqueue & dequeue -> We us head and tail pointers to perform this operation
2. isnumberpresent -> we use the map to check this out
3. delete -> use map to get to the address and then delete the node

But this approach might not work for duplicate elements.

Comment hidden because of low score. Click to expand.
0

for duplicate elements. you can store the offsets linkedlist/arraylist (its a queue/prev,next pointer) in the value of the hashmap.
when you want to dequeue, just pickup the top offset and delete it from the map's value's arraylist/linkedlist and delete from the element from queue.

Comment hidden because of low score. Click to expand.
0
of 0 vote

HashTable will have 2 pointers one for NextItem, PrevItem. and 1 Linked List pointer Incase of duplicates.

In case of Enque .. after inserting into hash ..we can make curPtr= CurPtr->next and CurPtrt->Prev= cur

Comment hidden because of low score. Click to expand.
0

Following you hind I have written solution like this

``````package edu.example.datastructure;

import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;

public class EfficientQueue  {

private final Map<Integer,Integer> map;

EfficientQueue() {
}

public void enqueue(Integer i) {
map.put(i, i);
}

public Integer remove(Integer i) {
return map.remove(i);
}

public Integer dequeue() {
Iterator<Entry<Integer, Integer>> iter = map.entrySet().iterator();
if (iter.hasNext())
return map.remove(iter.next().getKey());
else
return null;
}

public boolean isPresent(Integer i) {
return map.get(i) == null ?false:true;
}

public boolean hasNext() {
return !map.isEmpty();
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

I think the LInkedHashMap (as in JAVA) should do this

Comment hidden because of low score. Click to expand.
0
of 0 vote

1)Enque ->Normal enque operation i.e; arayy[i++]= val;
and HASH[val]= i-1;
2)Deque -> Normal Deque val=array[top--];
3)Delate(val)->if HASH[val]!=0) array[HASH[val]]=any mark for deleted item
4)IsPresent -> return array[top];

Comment hidden because of low score. Click to expand.
0
Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import collections
class dict_queue:
def __init__(self):
self.q = collections.deque()
self.d = {}

def enqueue(self, x):
self.q.append(x)
if x in self.d:
self.d[x] += 1
else:
self.d[x] = 1

def dequeue(self):
x = self.q.popleft()
while x not in self.d:
x = self.q.popleft()
self.d[x] -= 1
if self.d[x] == 0:
del self.d[x]
return x

def delete(self, x):
if x in self.d:
self.d[x] -= 1
if self.d[x] == 0:
del self.d[x]

def exists(self, x):
return (x in self.d)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.HashMap;
import java.util.Queue;

/*
* Design a data structure for the following operations:
*
* I. Enqueue
* II. Dequeue
* III. Delete a given number(if it is present in the queue, else do nothing)
* IV. isNumberPresent
*
* All these operations should take O(1) time
*/
private int NthIn;
private int NthOut;
private Queue<Integer> myQueue;
private HashMap<Integer,Integer> validPosition;

this.NthIn=1;
this.NthOut=1;
this.validPosition=new HashMap<Integer,Integer>();
}

public void Enqueue(int data){
if(this.validPosition.containsKey(data)){
if(this.validPosition.get(data)==-1){
this.validPosition.put(data, this.NthIn);
}
}
else{
this.validPosition.put(data, this.NthIn);
}
this.NthIn++;
}

public int Dequeue(){

while(!this.myQueue.isEmpty()){
int result=this.myQueue.poll();
if(this.validPosition.get(result)==-1||this.validPosition.get(result)>this.NthOut){
this.NthOut++;
continue;
}
else{
this.NthOut++;
return result;
}
}

return Integer.MAX_VALUE;
}

public void DeleteGivenNumber(int data){
if(this.validPosition.containsKey(data)){
this.validPosition.put(data, -1);
}
}

public boolean isNumberPresent(int data){
if(this.validPosition.containsKey(data)){
if(this.validPosition.get(data)==-1){
return false;
}
else{
return true;
}
}
else{
return false;
}

}

public static void main(String[] args) {
test.Enqueue(1);
test.Enqueue(1);
test.Enqueue(2);
test.DeleteGivenNumber(1);
test.Enqueue(1);
System.out.println(test.Dequeue());
System.out.println(test.Dequeue());

}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

LinkedHashmap where the underlying linklist should be dequeue. So have a hashtable and a dequeue. Whenever store data in hashtable insert a node in dequeue having key and value.

Comment hidden because of low score. Click to expand.
0
of 0 vote

This problem has already been discussed few weeks back : id=14546770

Comment hidden because of low score. Click to expand.
0
of 0 vote

hash table which holds the actual element and a queue(linklist) which holds the pointer to the location in the hash table.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Comment hidden because of low score. Click to expand.
0
of 0 vote

it can be done using n*3 matrix. The matrix index is the index for the element. For example, for an element 5,matrix[5][0]=index of prev, matrix[5][1]=1, ie element present,matrix[5][2]=index of next. If any element is not present, we can uniquely denote it by filling the row with some predefined symbol. We need 2 int variables front and rear which can be updated if necessary. The 4 operations can be done in O(1) time.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Is that phone interview question?

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.