Interview Question






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

1. Reverse one of the link list and then check for the node to node equality.
2. If the list is doubly linked list - then it is simple.
3. Use recursion to traverse one list => so the u r effectively pushing the list nodes as onto a stack. Now start comparing. If one fails - u terminate. In case one list exhausted and other is still non empty - u terminate. Else u succeed.

- Lord Darth Plagueis August 08, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

3 will need O(n) space since recursive function builds stacks

- NIR August 08, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

it is not a problem .

- prabagaran August 09, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool isRev(node* orig, node*& rev) {
    if (!orig && !rev) return true;
    if (orig && rev) {
        bool match = isRev(orig->next, rev) && (orig->value == rev->value);
        rev = rev->next;
        return match;
    }
    return !orig && rev;
}

- mg August 08, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think node rev always points to the same element (head)and it doesn't move in the call stack

- hopebasedcoder August 08, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

igore the prev comment

- hopebasedcoder August 08, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thanks to @restlesstoday, there's a bug if length is not the same, you need if(rev) before rev = rev->next. Another thing, a function is needed to check for NULLs (and may be length) before sending the heads to isRev.

- mg August 09, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Using system stack
node * check_rev(node *ptr1, node * ptr2)
{
    node * reverse_ptr = 0;
    if(ptr1->next != 0)
           reverse_ptr = check_rev(ptr1->next);
    else
           reverse_ptr = ptr2;

    if(reverse_ptr == 0
       || (*ptr1 != *reverse_ptr))
           reverse_ptrurn 0;

    return reverse_ptr->next;
}

- Ashutosh August 08, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Ignore previous code, it have a typo
The correct one is

node * check_rev(node *ptr1, node * ptr2)
{
    node * reverse_ptr = 0;
    if(ptr1->next != 0)
           reverse_ptr = check_rev(ptr1->next);
    else
           reverse_ptr = ptr2;

    if(reverse_ptr == 0
       || (*ptr1 != *reverse_ptr))
      return 0;

    return reverse_ptr->next;
}

- Ashutosh August 08, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@mg
Nice code.
But it fails/seg fault when the length of the lists are unequal ( size of orig > rev) due to the pass by reference argument -- node*& rev.

You'll need to add guard statements to make sure rev is non-null before derefencing rev.

@Ashutosh -- not sure how your code works. check_rev() takes two arguments.

- restlesstoday August 09, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes, I didn't test for that. I should have a function that checks for length and NULLs before passing it to the recursive function isRev. Thanks!

- mg August 09, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

To Be clear:
How can we have a linked list(LIST) and a reversed list(REVLIST) of itself (with physically same nodes). This is not possible.

If we are talking about reversal with respect to data in the list then it is possible.
Algo for this case:

step1: reverse any of the lists
step2: compare data at each node of the both the lists
step3: If corresponding data in the both the lists is same then ANS: Yes
else ANS: "NO"

- Anji September 10, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

If we are taking any recursive function then we are calling a 'Stack'. To be clear we are not supposed to use 'Stack' over here !!!

- particularraj November 01, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@Anji
Neat Solution. Why bring recursion into picture? Anyway it does not help.

- master December 30, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

multiply the data in the first node by 10,second node by 100 and so on...add all the values...multiply the other linked list in decreasing powers of ten...add the values...if both are same then the second one is the reverse of the first
for example consider
1)1->2->3
2)3->2->1
now consider the first list
1*10+2*100+3*1000
we get the result as 3210
now consider the second list
3*1000+2*100+1*10
we get the result as 3210
hence the result

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

best solution....

- cool:) July 12, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

no doubt!

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

Big assumption that linked list contain integral value

- M August 17, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

what the hell, how about

1) 100->10->1
2) 2->5->50

- Anonymous September 03, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

above solution is good one,we dont know how many elemants in the lists,
also if list contains 100 elements,have to mul by 10 power 100,this very expensive
so ignore the previous ans

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

above solution is not good one,we dont know how many elemants in the lists,
also if list contains 100 elements,have to mul by 10 power 100,this very expensive
so ignore the previous ans

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

recursion is the best way to check without changing both of the list...!

- PKT February 09, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Double recursion is the only way :D

- sanjithkanagavel July 19, 2014 | 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