## Amazon Interview Question

Quality Assurance Engineers**Country:**India

**Interview Type:**In-Person

2nd to last value would be c. Value d is 1st to last. And finally, value e would be last value.

#include<stdio.h>

#include<stdlib.h>

struct node{

int data;

struct node* next;

};

void push (struct node** head_ref,int new_data)

{

struct node *new_node=(struct node*)malloc(sizeof(struct node));

new_node->data=new_data;

new_node->next=(*head_ref);

(*head_ref)=new_node;

}

void display(struct node* head)

{

while(head!=NULL)

{printf("%d-->",head->data);

head=head->next;

}

printf("NULL"); }

void secondlastnode(struct node* head)

{

if(head==NULL||head->next==NULL)

{printf("NULL");

}

else

{

struct node* temp=head;

while(temp->next->next!=NULL)

{

temp=temp->next;

}

printf("\nSecond last node is %d",temp->data);

}

}

void main()

{char ch;

int i,choice,position;

struct node *head=NULL;

do{

printf("\nEnter data:");

scanf("%d",&i);

push(&head,i);

printf("\ndo you wish to continue:");

ch=getche();

}while(ch!='n');

display(head);

secondlastnode(head);

}

This is a simple trailing problem of a linked list to make it hard I'll implement a custom number of before linked nodes and if it is not possible to find the nth from the end it will return null.

```
/// Head should be a dumb object
public Node GetNthBeforeEnd(Node head, int nth)
{
if(head == null)
throw ArgumentNullException("head");
if(head.Next == null && nth < 0)
throw ArgumentOutOfRangeException();
Node tail = head;
Node curr = head;
for(int i = 0; i < nth; i++)
{
cur = cur.Next;
if(cur == null)
{
// Can't get it as there are less than nth
return null;
}
}
while(cur != null)
{
cur = cur.Next;
tail = tail.Next;
}
return tail;
}
public static PrintSecondLast(Node head)
{
Node result = GetNthBeforeEnd(head, 1);
if(result != null)
Console.WriteLine(result.Data);
}
```

Test cast should be

`assert( node != null && node.next != null && node.next.next == null)`

```
function printSecondLastNode(Node head) {
if ( head == null ) return;
Node node = head;
Node candidateSecondLast = null;
while ( node.next != null ) {
candidateSecondLast = node;
node = node.next;
}
if ( candidateSecondLast != null ) {
print candidateSecondLast.value;
}
}
```

#include<stdio.h>

#include<stdlib.h>

struct node{

int data;

struct node* next;

};

void push (struct node** head_ref,int new_data)

{

struct node *new_node=(struct node*)malloc(sizeof(struct node));

new_node->data=new_data;

new_node->next=(*head_ref);

(*head_ref)=new_node;

}

void display(struct node* head)

{

while(head!=NULL)

{printf("%d-->",head->data);

head=head->next;

}

printf("NULL"); }

void secondlastnode(struct node* head)

{

if(head==NULL||head->next==NULL)

{printf("NULL");

}

else

{

struct node* temp=head;

while(temp->next->next!=NULL)

{

temp=temp->next;

}

printf("\nSecond last node is %d",temp->data);

}

}

void main()

{char ch;

int i,choice,position;

struct node *head=NULL;

do{

printf("\nEnter data:");

scanf("%d",&i);

push(&head,i);

printf("\ndo you wish to continue:");

ch=getche();

}while(ch!='n');

display(head);

secondlastnode(head);

public void printSecondLastNode(Link root){

Link current = root;

boolean flag = true;

while(current != null){

if(current.next != null && current.next.next == null){

System.out.print("Second Last Node is : ");

current.displayData();

flag = false;

break;

}

current = current.next;

}

if(flag)

System.out.print("List is too small");

}

Ruby implementation should be like this

```
class Node
attr_accessor :value, :next_node
def initialize(value,next_node)
@value = value
@next_node = next_node
end
end
class LinkList
def initialize(value)
@head = Node.new(value,nil)
end
def add_to_linklist(value)
puts "Inserting value #{value.to_s}"
current = @head
while current.next_node != nil
current = current.next_node
end
current.next_node = Node.new(value,nil)
self
end
def display
current = @head
full_list = []
while current.next_node != nil
full_list += [current.value.to_s]
current = current.next_node
end
full_list += [current.value.to_s]
puts full_list.join("->")
end
def print_the_second_last_node
list = []
second_last_node = nil
current = @head
puts "you have only one element in link list" if current.next_node == nil
while current.next_node != nil
list.push(current.value.to_s)
current = current.next_node
end
index= list.size - 1
puts "second last node is #{list[index]}"
end
end
obj = LinkList.new(10)
obj.add_to_linklist(6)
obj.add_to_linklist(15)
obj.add_to_linklist(20)
obj.print_the_second_last_node
obj.display
```

int getSecondLastNode(Node *head)

{

Node * current = head;

Node * prev = NULL;

while(current != NULL) {

if (current->next != NULL)

prev = current;

current = current->next;

}

return (prev == NULL) ? -1 : prev->data;

}

bool IsSecondLastNode(Node *head, int num)

{

Node *current = head;

while(current != NULL) {

if( current->next != NULL && current->next->next == NULL && current->data == num) {

return true;

}

current = current->next;

}

return false;

}

```
using System;
using System.Collections.Generic;
namespace PrintSecondLastNodeLinkedList
{
class Program
{
static void Main(string[] args)
{
var list = new LinkedList<int>();
var first = new LinkedListNode<int>(1);
var head = first;
list.AddFirst(first);
for(int i=0; i<=10; i++)
{
list.AddAfter(first,i+10);
first = first.Next;
}
Console.Write("Input linked list :");
foreach (var item in list)
{
Console.Write("{0} ",item);
}
Console.WriteLine();
Console.WriteLine("Second Last Node : {0}", GetSecondLastNode(head).Value);
Console.ReadLine();
}
public static LinkedListNode<int> GetSecondLastNode(LinkedListNode<int> input)
{
if (input == null) throw new ArgumentNullException();
if (input.Next == null) throw new ArgumentException("List has only one item");
while(input.Next.Next!=null)
{
input = input.Next;
}
return input;
}
}
}
```

```
//Efficient o(n) algo for getting nth element from last
public Node<T> FindNthelementFromLast(int n)
{
if (First == null)
return null;
var current = First;
var mBehind = First;
for (int i = 0; i < n; i++)
{
if (current != null)
current = current.Next;
else
return null;
}
while (current !=null)
{
current = current.Next;
mBehind = mBehind.Next;
}
return mBehind;
}
```

void print2ndLastNode(Node *head,int k)

{

Node *current = head;

if(head == NULL)

{

printf("List is empty");

return ;

}

while(current != NULL && k > 0)

{

current = current->next;

--k;

}

if(current == NULL)

{

printf("Error Lenght of List is less than 2 ");

return;

}

Node *kthNode = head;

while(current != NULL)

{

current = current->next;

kthNode = kthNode->next;

}

printf("2nd(kth) node from the end : %d ",kthNode->data);

return;

}

@Santhosh

As per your code,we have to pass the value of k

In a linked list of 10 elements, if we have to print the 9th element and we pass the value of k as 9, your code works.

As per the question, we do not know the size in advance, so finding the size and getting the value of k has to be covered in the code (In the case of 10 elements, k=9 -->second last index)

- tus124 July 26, 2015