## Linkedin Interview Question for Software Engineer / Developers

Interview Type: Written Test

Comment hidden because of low score. Click to expand.
5
of 7 vote

1)Take 2 pointer move one pointer by 5 position ie, the difference between the two pointer is 5.
2)Now traverse through the list till the first pointer reaches the end of the list
3) now the second pointer will be pointing to the 5th element from the last.

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

nicely answered... hey bt can u plz elaborate on what does it mean by "in one pass"...

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

"in one pass" means you can traverse only once through the list.

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

So here you're traversing twice, aren't you? Once for each of the two pointers you have.

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

If you do node->next->next->next, and one of the pointers is NULL..you'd get a segmentation fault. How do you plan to do it?

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

Another way is using a queue data structure, which size is 5. Then enqueue the value of the linked list, and dequeue the head when the queue is full, after one pass, the head of the queue is the number you want.

Comment hidden because of low score. Click to expand.
1
of 3 vote

Use One pointer to the list and a queue of size 5:
1) traverse to the 5th node
2) insert the element at the queue
3) if the queue is full, take rear element out and insert the new element at the front
4) repeat it till the pointer reaches null
5) the rear pointer of the queue contains the 5th element from the tail of the list..

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

Cobra,
when we require 5th element from end. so we can use variable also.. then what is the need of queue ?

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

if you use a variable, how will you say it is a nth element from tail??
are u going to use n variables to find nth element from tail?

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

Good argument, cobra. It's always good to design your code to be easy to change. With your approach the value 5 would probably be one parameter passed to the queue in one place in the code.

One small correction: you need to be inserting elements into the queue even as you traverse to the 5th node.

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

You have to tell the fifth element from last using a linkedList

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

Here is the java implementation, hope it helps.

if(queue.size() == 5){
queue.poll();
} else {
}
}

//There are less than 5 node
if(queue.size() < 5){
return null;
}

return queue.poll();
}

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

Using an size-5 circular buffer:
const int Size = 5;
Node[] buffer = new Node[Size];
int index = 0;
{
buffer[index] = n;
index = (index + 1) % Size;
}
return buffer[index];

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

hey what does one pass here means? does it mean that we can't use recursion?

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

1) Take two pointers both at the start of linklist.
2) Advance one pointer by 5 positions.
3) then advance both the pointers simultaneously until second pointer becomes null.
4) Return first pointer.

{
{cout<<"not enough elements"; return null;}

for (int i=0;i<5&&ptr2!=null;i++)
ptr2=ptr2->next;

if(ptr2==null) {cout<<not enough elements; return null;}

while (ptr2!=null)
{
ptr1=ptr1->next;
ptr2=ptr2->next;
}

return ptr1;

}

Example: A->B->C->D->E->F->G->*(end)

5th from last: C
after loop1
ptr2=F

after loop2
ptr1=c

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

a single pass means , a node can be visited only once.. whether it is single pointer or two pointer..

you are done two pass... first pointer traverse n elements and the second pointer traverse n-5 elements

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

Cobra is right - you have done more than one pass here. Also you have not accounted for the fact that if you don't have enough elements you will return the head, which is not correct either since it is actually not the 5th element from the list. NULL would be a more proper return in that case.

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

Cobra,

Single pass or two pass is said in terms of time taken to do the task. If you are traversing the whole list once and again traverse to find 5th element from tail that is 2 pass. If you use 2 variables, you can traverse the list in 1 pass's time only so this method of using 2 variable is considered as one pass and not two pass.
I hope I made myself clear.

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

@Raj: That's not correct. If you have two variables and you traverse the list once with each of them, that's two passes. It doesn't happen in the time of one pass as you suggested. The logic above isn't considerably faster than doing two passes.

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

One pass means we can traverse the list only once.

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

We can do this in one pass using a pointer and a queue of length 5
pseudo code

``````function 5th_from_tail( head )
s = queue length 5
s = Null
while ptr != Null
ptr = ptr -> next

