Amazon Interview Question SDE1s
Team: IDC
Country: India
Interview Type: In-Person
The code is simple enough to explain what i am trying hence not summing it up
LinkedListNode nthToLast(LinkedListNode head,int value)
{
LinkedListNode p1=head;
LinkedListNode p2=head;
if (p2==null) return null;
for(int i=0;i<value-1;i++)
{
p2=p2.next;
}
if(p2==null)return null;
while(p2.next!=null)
{
p2=p2.next;
p1=p1.next;
}
return p1;
}
This algo will take O(n) time and O(1) space.
null values can be handled in a much better way here and hence more and more way to break this as well , do mention if u see this method not returning the expected o/p in any case
What if n is greater than length of the list? I think the for loop will throw exception then.
1.if n is greater than length of loop while executing first loop itself your p2 will point to null so its a handled case there will be no exception , you can handle null return type from calling method
2.If there is a loop in system : the complexity of solution not the rune time in total will increase as that will be another boolean based method to detect that once at the beginning of the code . You need two node pointers for that as well one slow runner and one fast runner
boolean detectLoop(LinkedListNode head)
{
LinkedListNode slowRunner = head;
LinkedListNode fastRunner = head;
while (fastRunner!=null && fastRunner.next!=null)
{
slowRunner = slowRunner.next;// one step at a time
fastRunner=fastRunner.next.next;// two steps at a time
if(slowRunner==fastRunner)
{
return true;
}
}
return false;
}
Please explain.
Let's say that the list is 5 node long and n == 10
now at the start both p1 and p2 point to head which is obviously not null. So, the first null check doesn't work in this case.
Now when you iterate over the list using p2 pointer for value (I am assuming that is n) times, at the 5th element, the next will be null
in the next execution of the for loop, you'll try p2->next which will throw a null reference exception.
Please correct me if I am wrong.
valid point , but this can be solved by just checking for null in the for loop , isn't it . And sorry for being ambiguous but when i mentioned first loop i meant for loo only . the first if loop is a very basic precaution which might happen in rare of teh rare cases. okay i think this modification will be able o handle the case you are talking about
for(int i=0;i<value-1;i++)
{
if(p2==null) return null;
p2=p2.next;
}
its good thing you were able to think , as i obviously missed it .. Thanks for suggestion , Do let me know if the code still can fail for some case.
Move the first pointer for n steps and then start second pointer from head.When the first pointer reaches the end,second pointer will be in the nth node from last.
Code:
- Dhass April 11, 2013public Node nthNodeFromLast(Node head,int n){ Node cur=head;Node cur1=head; int count=0; while(cur.next!=null){ cur = cur.next; count++; if(count>=n) cur1 = cur1.next; } return cur1; }