## Amazon Sage Software Interview Question for Software Engineer / Developers

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

Use two pointers. Initalize both pointers to the front of the list then use a loop to traverse one pointer Nth times. Then moves both pointers until one reaches the end of the list. The second pointer is Nth to last element

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

Its very good i feel!

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

Perfect!

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

Perfect!

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

Same to what I thought.....:-)

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

Here n is the distance from the last element. Is there a better solution out there ??

node *getNthToLast(node *head, int *pos, int n) {
*pos=0;
return NULL;
}

node *nElemNode = getNthToLast(head->next, pos, n);
if((*pos)++==n)
else
return nElemNode;
}

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

How do you accomplish this in Java. Sorry but I am a newbie.

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

Iteration solutions are generally better than recursive solutions. Can you do it iteratively?

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

Well its obvious to do it iteratively if its a doubly linked list... simply traverse till the last node... now traverse back n nodes.

On the other hand if its singly linked I dont see how it can be done in an "efficient" manner (without doing something stupid like using extra memory!). You really have to first find the length of the list somehow.... a quick way could be to traverse the list 2 nodes in each iteration of the while/for loop (something I would do to find the middle element of a linked list). Dunno if this makes sense ?

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

Using extra memory isn't much worse than a recursive solution. Every time you add a level to your recursion, you increase the stack. Memory usage for your recursive solution is O(n) anyway.

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

@KHOA U may be right... i also think that 2 pointers make sense and simplifies the solution.

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

If the size of the list is M(compute this) and you want N, then traverse a pointer M-N-1 times.

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

Taking Khoa's idea further...something like this....

int findNthPos(int pos)
{
LLIST ptr1,ptr2;
int current=pos;
while(ptr1->next)
{
current = pos;
ptr2= ptr2->next;
ptr1 = ptr2;
while(current-- >0)
{
if(ptr1!=NULL)
ptr1=ptr1->next;
}

}
return ptr2->data;
}

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

Khoa's solution would work fine. To put it into code

{
if ( pos < 0 || listHead == NULL )
return FAILURE;
while( pos > 0 )
{
if( ptr1 == NULL )
return FAILURE; // could return some other error value
ptr1 = ptr1->next;
pos--;
}
while( ptr1 != NULL )
{
ptr1 = ptr1->next;
ptr2 = ptr2->next;
}
return ptr2->data;
}

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

Trying to see if i can put spaces in here ... being a Virgo, i tend to be fussy about small things sometimes :-)
{
&nbsp;&nbsp;&nbsp;&nbsp;if( pos < 0 || listHead == NULL )
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return FAILURE;
// look up the previous answer for complete code
}

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

node* findNthPos( node* head, int pos )
{
node *nth, *current;
int n = 0;
while(current)
{

current = current->next;
if(n == pos)
{
nth = nth->next;
}
else
{
n++;
}
}
}
if(n == pos)
return nth;
else
return NULL; /* no such node */

}

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

{
int size=0;
while(iter != null)
{
size++;
iter = iter -> next;
}

for(int i=2;i<=size-pos;i++)
{
foundNode=foundNode->next;
}

return foundNode;
}

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

Although the above solutions may work, such complex solutions can potentially introduce bugs that are cumbersome to detect.

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

Just for fun...to find the nth to last element.

If you know how many elements are in the linked list, and you have a pointer to the first element and the last element. Also, assuming that its a double-linked list.

Determine if the Nth element is closer to the front of the list, or the back of the list, ie (length/2). If its closer to the front of the list, travse from the front of the list. If its closer to the back of the list, traverse from the back.

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

Khoa's solution would work fine. To put it into code

if(n<0){ //check for negative input
cout<<"Error";
return NULL;
}

node *nBehind; //n-behind pointer

for(int i=0; i<n; i++){
if(curr->next){
curr = curr->next
}
else{
return NULL;
}

while(curr->next){
curr = curr->next;
nBehind = nBehind->next;
}

return nBehind;
}

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

while(curr) and not while(curr->next)

as your for loop runs from 0 to n-1

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

Khoa's solution would work fine. To put it into code

if(n<0){ //check for negative input
cout<<"Error";
return NULL;
}

node *nBehind; //n-behind pointer

for(int i=0; i<n; i++){
if(curr->next){
curr = curr->next
}
else{
return NULL;
}
}

while(curr->next){
curr = curr->next;
nBehind = nBehind->next;
}

return nBehind;
}

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

What is the difference between 2 pointers solution and Jack's solution? i.e.

1. Count the number of elements. O(M) time, say M nodes totally.
2. From begining travel M-N+1 steps.

