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.

- Administrator August 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- vlad August 26, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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 ).

- Anonymous August 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

^that was my comment ( forgot to sign in ) :P

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.

- Cerberuz August 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Thomas August 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Why the comment is deleted???

- SD August 30, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Cerberuz August 30, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you post up comment again?

- Anonymous April 13, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I've already posted the updated approach above.

- Cerberuz April 13, 2013 | Flag
Comment hidden because of low score. Click to expand.
3
of 3 vote

Linkedlist+HashTable
Linkedlist: Stores the elements
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)

Comments are Appreciated.

- programmer August 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Psycho August 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes, doublylinked list would be feasible than singlyLinkedlist.

- programmer August 30, 2012 | Flag
Comment hidden because of low score. Click to expand.
2
of 4 vote

HashTable + Doubly Linked List implementation of Queue.

- Anonymous December 16, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- alex December 16, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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.

- alex December 16, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous December 16, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- alex December 16, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous December 16, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- zeroByzero December 16, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Would you give the link to it plz?

- Jess December 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous December 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

why are we using doubly linked list..?

- zeroByzero December 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

^ to clarify your doubt.
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.

- krb December 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Suryaamsh December 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- Anonymous December 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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

- Kary December 24, 2012 | Flag
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

- Evan August 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Exactly You are right.

- Karthik August 26, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous August 26, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Anonymous August 26, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- krish August 26, 2012 | Flag
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 votes

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).

- Aalok August 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Cerberuz August 27, 2012 | Flag
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

- Aks August 26, 2012 | Flag Reply
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.

- inasaa August 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- seahawk August 31, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

How about hashtable with Linked List ??

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

- Raja August 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Following you hind I have written solution like this

package edu.example.datastructure;

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

public class EfficientQueue  {
	
	private final Map<Integer,Integer> map;
	 
	EfficientQueue() {
		map = new LinkedHashMap<Integer, Integer>();
	}
	
	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();
	}

	

	

}

- kavan August 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- kghatak August 27, 2012 | Flag Reply
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];

- samrat August 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes
- programmer August 27, 2012 | Flag
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)

- Anonymous August 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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




public class Queue_With_Additional_Functions {

/*
* 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;

public Queue_With_Additional_Functions(){
this.NthIn=1;
this.NthOut=1;
this.myQueue=new LinkedList<Integer>();
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++;
this.myQueue.add(data);
}

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) {
Queue_With_Additional_Functions test=new Queue_With_Additional_Functions();
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());

}

}

- Chengyun Zuo August 28, 2012 | Flag Reply
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.

- saurabh August 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Cerberuz December 16, 2012 | Flag Reply
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.

- Anonymous December 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Cheeck out java's LinkedHashMap implementation.

- Jagat January 17, 2013 | Flag Reply
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.

- Sounava Pal May 22, 2021 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Is that phone interview question?

- Lyubomir December 16, 2012 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More