Amazon Interview Question
SDE1sCountry: India
Interview Type: In-Person
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
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.
I think the soln is possible if we have pointer to the pointer of last node,i/e double pointer..
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;
}
Head pointer is not given, thats the key point here.
So we can not iterate through the list.
@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.
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.
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..
I got the question properly. And I gave him the correct answer also.
If you have any doubt at any part, let me know.
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;
}
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)
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
}
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
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!
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.
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.
- Jose Cuervo July 11, 2013