Software Developer

The idea is to use a recursive approach to find the given key and then remove that node. The recursive idea is very clear that we will traverse through the circular linked list, and we will check if the value of the node is equal to the given key. 
 

We will define a function deleteNodeHelper(root, key, head) to remove the key in which the head is the starting node of the linked list, and we will send root as the next node of the head node.   
 

Working of the Recursive function: 

1. If the root is equal to head, then we have traversed the whole linked list and have not found the given key. So, we will return head. This will act as the base case of the recursive function.
2. We will check if the value of the node is equal to the key. We have found the node with the given key, and we have to remove this node. So, we will return the next node of the root.
3. Now, we have to make a recursive call to check all nodes of the remaining linked list. We will set the next node of the root as deleteNodehelper(next, key, head), where next is equal to the next node of root.
4. In the end, we will return the current node root.

Approach: According to LRU, if the page we need is not present in the set of pages, the page fault occurs, and we replace the least recently used page with the current page. And if the page is present, we just use it, and no page fault occurs.

Algorithm: 

• Create a variable ‘ans’ and initialize it to 0.
• Create an empty vector ‘currentPages’.
• Iterate using a for loop from i = ‘0’ to ‘N - 1’.
  • If Pages[i] in ‘currentPages’.
    • Remove Pages[i] from ‘currentPages’.
    • Append Pages[i] to ‘currentPages’.
  • Else.
    • Increment ‘ans’ by 1.
    • If currentPages.size() == C.
      • Remove currentPages[0] from ‘currentPages’.
    • Append Pages[i] to ‘currentPages’.
• Print ‘ans’.

Floyd's algorithm can be used to solve this question.
Define two pointers slow and fast. Both point to the head node, fast is twice as fast as slow. There will be no cycle if it reaches the end. Otherwise, it will eventually catch up to the slow pointer somewhere in the cycle.
Let X be the distance from the first node to the node where the cycle begins, and let X+Y be the distance the slow pointer travels. To catch up, the fast pointer must travel 2X + 2Y. L is the cycle size. The total distance that the fast pointer has travelled over the slow pointer at the meeting point is what we call the full cycle.
X+Y+L = 2X+2Y
L=X+Y
Based on our calculation, slow pointer had already traveled one full cycle when it met fast pointer, and since it had originally travelled A before the cycle began, it had to travel A to reach the cycle's beginning! 
After the two pointers meet, fast pointer can be made to point to head. And both slow and fast pointers are moved till they meet at a node. The node at which both the pointers meet is the beginning of the loop.
Pseudocode :
detectCycle(Node *head) {
Node *slow=head,*fast=head;

while(slow!=NULL && fast!=NULL && fast->next!=NULL) {

slow = slow->next; 
fast = fast->next->next; 

if(slow==fast) 
{
fast = head;
while(slow!=fast) 
{

slow = slow->next;
fast=fast->next;
}
return slow;

}

}

return NULL; }

Concept of sorting can be applied here.
1. Sort the array.
2. Maintain two indexes one at beginning (l=0) and one at end (r=n-1). 
3. Now, traverse the array until l 3.1 Calculate sum of arr[l] + arr[r]
3.2 if abs (sum) < abs (minimum sum), then update the minimum sum and pair.
3.3 If sum < 0, this means if we want to find sum close to 0, do l++
3.4 If sum is greater than 0,this means if we want to find sum close to 0 , do r--.
The minimum sum will store the sum closest to zero. 

Time Complexity : O(nlogn)