Find Nth Node from End of the Singly linked list.

-
Given N size node in the Singly Linked list and you have to find the kth node's value from the end. 
Suppose, You have been provided the above Singly Linked List and the interviewer asks you to return 2nd last element from the linked list. Your response will be 7 and if the kth element is greater than the size of the Linked list then return -1. -1 will represent that the kth element is not present.

This problem is repeatedly asked by many of the product based companies and the interviewer will grill you on it. He will add some constraint on the fly and asks you to solve it optimize way.
Suppose, If we are going to solve this problem what would be the solution that comes into our mind. A Singly linked list holds the count of the node in the size variable, We will iterate from the head node to size - kth node and return the kth node's value. Once you give this solution to the interviewer, he/she will directly tell you that there is no size variable available in this custom Singly linked list. 
We are now trying to solve it by using a dynamic array and store each node value in a particular index. We can directly fetch the value with the help of the array's index and return the result. Once you give this solution to the interviewer, he/she will ask you to write a solution without any extra space.
We are puzzled sometimes because of the interview pressure and solution doesn't hit at the right time. We can do this with the help of the two pointers/references of a Linked List class. The first reference will move k time and then they move together. When the first reference reaches at the end of the node and the second reference is exactly on the kth node. That's how we do it. 
public int get(Node head, int n) {
    if (head == null)
        return -1;
    Node ref = head, fastRef = head;
    while (n-- > 0){
        if (fastRef == null)
            return -1;
        else
            fastRef = fastRef.next;
    }
    while (fastRef != null) {
        ref = ref.next;
        fastRef = fastRef.next;
    }
    return ref.value;
}
I hope you understood the solution to the given problem. We will come up with a new challenge soon.

Comments

Post a Comment

Popular posts from this blog

Recursion

-
Image
The process in which a function calls itself and only works where we call the same operation multiple times with different inputs. In every call, we try to make the problem smaller. There must be a base case where the system will stop the recursion and give you a result back. It internally stores the recursion state in the method call stack. If there is no base condition in the recursion method then it will go into an infinite loop and you might face the StackOverflow Exception . There are several types of recursion:- Head Recursion Tail Recursion Tree Recursion Nested Recursion Head Recursion It will call recursively first then at the end do all the computation. private static int factorial( int number) { return (number== 1 )? number : number* factorial (number- 1 ) ; } factorial(5) (5* factorial(5-1)) (5* (4* factorial(4-1)) (5* (4* (3*factorial(3-1))) (5* (4* (3* (2*factorial(2-1)))) (5* (4* (3* (2* (1*1))))) output = 120 Tail Recur
Read more

Priority Queue

-
A priority queue is an abstract data structure and it is similar to the regular queue . Each element in the priority queue has a priority associated with it. In the priority queue, we dequeue the highest priority element before the lowest priority and if the priority is the same then as per the insertion order it will dequeue. One of the best real-time applications, CPU Scheduling is basically done the same thing. If the higher priority task occurs then it interrupts the ongoing process and shares the resources to the higher priority. We have taken the example of RabbitMq in the queue blog . In RabbitMq, we push elements in the queue and wait until the subscriber subscribes to the messages. Suppose, If there are n messages that are pending to subscribe and one of the messages needs to be processed as soon as possible. If we have pushed the message by setting the high priority in the queue then it will process first then rest of them. Some of the languages implement the priority queue
Read more