element = s.pop_from_tail()
if element == Null
return "not enough elements"
else
return element``````

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

we can do this without using a queue. we need to have only two pointer. So, space complexity will be less

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

But as mentioned in the question, space complexity is not the issue. but list should be transversed only once. And using two pointer that can't be done.

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

even with the queue you are doing a two pass, instead of visiting an already visited node using the second pointer, you are visiting it to remove from the end of the queue when queue is full

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

``````list_node * get5thNode()
{
list_node * temp = NULL;
int index = 1;

while(runner->next != NULL)
{
runner = runner->next;
if(index > 5)
{
if(!temp)
else
temp = temp->next;
}
index++;
}
return temp;
}``````

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

But this is not one pass. Using two pointer you are transversing list twice.

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

O(n) solution
General Solution to find nth node from tail

``````public class FifthNodeFromTailLinkedList {
private static final int nthNode = 5;
public static Node getNthNodeFromTail(Node head) {
return null;
}

Node nthTailNode = null;
int count = 0;
while (node != null) {
count ++;
if (count == nthNode) {
break;
}
node = node.getNext();
}

while (node.getNext() != null) {
nthTailNode = nthTailNode.getNext();
node = node.getNext();
}
return nthTailNode;
}

public static void main(String args[]) {
Node node = new Node(1);
node.setNext(new Node(2));
node.getNext().setNext(new Node(3));
node.getNext().getNext().setNext(new Node(4));
node.getNext().getNext().getNext().setNext(new Node(5));
node.getNext().getNext().getNext().getNext().setNext(new Node(6));

System.out.println(getNthNodeFromTail(node).getValue());
}
}

class Node {
private int value;
private Node next;

public Node(int value) {
this.value = value;
}

public int getValue() {
return value;
}

public void setValue(int value) {
this.value = value;
}

public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
}``````

Output:

``2``

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

Using implicit Stack :

``````Lnode* kthFromTail(Lnode* start, int k)
{
static int count =0;
if(!start)
return NULL;

Lnode* end = NULL;
end = kthFromTail(start->next, k);
count++;
if(count==k) end = start;
return end;
}``````

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

/*
* Write a function that would return the 5th element from the
* tail (or end) of a singly linked list of integers, in one pass,
* and then provide a set of test cases against that function
* (please do not use any list manipulation functions that you
* do not implement yourself).
*/
class App {

public static void main(String[] args) {
int arr[] = new int[] { 0, 1, 2, 3, 4, 5, 6 };

int lastLocation = 0;

while (true) {
try {
System.out.println(arr[lastLocation]);

lastLocation = lastLocation + 5;
} catch (ArrayIndexOutOfBoundsException e) {
//System.out.println("arr Out of index: " + lastLocation);
break;
}
}

lastLocation--;

for (int i = 0; i < 5; i++) {
try {
// This sysout statement ensure that same element is not hit
// twice
System.out.println(arr[lastLocation]);
if(lastLocation < 4) {
System.out.println("Array Length less than 5");
break;
}

// System.out.println("Last element of array: "
// + arr[lastLocation]);
System.out.println("5th Last element of array: "
+ arr[lastLocation - 4]);
break;
} catch (ArrayIndexOutOfBoundsException e) {
System.out.println(lastLocation--);
}
}
}
}

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

two pointer and one counter
1) one pointer keep moving till the end, everyone move, counter will increase one
2) when counter is >= Nth (e.g 5), the second pointer will starting pointing from head, since then, every since first pointer move, second pointer will also move
3) when first move till the end of list, return second pointer

``````using System;

namespace ConsoleApplication1
{
class NTHElementFromTailFromList
{
static void Main(string[] args)
{
Node node = new Node
{
value = "1",
next = new Node
{
value = "2",
next = new Node
{
value = "3",
next = new Node
{
value = "4",
next = new Node
{
value = "5",
next = new Node
{
value = "6",
next = new Node
{
value = "7",
next = null
}
}
}
}
}
}
};

Node nTh = FindNthElementTail(node, 2);

Console.WriteLine(nTh);
}

static Node FindNthElementTail(Node n, int nth)
{
Node nThElement = null;
int count = 0;

while (n != null)
{
count++;

if (count >= nth)
{
if (nThElement == null)
{
}
else
{
nThElement = nThElement.next;
}
}

n = n.next;
}

return nThElement;
}
}

class Node
{
public Node next { get; set; }
public string value { get; set; }

public override string ToString()
{
return this.value;
}
}
}``````

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

