HCL Interview Question Software Engineer / Developers
Country: India
Interview Type: In-Person
you don't have any node address nth node or n+1th node address... how you delete?
the function give is
void deletenode(int n)
{
}
here you can't access the any of the linked list pointers
The question seems vague, we need the head of the linked list to traverse it otherwise where will you search
If we had head pointer, then this can be solved
void DeleteNth(int n)
{
Node current = First;
for (int i = 0; i < n - 1; i++)
{
//Move pointer to n - 1th
current = current.Next;
}
Node prev = current;
current = current.Next.Next; // Move pointer to N + 1th
prev.Next = current; // N - 1th node points to N + 1th
}
The question clearly states that we dont have a pointer to head node.
At least, for the purpose of discussion, we can safely assume that n is the address of nth node and Dev's logic is correct
below is the probable answer
when creating the head pointer get the aligned memory with e.x. 128 bytes, so last 7 bits of the address will be zeros... now add the node number to be deleted to this address and convert it into int and pass to the function... in the function extract/deduct the last 7bits from the number so we will get number of node to be deleted and base address... now convert this int base address to linked list pointer address i.e.(node*)
probably they are getting the aligned memory with e.x. 128 bytes, so last 7 bits of the address will be zeros... now add the node number to be deleted to this address and convert it into int and pass to the function... in the function extract/deduct the last 7bits from the number so we will get number of node to be deleted and base address... now convert this int base address to linked list pointer address i.e.(node*)
you have access to only one integer variable "n", other than this you don't have anything... if you want to delete a node in a linked list minimum data required id linked list "node pointer" and the node number "n" to be deleted... so you need to get both of these data in single variable... so this is the only way we can do
Note in the problem statement, it is said that "not have the address of the first node of the Linked list". This doesnt mean you dont have pointer to any node in the Linked List.
Probable Solution: Let us say you are on some node 'X' in this linked list. We can iterate tho' the Linked list with 2 pointers (a and b) which are 'n' nodes away moving them 1 node at a time together. When b reaches the end of the Linked list, a is n nodes from end of the list.
If we know the length of the linked list say 'l', then we can do l - n = d (distance to be used between a, b pointers) to get the 'n' node.
Once we get to the nth node, we can reset the pointers of its neighbours to delete the node.
Suppose there are 2 or more linked lists of at least the requisite length present in memory. WIthout the head pointer, it's obviously impossible to know which of those linked lists the request pertains to. Since the request could pertain to any one of the lists and you have no information on which one, it's not possible to fulfill the request. This is kind of a solid impossibility proof.
Interviewers make mistakes.
I think the parameter is the nth Node.then you can delete it.
void delete(Node * nth){
Node * next = nth->next;
if (next != NULL){
memcpy(nth ,next ,sizeof(Node);
free(next);
next = NULL;
}else{
//how to process this case?
}
}
you have the address of the nth node , to be deleted. See through logic previous pointer means nth -1 node -> next will point to the same node. Wot all u can do is store the address of nth node->next to the nth -1 node->next , with the help of two pointer .
your nth node will be deleted. I have made the program , and it's working properly.
Storing the nth node->next address to the nth node will update your nth -1 node ->next itself. Hence proved.
To delete a node You must have address of any previous node or node which you want to delete shouldn't we last one. If we have any previous node info or list header info then we can traverse upto that node and delete it. In case, if we don't have address of any previous node and the Node which should be deleted is not last one then we can copy n+1 th node's data to nth node and then delete n+1th node.
i hope the parameter is pointer to the node to be deleted.Then it is solved.just go on copying the (n+1)th node data to nth node, till the (n+2)th node is not null.when n+2 node is null,make the next part of current nth node null and using a second pointer of node type delete the last means n+1th node.that's it.it does not work if the node to b deleted is the last node.
oid deleteNode(Node **nodeptr){
Node *curr = *nodeptr, *prev = NULL;
if( (*nodeptr)->next != NULL){
while( curr->next ){
// 1. set previous node
prev = curr;
// 2. copy next data to current item
curr->data = curr->next->data;
// 3. advance curr
curr = curr->next;
}
prev->next = NULL;
nodeptr = &curr;
}
*nodeptr = NULL;
}
void deleteNode(Node **nodeptr){
Node *curr = *nodeptr, *prev = NULL;
if( (*nodeptr)->next != NULL){
while( curr->next ){
// 1. set previous node
prev = curr;
// 2. copy next data to current item
curr->data = curr->next->data;
// 3. advance curr
curr = curr->next;
}
prev->next = NULL;
nodeptr = &curr;
}
*nodeptr = NULL;
}
I am just addind to the notbad solution
void delete(Node * nth){
Node * next = nth->next;
if (next != NULL){
memcpy(nth ,next ,sizeof(Node);
free(next);
next = NULL;
}else{
//how to process this case?
// in this case, we mark the address as NULL
*nth = NULL;
}
will it work? any comments?
}
}
Lets say: nth node has value 5 and n+1th node has 10 value.
- Dev July 29, 2012copy n+1th node value into nth node, and delete n+1th node.