McAfee Interview Question Applications Developers
Country: United States
Interview Type: Written Test
#include <iostream>
using namespace std;
struct Node
{
int mData;
Node* mNext;
Node(int data , Node* next=nullptr):mData(data),mNext(next) {}
};
struct List
{
List():mHead(nullptr){}
Node* mHead;
void Add(int data)
{
if(!mHead)
mHead = new Node(data);
else
{
Node* temp = mHead;
while(temp->mNext != nullptr)
temp = temp->mNext;
temp->mNext = new Node(data);
}
}
void Display()
{
Node *temp = mHead;
cout<<"\n Content of List are : ";
while(temp != nullptr)
{
cout<<"\t"<<temp->mData;
temp = temp->mNext;
}
}
void Find_Last_nth_Element(int count)
{
if( (count>0) && mHead)
{
Node* temp = mHead;
int index = 0;
while( (index < count) && temp )
{
temp = temp->mNext;
++index;
}
if(index != count)
cout<<"\n lesser elements in List"<<endl;
else
{
Node* nthNode = mHead;
while(temp)
{
temp = temp->mNext;
nthNode = nthNode->mNext;
}
cout<<"\n the "<<count<<" node from last in list is "<<nthNode->mData;
}
}
}
};
void main()
{
cout<<"\n Program Started"<<endl;
List myList;
for(int i=0;i<20;++i)
myList.Add(10*i+i);
myList.Display();
int nthNode=0;
cout<<"\nEnter nth Element from last:";
cin>>nthNode;
myList.Find_Last_nth_Element(nthNode);
cout<<"\n Program Ended"<<endl;
}
public static void findFifthElementFromEnd() {
if (linkedList == null && linkedList.head == null) {
return;
}
Node fast, slow;
int i = 0;
fast = slow = linkedList.head;
while (fast != null && i < 5) {
fast = fast.next;
i++;
} // now fast reach to 5th location.
if (i < 4) {
System.out
.println("Linkedlist has less than 5 elements");
return;
}
while (fast != null) {
slow = slow.next;
fast = fast.next;
}
System.out.println("5th element from end is :" + slow.data.toString());
}
if(head==NULL)
return NULL;
t1=head;
t2=NULL;
cnt=1;
while(t1!=NULL)
{
if(t1->next==NULL)
return t2;
cnt++;
if(cnt%5==0)
{
t2=t1;
cnt=1;
}
t1=t1->next;
}
return t2;
question its mentioned that it should not be from head.
its not possible to traverse the single link list from tail.
I believe you just misread the question. I believe they mean to just find the node that is located 5th from the end, not the head.
Ok !!
I got it its easy to traverse and identify the 5 th node from last
declare to node pointer *fast & *slow ;both assigned head
declare a counter=0;
while counter<5
fast=fast->link;
now we get a pointer 5 node behind, we keep traversing both one node until fast reach null.
When fast reach the end of the list, Slow will be pointing 5 node from the last which is our required node.
import java.util.List;
import java.util.LinkedList;
import java.util.Iterator;
public class NElement {
public Object findNthElementFromLast(List<Object> l, int leap) {
Iterator fast = l.iterator();
Iterator slow = l.iterator();
Object element = null;
if(l.size() < leap)
return null;
for(int i=0; i<leap-1; i++) {
if (fast.hasNext()) {
fast.next();
}
}
while (fast.hasNext()) {
fast.next();
element = slow.next();
}
return element;
}
public static void main(String[] args) {
List<Object> l = new LinkedList();
for (int i=0; i<Integer.parseInt(args[0]); i++)
l.add(i);
NElement e = new NElement();
System.out.println(e.findNthElementFromLast(l,5));
}
}
Algo 1:
Use two pointers
linkedListNode *FindFifthElementFromEnd(linkedListNode *ptr){
if(ptr == NULL){
return NULL;
}
linkedListNode *frontCrawler = ptr,*tailCrawler= ptr;
int counter = 5;
while(counter){
if(frontCrawler->next != NULL){
frontCrawler = frontCrawler->next;
}else{
return NULL;
}
}
while(frontCrawler->next!= NULL){
frontCrawler = frontCrawler->next;
tailCrawler = tailCrawler->next;
}
return tailCrawler;
}
Algo 2:
1) Use hashmap
2) return appropriate node
linkedListNode *FindFifthElementFromEndHashMap(linkedListNode *ptr){
if(ptr == NULL){
return NULL;
}
hash_map<int,int> nodeIndexMap;
int counter = -1;
linkedListNode *crawler= ptr;
while(crawler != NULL){
nodeIndexMap.insert(pair<int,int>(++counter,ptr->value));
crawler = crawler->next;
}
if(counter < 4){
return NULL;
}
return nodeIndexMap[counter-4];
}
Algo 3:
1) Find length of linkedlist
2) Return node length - 5
linkedListNode *FindFifthElementFromEndUsingLength(linkedListNode *ptr){
if(ptr == NULL){
return NULL;
}
linkedListNode *crawler = ptr;
int lengthOfLinkedList = 0;
while(crawler != NULL){
lengthOfLinkedList++;
crawler = crawler->next;
}
if(lengthOfLinkedList < 5){
return null;
}
lengthOfLinkedList -= 5;
crawler = ptr;
while(lengthOfLinkedList--){
crawler = crawler->next;
}
return crawler;
}
Traverse the linked list from head to tail and find the number of elements. If space is not an issue we can simultaneously hash the addresses of the node as well (this helps accessing the element in O(1) once we are done). Now, if the addresses are mapped then return the address at n-5 location (we should check if this value is valid). If extra space is not available, then start from head and go all the way to the n-5 element.
list
return_lastKth_obj(list head)
{
list prev=head;
while(1)
{
if(head == NULL)
return prev;
if(head->next == NULL)
return prev->next;
if(head->next->next == NULL)
return prev->next->next;
if(head->next->next->next == NULL)
return prev->next->next->next;
if(head->next->next->next->next == NULL)
return prev->next->next->next->next;
prev = head;
head = head->next->next->next->next->next;
}
}
#include"stdafx.h"
#include"iostream"
#include"string"
using namespace std;
#define P system("pause")
//Class for Singly Linked List with count...
class SingleLinkedList
{
typedef struct Node
{
int n;
Node *pNext;
Node( )
{
n = -1;
pNext = this;
}
Node( int& x )
{
n = x;
pNext = this;
}
} Node;
public:
int length; //count.
Node *pHead;
Node *pEnd;
SingleLinkedList( )
{
pHead = new Node( );
pEnd = pHead;
length = 0;
}
void inset( int x )
{
Node *pNode = new Node( x );
pEnd->pNext = pNode;
pEnd = pNode;
++length;
}
int findNthFromLast( int pos )
{
int actPos = this->length - pos + 1;
Node *pnode = this->pHead;
for(int i = 1; i < actPos ; ++i)
{
pnode = pnode->pNext;
}
return ( pnode->n );
}
};
int main()
{
SingleLinkedList slList;
slList.inset(2);
slList.inset(3);
slList.inset(4);
slList.inset(5);
slList.inset(6);
slList.inset(7);
slList.inset(8);
slList.inset(9);
//Getting 5th element from last...
int n = slList.findNthFromLast( 5 );
cout<<"Fifth element from end: "<< n <<endl;
P;
return 0;
}
#include"stdafx.h"
#include"iostream"
#include"string"
using namespace std;
#define P system("pause")
//Class for Singly Linked List with count...
class SingleLinkedList
{
typedef struct Node
{
int n;
Node *pNext;
Node( )
{
n = -1;
pNext = this;
}
Node( int& x )
{
n = x;
pNext = this;
}
} Node;
public:
int length; //count.
Node *pHead;
Node *pEnd;
SingleLinkedList( )
{
pHead = new Node( );
pEnd = pHead;
length = 0;
}
void inset( int x )
{
Node *pNode = new Node( x );
pEnd->pNext = pNode;
pEnd = pNode;
++length;
}
int findNthFromLast( int pos )
{
int actPos = this->length - pos + 1;
Node *pnode = this->pHead;
for(int i = 1; i < actPos ; ++i)
{
pnode = pnode->pNext;
}
return ( pnode->n );
}
};
int main()
{
SingleLinkedList slList;
slList.inset(2);
slList.inset(3);
slList.inset(4);
slList.inset(5);
slList.inset(6);
slList.inset(7);
slList.inset(8);
slList.inset(9);
//Getting 5th element from last...
int n = slList.findNthFromLast( 5 );
cout<<"Fifth element from end: "<< n <<endl;
P;
return 0;
}
struct Node
{
Node* n;
int v;
};
Node* GetKthNodeFromEnd(Node* head, int k)
{
int count = 0;
Node* kthNode = nullptr;
Node* curNode = head;
while (curNode != nullptr)
{
if (count >= k && kthNode == nullptr)
kthNode = head;
if (count >= k && kthNode != nullptr)
kthNode = kthNode->n;
++count;
curNode = curNode->n;
}
return kthNode;
}
public static void main(String... args) {
LinkedList<Integer> list = new LinkedList<Integer>();
list.addLast(100);
list.addLast(200);
list.addLast(300);
list.addLast(400);
list.addLast(500);
list.addLast(600);
list.addLast(700);
list.addLast(800);
Node<Integer> nFromEnd = findNFromEnd(list.getFirst(), 5);
Node<Integer> node = nFromEnd;
while(node != null) {
System.out.println(node.getData());
node = node.getNext();
}
}
private static Node<Integer> findNFromEnd(Node<Integer> head, int n) {
Node<Integer> firstNode = head;
Node<Integer> current = head;
int index = 1;
while (current.getNext() != null) {
current = current.getNext();
if (index >= n) {
firstNode = firstNode.getNext();
}
index++;
}
return firstNode;
}
public void findElementFromLast(int index) {
if (index < 1 || index > getNodeCount()) {
return;
}
Node currentNode = head;
for (int i = 0; i < (getNodeCount() - index) && currentNode != null; i++) {
currentNode = currentNode.next;
}
currentNode = currentNode.next;
System.out.println("Data: " + currentNode.data);
}
getNodeCount() is a simple function which returns number of nodes in linked list
Take 2 pointers- move the first one past 5 nodes from the head and then start the second one at the head. Keep advancing both the pointers one step at a time until the first pointer reaches the last node when which the second will be pointing to the 5th node from the last.
- Murali Mohan August 16, 2013