// maintain two pointers fast and slow

``````ListNode* kthNodeFromEnd(ListNode* head, int k)
{
if (head == NULL) return NULL;
while (--k && fast->next != NULL) fast = fast->next;
if (fast == NULL) return NULL;
while (fast->next != NULL) {
fast = fast->next;
slow = slow->next;
}
return slow;
}``````

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

Do it with tail recursion. Write a recursive function that, given a node in the list, returns the order of that node from the tail.

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

``````{ public static void findpos(LinkedList linkedList,LinkedList.Node head,int n)
{
int length=0;
int i=0;

while (i<n){

temp=temp.next();
i++;
}

while(temp.next() !=null)
{
pos=pos.next();
temp=temp.next();

}

System.out.println("Element at n th from last = "+ n + "  of LinkedList : " + pos.data());

}``````

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

public class NthFromLast {

static class Node {
int value;
Node next;
public Node(int value, Node next) {
this.value = value;
this.next = next;
}
public String toString() {
return String.valueOf(value);
}
}

int counter = 0;
Node nthNode;

public Node getNthNode(Node first, int n) {
getNthNodeRecursive(first, n);
return nthNode;
}

private void getNthNodeRecursive(Node first, int n) {

if(first == null) {
return;
}

if(first.next != null) {
getNthNodeRecursive(first.next, n);
}

counter++;

if(counter == n) {
nthNode = first;
}

}

public static void main(String [] args) {
Node first = new Node(1,
new Node(2, new Node(3, new Node(4, new Node(5, new Node(6, null))))));

NthFromLast n = new NthFromLast();
System.out.println(n.getNthNode(first, 4));
}

}

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

This one is using recursion, single pass and O(1) space. Apologies for the duplicate post.

``````public class NthFromLast {

static class Node {
int value;
Node next;
public Node(int value, Node next) {
this.value = value;
this.next = next;
}
public String toString() {
return String.valueOf(value);
}
}

int counter = 0;
Node nthNode;

public Node getNthNode(Node first, int n) {
getNthNodeRecursive(first, n);
return nthNode;
}

private void getNthNodeRecursive(Node first, int n) {

if(first == null) {
return;
}

if(first.next != null) {
getNthNodeRecursive(first.next, n);
}

counter++;

if(counter == n) {
nthNode = first;
}

}

public static void main(String [] args) {
Node first = new Node(1,
new Node(2, new Node(3, new Node(4, new Node(5, new Node(6, null))))));

NthFromLast n = new NthFromLast();
System.out.println(n.getNthNode(first, 4));
}

}``````

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

1. get the size of the linked list say size
2. calculate size-5 = traverseLength
3. From the head pointer traverse linked list by traverseLength and print the element.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

whats wrong with using something like
current=first
while(current.next.next.next.next.next!=null)
current=current.next;

where next is the next node.

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

errr!!! i think it confusing. I am using current.next.next.next.next.next only as a checking condition
i am incrementing current as current.next.

correct me if i am wrong

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

That doesn't matter. Even if it's a checking condition, you're still traversing 5 nodes every time you do current.next.next.next.next.next

It can't reasonably be considered an approach that only makes a single pass.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

class Node {
Object data;
Node next;
};

{
{
}
else
{
int i = 1;
for(; i<5; i++)
{
if (p1.next != null)
{
p1 = p1.next;
}
}

if (i < 5)
{
throw Exception("Error: elements are less than 5 in the linked list");
}

while (p1.next != null)
{
p1 = p1.next;
p2 = p2.next;
}

return p2;
}

}

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.