The numbers of steps are the same for both.

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

The 2 pointer approach will take only M steps.

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

I think 2 pointer approach also takes 2M-N+1 moves.

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

Why don you take Saloni's code and spend some time to analyze the number of steps.

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

Assuming that Node represents a node in the linked list.

struct ptrpos
{
Node *ptr;
int pos;
}
With array of n structures ptrpos_array, walk through the
list and fill in the array with pointer to the node
and its position till you reach the end. Now we know
the number of nodes lets say it is m. The pointer to
the nth node is at ptrpos_array[m-n+1].

This approach also takes o(m)

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

This approach also takes O(m). However, extra storage is needed for the array.

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

Forget to mention, just round robin the array
filling once you reach the end of the array.

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

{
int i = 1;
ListNode* node = list->first;
ListNode* to_return = NULL;
while (node)
{
if (i == n)
to_return = node;

node = node->next;
i++;
}
}

I'd test this with a few test cases... the edge cases (list size 0, 1), maybe a five-element list, and a case where n is greater than the list size.

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

{
int i = 1;
ListNode* node = list->first;
ListNode* to_return = NULL;
while (node)
{
if (i == n)
{
to_return = list->first;
}
if (i>n)
{
to_return = to_return->next ;
}

node = node->next;
i++;
}
}
Hi Corrected code is above.. Please check the difference

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

take 2 pointers...
move one N steps and then start moving the second also..when the first hits last the second is Nth from last :)

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

node *find(int n, node *p) {
node *temp;
int num = 0;
if (p == NULL) return -1; /* checking error condition */
if (n == 0) return p; /* another error case */
temp = p;
while (p != NULL && num < (n-1)) {
p = p->next; num++;
}
if (p == NULL) return -1; /* list is not big enough */
while (p != NULL) {
p=p->next; temp=temp->next;
}
return temp;
}

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

Amazing solution and smart too..

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

Hi guys
I think instead of using two pointers and then traversing the list we could use some extra space and do it with one pointer.
We can use a circular queue of size n+1 and then start traversing the list till end and keep inserting the elements in the queue.When we reach the end of the list the front element in the queueis the required node.

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

1) Take 2 pointers A and B
2) Point both to starting of list A=0 b=0
3) Move one pointer to nth node A=n-1
4) Move both the pointers and stop when A hits the last Node .Now B will point to the Nth Node from last

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

would it work if say...size of list is m and we try to find nth node from end..where n >m/2??

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

Khoa's solution is right and it is also mentioned in the book PIE with the same solution

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

{
link *nelement = ln, *node = ln;
int i = 0 ;
while(i < N && node != NULL)
{
i++;
node = node->next;
}
if(i != N)
{
printf("\n No. of element in link list is less than %d \n ",N);
return ;
}
else
{
while(node != NULL)
{
node = node->next;
nelement = nelement->next;
}
}
printf("\n %dth element of link list from end is : %d " ,N,nelement->info);
}

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

public string NthElementTolast(Node node,int n)
{
int end=0;int nthPos=0;
string nthValue=node.Value;
if(n<=end || node==null) return "";
while(node.next!=null)
{
node=node.next;
end++;
if((end-nthPos)= n)
{
nthPos++;
nthValue=node.Value;
}
}
return nthValue;
}
}

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

Simple approach on khoa's solution

struct list
{
int data;
struct list *next;
};
typedef struct list myList;

{
myList *fast = NULL;
myList *slow = NULL;
int count = 1;

while(NULL != fast)
{
if ( (count >1) && ((count % 5) == 1)) /* 5 times slower then fast pointer*/
slow = slow->next;

fast = fast->next;
count++;
}

/* in case list contains lesser than 5 nodes, this returns NULL, which is ok as there is no 5th node in the list */
if(count <5)
return NULL;
else
return slow;
}

}

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

For any number n, just replace 5 with n. (count%n) does the trick, it moved slow pointer n times slower than the first one.

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

i dont exactly understand this...
Does this find nth from the tail?
like if we have to find rd from the tail with 10 nodes, does the code find the 7th node?

The problem is more of complexity.
One solution is to count the nodes and return the 7th (after you know that there are 10 elements), or maintain a counter as u add nodes.

The simpler solution is to run two pointers, ptr0 and ptr1, and start using ptr1 after ptr0 has reached the nth element (checking that it is not out of bounds)
Thus, when ptr1 reaches the end of the list, ptr1 points exactly to the nth from tail element.

The above solution gives n from front.
The point to note is nth from tail is difficult in a singly linked list.

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

