## Amazon None Interview Question for Nones

• 0

Country: India
Interview Type: Written Test

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

I am assuming that list's head is pointing the start of queue (so the front) and tail is pointing the end of queue (so the rear as first in first out). So if the list is circular, then if we have a pointer that points to the head, then for enqueue operation, we have to traverse to the end of the list and then can add a new element (I am assuming list in single linked list). But if we have a pointer at tail, then for enqueue we can do that O(1) by newnode->next=tail->next->next; tail->next=newnode; tail=newnode;
For dequeue, We can do that in O(1) too, newnode=tail->next; tail->next=tail->nex->next; return newnode;

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

I guess the answer should be the "node before the front node" of the queue, since for deletion in O(1) you need node before front , since list is circulary connceted so rear can also be approached by this node so both insertiona nd deletion will be O(1

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

1) Rear.
As the rear pointer is the pointer can access the top and the bottom of this list in constant time of 1. All other node is depending on the length of this list and its position. The worst case is the front because it needs to go through the whole list to reach the last node.

And enqueue/dequeue is an operation on top/bottom node.

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

rearP; // pointer pointing to the rear node
------ enqueue ------
newNode->next = rearP->next;
rearP->next = newNode;

------ dequeue -------
topP = rearP->next;
rearP->next = top->next;

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

you need front of queue (i.e end of the circular LL which point to first of the LL).
enque: (insert at node next to p)
Node n = new Node();
n.next = p.next;
p.next = n;
deque: (Delete the node at p)
p.data = p.next.data;
p.next = p.next.next;

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

I guess the answer should be the "node before the front node" of the queue.

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

yes,
since for deletion in O(1) you need node before front , since list is circulary connceted so rear can also be approached by this node so both insertiona nd deletion will be O(1)

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

folks what do we mean by taking O(1) time. what does that exactly mean?

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

You want a pointer to the last item.

Suppose three items in the queue.
- Item #1 points to item #2
- Item #2 points to item #3
- Item #3 points to item #1

To enqueue a new item (item #4), we need to change item #3 to point to item #4.

Once item #4 is added, to dequeue item #1 we need to change item #4 to point to item #2.

For both enqueue and dequeue, we're updating the last item in the list, so having a pointer to the last item in the list is most efficient.

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

I think it is option D which could be node before rare that is answer_node->next=rare.
Cause for
1.add operation on queue you have to do
2. To remove from front

If the rare node is consider as answer we have to traverse whole link list to dlete the rare node to perform delete operation.

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

I think it is option D which could be node before rare that is answer_node->next=rare.
Cause for
1.add operation on queue you have to do
2. To remove from front

If the rare node is consider as answer we have to traverse whole link list to delete the rare node to perform delete operation.

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

If anyone tried to find out that

If there is only 1 element in list i.e. pointing to itself condition then you cant perform deletion.

So answer is c) not possible

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

I think using 1 ,2 ,3 u can do it

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

i think it would be front bz when v r talking about circular list so if front is assigned a pointer , v cn come to rear by just finding next pointer to the next node .

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

Yes...
it is the front of the queue as we can use the circular linked list
1)we can enqueue the element at the rear by bellow
newNode->next = front->next ;
front->next = newNode;
newNode->data = front->data;
front->data = givenDataToEnqueue;
front = newNode;

2)To Dequeue:
As we are enqeuing from the rear by above snippet ..
For deqeue we need to do it from front.
nextFrontNode = front->next;
front->data = nextFrontNode->data;
front->next = nextFrontNode->next;
free(nextFrontNode);

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

dequeue is not correct..

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.