## Amazon Interview Question for SDE1s

• 0

Team: IDC
Country: India
Interview Type: In-Person

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

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:

``````public Node nthNodeFromLast(Node head,int n){
int count=0;
while(cur.next!=null){
cur = cur.next;
count++;
if(count>=n)
cur1 = cur1.next;
}
return cur1;
}``````

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

doesnt your pointers start at same point? what is the use of having two pointers? One pointer should have a head start:

``cur1 = head.next.next;``

so that its always 2 steps ahead

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

struct node* nEndNode(struct node* head, int n) {
int i;
for(i=0;i<n;i++)
current = current -> next;
while(current->next!=NULL){
current = current -> next;
ref=ref->next;
}
return ref;
}

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

``````The code  is simple enough to explain what i am trying hence not summing it up

{
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``````

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

i have given same solu but they told me how to break my code

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

What if n is greater than length of the list? I think the for loop will throw exception then.

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

What if there is a loop in the list ?

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

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)
{
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;
}``````

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

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.

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

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.

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

Node findNth(int m){
}else{return null;}

int n=0;
while(fast.next!=null){
if(n==m){
slow=slow.next;
}
else{
n++;
}

fast=fast.next;
}

return slow;
}

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

correction in previous code int n=1;

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

Take two pointers initially pointing to the first node. Move one of the pointers to the nth node from the beginning. The start moving both the pointers till the first pointer reaches to the end. The second pointer points to the required node.

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.

### 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.