lolz
typo:
"3rd from tail"
Thus, when "ptr0" reaches the end of the list, ptr1 points exactly to the nth from tail element.

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

I am of a different opinion.
Better use a stack. Assuming worst case where this linked list is single linked list . We do not know number of nodes we do not know the size. Just keep pushing addresses of nodes on a stack still you get end of list.
When end of list is achieved just pop n-1 nodes addresses from the stack and peek top of stack. You will get nth node from last.
Any suggestions on this approach??

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

I thin that stack approaching is not good in terms of memory management and we also need additional work for sorting either. as you mentioned, we do not know how big the size of liked list. but no matter what it's O(m)
iteration would be better, I mean it's simple and clear enough I think.

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

Reverse the list (which can be done in O(n) ) and find the nth position and again reverse the list

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

#include <iostream.h>
#include<iomanip.h>
#include<conio.h>
using namespace std;
struct node
{
int data;
node *nxt;// Pointer to next node
};

node *start_ptr = NULL;
node *current; // Used to move along the list

{ node *temp, *temp2; // Temporary pointers

// Reserve space for new node and fill it with data
temp = new node;
cout << "Please enter the data value: ";
cin >> temp->data;
temp->nxt = NULL;

// Set up link to this node
if (start_ptr == NULL)
{ start_ptr = temp;
current = start_ptr;
}
else
{ temp2 = start_ptr;
// We know this is not NULL - list not empty!
while (temp2->nxt != NULL)
{ temp2 = temp2->nxt;
// Move to next link in chain
}
temp2->nxt = temp;
}
}

void display_list()
{ node *temp;
temp = start_ptr;
cout << endl;
if (temp == NULL)
cout << "The list is empty!" << endl;
else
{ while (temp != NULL)
{ // Display details for what temp points to
cout << "Data : " << temp->data;
if (temp == current)
cout << " <-- Current node";
cout << endl;
temp = temp->nxt;

}
cout << "End of list!" << endl;
}
}

void findNthLast()
{
node *nBehind; //n-behind pointer
node *curr = start_ptr;
int n=3;
for(int i=0; i<n-1; i++)
{
if(curr->nxt)
{
curr = curr->nxt;
}
}
nBehind = start_ptr;
while(curr->nxt)
{
curr = curr->nxt;
nBehind = nBehind->nxt;
}
cout<<"The third last element is :"<<nBehind->data;
}

int main()
{
start_ptr = NULL;
char option;
do
{
display_list();
cout << endl;
cout<<"Enter another value (y/n):";
cin>>option;
}while (option == 'y');
display_list();
cout<<"Here is the third node from the end in the list\n";
findNthLast();
getch();
}

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

If we don't have to maintain the list in its original form, then reverse the list as we iterate the first time. So from L, we now have L' (reversed list). Now iterate N steps in L' to reach Nth last element in original list L. This would require M+N-1 steps. However, it keeps the list in reversed state. If N is very close to M, then this approach is worse than iterating twice on L. Worst case performance of both approaches are the same. If you are going to hit the 'back' of the list, then the approach stated above would work better.

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

Ok

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

``````node* nth_last(node* head, int n)
{
node* nth;
int i;
for(i=0;i<n && nth;++i)
nth=nth->next;
if(!nth) return 0;
while(nth)
{
nth=nth->next;
}
}``````

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

2-pointer approach is the best solution for this question.

All other solutions need extra time or space. Stack / Hash map approach needs extra O(n) space. Recursion (whoever suggested the reversing-approach) is equally bad. Recursion eats up a lotta stack. The function stack's size grows by twice with every recursive call.

So, stick to slow-fast pointer method which is O(n) max.

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

``I want to solve this problem using recursion in JAVA. Can anyone please help me out?``

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

``````//c#
public Node nthToLast(int n)
{
Node runnerNode1 = firstNode;
Node runnerNode2 = firstNode;

for (int j = 0; j < n - 1; ++j)
{
runnerNode2 = runnerNode2.nextNode;
}
while (runnerNode2.nextNode != null)
{
runnerNode1 = runnerNode1.nextNode;
runnerNode2 = runnerNode2.nextNode;
}
return runnerNode1;
}``````

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

Solutions :
1.Two pointer Solution (move first pointer to n and then start moving both the pointer till first touches the end and now the second pointer is the nth node from end)
2.Traverse once and check the length of the list and now traverse len-n times from beginning.
3.Use Hashtable <position,data> push everything into the hasttable and pop the len_of_hash-n from the table
4.Push every data into stack and now pop up the value n times and then you will get your 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.