LRU Cache Algorithm & Circular Linked List Insertion Guide

Introduction

Understanding the Least Recently Used (LRU) cache algorithm is essential for acing technical interviews. This guide covers the implementation of LRU cache and a function to insert an integer into a sorted circular linked list. We will also provide test cases and explanations to solidify your understanding.

LRU Cache Algorithm

Problem Statement

The Least Recently Used (LRU) cache algorithm removes the least recently used element when the cache is full. If a requested element is not found in the cache, it results in a cache miss. Your task is to implement a function that calculates the number of cache misses for a given list of integers.

Function Signature

int lruCountMiss(int max_cache_size, int *pages, int len);

Test Cases

Test Case 1:

Input:

max_cache_size = 3
pages = [7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0]
len = 16

Expected Output:

11

Test Case 2:

Input:

max_cache_size = 2
pages = [2,3,1,3,2,1,4,3,2]
len = 9

Expected Output:

8

Explanation

Each time an element is not found in the cache, a cache miss occurs. The cache follows the Least Recently Used replacement policy to manage entries efficiently.

Inserting an Integer into a Sorted Circular Linked List

Problem Statement

Write a function to insert an integer into a circular linked list where elements are sorted in ascending order. The function should return a pointer to the newly inserted node.

Function Signature

struct CNode {
    int value;
    CNode* next;
};

CNode* insertSortedList(CNode* start, int n);

Test Cases

Test Case 1:

Input:

List: [3 → 4 → 6 → 1 → 2 → ^]
n = 5

Expected Output:

[5 → 6 → 1 → 2 → 3 → 4 → ^]

Test Case 2:

Input:

List: [1 → 2 → 3 → 4 → 5 → ^]
n = 0

Expected Output:

[0 → 1 → 2 → 3 → 4 → 5 → ^]

Explanation

The new node should be inserted in the correct position while maintaining the sorted order. If the list is empty, the new node should become the head.

Conclusion

Mastering the LRU cache algorithm and linked list operations is crucial for technical interviews. By understanding these concepts and practicing their implementation, you will be well-prepared to tackle similar problems efficiently.