Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Written Test
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 plz tell how it is possible for xor linklist while no previous or next information available
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.
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.
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.
I just can't understand why the node pointing to the kth node of the list would be the head of the linked list.
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 )!!!!!!
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.
- next September 16, 2012Therefore, I think either the question is not complete or if it's complete then it can't be solved.
comments ???