Amazon Interview Question for Software Engineer / Developers


Country: India
Interview Type: Written Test




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

for getting the previous nodes of the current node, I agree that xor list must be the answer if it's a singly linked list. But for the XOR to work u need to have either pointer to next or previous nodes, since only then can u do XOR with the current's next pointer to get the pointer to the next or previous node.
Therefore, I think either the question is not complete or if it's complete then it can't be solved.

comments ???

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

i think u r right :)

- bibbsey September 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Its possible only if it is doubly linked list or xor linked list or you know that memory allocation for linked list is contiguous.

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

yes, It's a Xor linked list.

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

veeru,are you a college student?and if yes ,then from which college?

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

cerberuz plz tell how it is possible for xor linklist while no previous or next information available

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

No you can't, either one of them is required.

- Cerberuz September 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

is this question complete ??

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

Since the link list is by default singly link list. Therefore we need to go with this case only.
Just do the XOR (memory efficient) traversal since it allows to traverse in either direction.

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

it is possible only for doubly linked list or circular linked list to get elements before kth element when head is pointing to kth element.
in case doubly linked list we traversed backward to get k elements.
in case of circular list we first count total number of nodes(say n) and second iteration we ignore (n-k) and consider rest k nodes.

we can't find those elements if linked list is represented as xor linked list. we have only one node information for traversing backward or forward direction we need 2 nodes information that we do not have. it is also not mentioned k is the last element or first element.

for example A->B->C->D->E->F
if head points to D then we get C address by ((address of D )XOR (Address of E))
we don't have Address of E.

- sudipta Samanta September 16, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

We have address of E, for example if we want to access the element which is 2 nodes ahead then we do node->next->next which will give you the address of the node which is 2 nodes ahead. So by the XOR operation of single linked list we can find the answer of the question asked

- harish.kv12 September 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

it is possible only for doubly linked list or circular linked list to get elements before kth element when head is pointing to kth element.
in case doubly linked list we traversed backward to get k elements.
in case of circular list we first count total number of nodes(say n) and second iteration we ignore (n-k) and consider rest k nodes.

we can't find those elements if linked list is represented as xor linked list. we have only one node information for traversing backward or forward direction we need 2 nodes information that we do not have. it is also not mentioned k is the last element or first element.

for example A->B->C->D->E->F
if head points to D then we get C address by ((address of D )XOR (Address of E))
we don't have Address of E.

- sudipta Samanta September 16, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I just can't understand why the node pointing to the kth node of the list would be the head of the linked list.

- notbad September 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Actually he didn't mean head, what he meant is a pointer. He was a bit confused while asking[not an issue ]

- Avi September 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

If this is in native code. You get the address of the pointer you are given, then scan through your memory to find that value. When you find it, that is the memory location of the pointer from the previous node. Iterate until you can no longer find your node's address in memory.

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

if u are in kth node then u heve k-1 nodes before that node ....
get the address of the pointer that points to the kth node
starting node will be at the
address of kth node - k(size of that structure )!!!!!!

- raghven3534 October 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Linked List are not allocated memory contigously

- Dexter October 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I was on Interview and has received same question

The trick is: need to delete not the Head node, but to pop up he data from it; ; copy the data from k-th one to head one; link the head node with k-th+1 noe and delete the k-th one

best regards

- Anonymous July 25, 2015 | 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