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.

- Jose Cuervo July 11, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nope. No iteration allowed.

- yolo July 12, 2013 | Flag
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

- Anonymous July 12, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

can you write code?

- anonymous February 20, 2015 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 votes

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?

- Sabbir June 30, 2015 | Flag
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.

- Ben July 15, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 votes

How can you walk if the head is not given?

- Peter July 25, 2013 | Flag
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..

- Amit July 11, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

That's a doubly linked list. Not allowed.

- yolo July 12, 2013 | Flag
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;
}

- masterjaso July 11, 2013 | Flag Reply
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.

- yolo July 12, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 3 votes

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

- masterjaso July 12, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

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

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

- yhax July 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

nxt=NULL; //your answer

}

- Anonymous April 18, 2014 | Flag
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...

- PKT July 11, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

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

- yolo July 12, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- PKT July 12, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@yolo,
Can you tell the solution.

- Anonymous July 23, 2013 | Flag
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;
}

- edlai July 12, 2013 | Flag Reply
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;

- bibbsey August 01, 2013 | Flag Reply
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.

- ankuragrawal420 November 14, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

what is given to us?

- aniztar January 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@yolo
Can u please post answer this que?

- Anonymous March 03, 2014 | Flag Reply
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)

- bhuleskar April 12, 2014 | Flag Reply
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
   }

- Algorithmy September 25, 2014 | Flag Reply
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

- Abhishek November 01, 2014 | Flag Reply
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!

- Hamada Zahera February 13, 2015 | Flag Reply
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;

- yagnasri.alla July 13, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Amit July 11, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Ronald Bhuleskar April 18, 2014 | Flag


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