## Amazon Interview Question for SDE1s

Country: India
Interview Type: In-Person

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

Your statement of the problem is confusing. I think you want to delete the previous node? If all we need is to delete the last node or tail then it's fairly trivial. You could easily add a head member to each node. Then you have your list start off with a dummy head that never gets removed. Still will take you iterating back to the given node from the head.

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

Nope. No iteration allowed.

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

There is a type of single linked list where the pointer of a node contains the XOR of the previous and next nodes

In such type of a linked list, going back to the previous node is to XOR with the next node, in this case null.

Once we reach the previous node this way its just a matter of completing the formalities

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

can you write code?

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

if we don't have pointer to first node or any node, how can we access info of any node to do the operation you mentioned?

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

I say, the extra data to keep in your node is a flag to indicate if the node is deleted. When you have a chance, e.g., walking the list from the head, you can unlink a node if it is marked deleted, otherwise just respect the deleted flag when handling any node.

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

How can you walk if the head is not given?

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

I think the soln is possible if we have pointer to the pointer of last node,i/e double pointer..

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

That's a doubly linked list. Not allowed.

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

So to delete the last node from a singly linked list, you invoke a function from that node (this is the additional data I believe the interviewer was talking about) that:

1. Checks if this node is the last node - if so set it to null
2. Iterates through the list looking 2 nodes ahead (n.next.next) to find the end of the list
3. Finally moves to the last node and sets it to null

Brief example:

Node n = myLinkedList.getRandomNode(); (this is any node that is part of a linked list)

n.deleteLast();

``````public void deleteLast(){
//check if this is the last node
if(this.next == null) {
this = null;
return;
}

//look 2 nodes ahead to see if we have reached the end
Node temp = this;
while(temp.next.next != null){
temp = temp.next;
}

//Finally, move to last node and set it null
temp = temp.next;
temp = null;
}``````

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

Head pointer is not given, thats the key point here.
So we can not iterate through the list.

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

@yolo

You can iterate through a LinkList without the head pointer, so long as you have one of the nodes from the list. My example above does not utilize a head pointer, but definently utilizes iteration. Every node in a list has a pointer to next, and therefore you can start at any node N and move/look forward.

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

The main thing about removal of node in a LinkedList is to break the chain properly. The above code does not break the linked list chain. There must be some code that assigns "node.next" with a new value. I can't see this from the above code. The statement this=null does not make sense.

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

this = null wont work. What about having this as your method:

``````public Node GetLastNode ()
{
if (this.next == null) return this;
Node temp = this.next;
while (temp.next != null)
{
temp = temp.next;
}
return temp;
}``````

then when you need to delete, you get the last node:

``Node lastNode = givenNode.GetLastNode();``

but you actually only do the delete the next time you use the list e.g. for printing, by doing something like:

``if (currentNode.next == lastNode) { currentNode.next = null; }``

probably not what they want, just my 2 cents..

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

Keep refernce of the node in this case...... and as temp will be null and in else case the last node will be set to null

void del(struct node * &nxt){

struct node *temp=nxt->next;

if(temp!=NULL){
nxt->data=temp->data;
nxt->next=temp->next;

free(temp);

}else

}

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

I am sorry but...
I think question filler didn't get question properly...

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

I got the question properly. And I gave him the correct answer also.

If you have any doubt at any part, let me know.

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

@yolo: oh... my fault... Apologies for that....

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

@yolo,
Can you tell the solution.

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

The solution is possible if you can have a tail pointer and the linked list is made circular.

``````public void add(Node node) {
if(tail==null) {
node.next = node; // Point to itself
}
else {
node.next = tail.next;
tail.next = node;
}

tail = node;
}

public void removeLast() {
if(tail==null) return;
if(tail.next==tail) tail = null; // Single node in linked list

Node newTail = tail;
while(newTail.next != tail) newTail = newTail.next; // Find previous node to tail

newTail.next = tail.next;
tail = newTail;
}``````

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

Use a static variable in the linked list structure.

``````struct LL
{
int data;
LL* next;
static LL* secondLast;
};``````

While creating the list, keep updating the static variable so that it points the second last one.
Then it's simple

``````delete LL::secondLast->next;
LL::secondLast->next = NULL;``````

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

There is no way you can delete the last node when only pointer to a node is given.Generally the question is asked for middle node and the answer still remains NO. But there you can simulate this behavior by copying the contents to next node and deleting the given node.

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

what is given to us?

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

@yolo

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

Keep a deleted bit field in the Node.
struct Node {
int data;
struct Node * next;
int isDeleted;
}

Your function would just set this bit to 1 (isDeleted = 1) when you ask something to delete.
It takes 2 things into consideration.
1. Deleting the last node where there is only 1 node in the LL.
2. Deleting the last node where the random pointer given is itself the last node.

When you traverse the link list later. You can handle these deleted Node blocks in memory:
1. Skip the ones where Node->isDeleted = 1 (not a good option but not wrong either)
2. While traversing at a later point your program would check if any node is marked as deleted and at this time rearrange pointers correctly. (efficient - this is also the technique used in paging where a page is marked as deleted in memory and delayed the deletion on disk)

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

Thanks to the post on stack overflow for the answer-

``````/**
* Delete the node in single linked list given pointer to only that node
*
* The idea is to copy the data from the next node to the current node
* and delete the next node. The solution does not work if the node is the
* last node (This is what candidate has to debate and point out in interview)
*/
public void deleteNode(Node n){
if( n == null && n.next == null){
System.out.println("Cannot delete with out prev pointer");
}

n.data = n.next.data; //copy data from next element to this
Node temp = n.next; //store the next in temp
n.next = n.next.next; //point the next to next.next - delete node
temp = null; //release memory
}``````

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

I'm not getting the question. What are you given?
If you are given a pointer to some random node in a circular (singly) linked list, and you want to delete the node before it, just hold a pointer to that node and go through the list. when you reach that 'starting' element again, delete the previous one.
e.g. given: 'p'
q=p
while(q->next != p && q->next!=NULL)
q=q->next;
(*q)=(*p); //gets rid of the node you are pointing to

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

It's not possible to do this in a single linked list , but at least you should have a pointer , may be the pointer to this node. In case, you can add more data . I think you might add node index while building the list. use this index to iterate from somewhere until length-2 . So you deleted the last element Now!

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

I guess in c or c++ you can do this,

``*lastnode = null;``

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

last node has no next...its next is NULL..read the question carefully

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

It is a bad approach to copy data among the nodes.
Since we use this data as integer, its okay, consider having a Gigabyte of data stored in the link list node. Would you still copy data among nodes. Nah!

I mentioned a solution to this. Please check above with having an extra bit for deleted node.

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.