Amazon Interview Question
Quality Assurance EngineersCountry: 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