Qualcomm Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
struct node* getNthLast(struct node* head,int n)
{
struct node *tmp1, *tmp2;
tmp1=tmp2=head;
while(tmp2)
{ if(n>0)
{
tmp2=tmp2->next;
n--;
}
else
{
tmp1=tmp1->next;
tmp2=tmp2->next;
}
}
return tmp1;
You can always edit your comment and correct any typos. Check 'Edit' link on your reply.
Keep a queue of fixed size n and loop through the linked list. As you get each node perform the following operations enqueue the current node in the end and dequeue the first element if it is full.
Precisely the pseudo code should look like:
FetchNthFromEnd (node top)
begin
queue q(n)
while(top is not null)
loop
enqueue(q,top) // it should handle the case when the queue is full, in that case the first element should be dequeued and then new element should be enqueued.
next(top)
endloop
return dequeue(q)
end
enqueue and dequeue both are O(1) so it is O(N).
// Find tail
struct node* findTail(struct node* head)
{
struct node* tail = NULL;
while(head != NULL)
{
tail = head;
head = head->next;
}
return tail;
}
node *Function(int nthnode_to_move)
{
int totalnodes = 0, difference = 0, nthnode = 0;
node *temp1 = head;
node *temp2 = head;
if ( head == NULL )
return 0;
while ( temp->next != NULL )
totalnodes++;
if ( totalnodes < nthnode_to_move )
return 0;
else
{
difference = totalnodes - nthnode_to_move;
nthnode = difference + 1;
while ( nthnode < 0 )
{
temp2 = temp2->next;
nthnode--;
}
return temp2;
}
}
if(head==null) return null;
- DH October 26, 2011Start with two pointers.
P1 and P2 pointing at the head.
keeping p1 at the position, increment p2 n times. (During the process, if anywhere p2 points to null, return null).
Now increment p1 and p2 together until p2->next == null.
p1 points to the nth node from the nth node from last.
regards.