Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Problem

Submissions

Hints & solutions

Discuss

Kth Movie Member

Easy

0/40

2 upvotes

Problem statement

You are standing in queue to buy the latest Batman movie ticket. You noticed the queue looked like a singly LinkedList.

Each person has some amount of money with them, you are bored, and you want to find the amount of money the person is standing at the ‘Kth’ of the queue from the back.

Check examples for better understanding.

Example :

N = 4,  K = 2  
NODE = 1 -> 2 -> 3 -> 4
In the following example, the 2nd person from the back has ‘3’ units of money.

Detailed explanation ( Input/output format, Notes, Images )

Input Format :

The first line contains an integer ‘T’ denoting the number of test cases. Then each test case follows.
The first line of the test case contains an integer ‘K’.

The second line of the test case contains ‘N + 1’ space-separated where the first 'N' elements represent the LinkedList node. The last integer is always '-1', representing the end of the LinkedList.

Output format :

For each test case, print the amount of money the ‘Kth’ person from the back of the queue has with them.

Note :

You don’t need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10
1 <= K <= N <= 10^5
1 <= HEAD->VAL <= 10^5
Sum of N <= 10^5

Time Limit: 1 sec

Sample Input 1 :

2
3
2 2 2 2 -1
3
4 5 3 1 2 6 -1

Sample Output 1 :

2
1

Explanation Of Sample Input 1 :

For test case 1, 
In the queue, the person from ‘3rd’ last, has ‘2’ units of money.

For test case 2,
In the queue, the person from ‘3rd’ last, has ‘1’ unit of money.

Sample Input 2 :

2
4
3 1 2 2 -1
1
5 5 1 2 1 2 -1

Sample Output 2 :

3
2

Hint 1

Can you use a reference pointer to make an optimal jump in the list queue?

Approaches (1)

Approach 1

Optimal

APPROACH :

We need to find the ‘Kth’ node from the end of our Singly List and its return value.
We will make a reference head, ‘REF_HEAD’, and move it ‘K’ times forward after we reach the ‘Kth’ position.
Now move the main ‘HEAD’ to ‘NEXT’ pointer along with ‘REF_HEAD’ until ‘REF_HEAD’ is not ‘NULL’.
When our ‘REF_HEAD’ reaches the end of our LinkedList, we can say our head is at the ‘Kth’ node from the end.
- As we were already in the ‘K’ position ahead of our main ‘HEAD’, we will make exactly ‘N - K’ moves in the second iteration, so our ‘HEAD’ will reach ‘N - K’th position from the beginning and ‘Kth’ from the end.

ALGORITHM :

Create one List pointer, ‘REF_HEAD’.
Iterate our ‘REF_HEAD’ to the next ‘K’ times.
Now Iterate our ‘HEAD’ and ‘REF_HEAD’ to ‘NEXT’ till ‘REF_HEAD’ is not ‘NULL’.
Return ‘HEAD -> VAL’.

Time Complexity

O(N), where ‘N’ is the size of our linked list ‘HEAD’.

We will iterate over links only once, so total operations are ‘N’.

Space Complexity

O(1)

Constant extra space is required. Hence, the overall Space Complexity is O(1).

(100% EXP penalty)

Kth Movie Member

Shubham Soni

Interview problems

C++ Solution Using Reverse Function✅

List* reverseList(List *head)
{
   if(head==NULL || head->next==NULL)
   {
      return NULL;
   }

   List* forward=NULL;
   List* prev=NULL;
   List* curr=head;

   while(curr!=NULL)
   {
      forward=curr->next;
      curr->next=prev;
      prev=curr;
      curr=forward;
   }

   return prev;
   
}

int kthMoney(List *head , int k) {

   // Write your code here.
   List *head1=reverseList(head);

   List* temp=head1;
   int cnt=0;

   while(temp!=NULL)
   {
      cnt++;

      if(cnt==k)
      {
         return temp->data;
      }

      temp=temp->next;
   }
}

111 views

0 replies

0 upvotes

Codestudio

Discussion thread on Interview Problem | Kth Movie Member

Hey everyone, creating this thread to discuss the interview problem - Kth Movie Member.

Practise this interview question on Coding Ninjas Studio (hyperlinked with the following link): Kth Movie Member

247 views

4 replies

1 upvote

Console