AMCAT Automata Question Bank: LRU Cache and Circular Linked List

The AMCAT Automata question bank tests two distinct DSA skills: LRU cache management and sorted circular linked list insertion, both within the same 30-minute coding window.

This set works through both problems from function signature to verified test cases. SHL India, which administers AMCAT through the Automata 2.0 platform, grades each submission on four axes: correctness, time complexity, runtime error handling, and approach quality. For a full overview of the test format and what the grader measures at each difficulty level, see AMCAT Automata: Questions, Answers, and Scoring Criteria.

---

What These Two Problems Test

LRU cache and circular linked list insertion are not arbitrary choices. Both require you to model state correctly over time (or position) and handle boundary conditions that break naive implementations.

The LRU problem is about tracking access order. Every page reference updates the “most recently used” ranking of cache contents. Get the order wrong and your eviction logic picks the wrong victim, producing an incorrect miss count. The circular linked list problem is about traversal logic when there is no sentinel None to stop at. The insertion point depends on one of three structural cases. Missing even one case fails a test batch.

Problem	Function signature	Returns
LRU cache miss count	lruCountMiss(max_cache_size, pages, len)	Number of cache misses (int)
Sorted circular list insertion	insertSortedList(start, n)	Pointer to newly inserted node

The full AMCAT module structure, from Quantitative Ability through Personality Inventory, is in the AMCAT syllabus module-wise guide.

---

Problem 1: LRU Cache Miss Count

The Least Recently Used algorithm removes the item that was accessed least recently when the cache is at capacity and a new item needs to be stored. Your function counts how many times a page is not found in cache across the entire page-reference sequence.

Two terms matter here. A cache hit occurs when the requested page is already in cache; the access order updates but the miss count stays the same. A cache miss occurs when the page is absent; the miss counter increments, and if the cache is full, the least recently used page is evicted before the new one is added.

How the LRU Replacement Policy Works

• Start with an empty cache.
• For each page in the sequence, check whether it is in cache.
• If the page is in cache: hit. Move it to the most-recently-used position. Do not increment the miss counter.
• If the page is not in cache: miss. Increment the counter. If the cache is full, evict the page at the least-recently-used position. Then add the new page at the most-recently-used position.
• Return the total miss count after processing all pages.

Python Implementation

def lru_count_miss(max_cache_size, pages):
    cache = []      # index 0 = LRU, index -1 = MRU
    misses = 0
    for page in pages:
        if page in cache:
            cache.remove(page)
            cache.append(page)      # refresh to MRU
        else:
            misses += 1
            if len(cache) == max_cache_size:
                cache.pop(0)        # evict LRU
            cache.append(page)
    return misses

This runs in O(n times cache_size) time. Adequate for AMCAT-scale inputs; a hash map plus doubly linked list gives O(n) if the grader pushes for it.

Test Case 1 Trace

Input: max_cache_size = 3, pages sequence of 16 elements.

Page	Event	Cache after (LRU → MRU)	Misses
7	Miss	[7]	1
0	Miss	[7, 0]	2
1	Miss	[7, 0, 1]	3
2	Miss, evict 7	[0, 1, 2]	4
0	Hit	[1, 2, 0]	4
3	Miss, evict 1	[2, 0, 3]	5
0	Hit	[2, 3, 0]	5
4	Miss, evict 2	[3, 0, 4]	6
2	Miss, evict 3	[0, 4, 2]	7
3	Miss, evict 0	[4, 2, 3]	8
0	Miss, evict 4	[2, 3, 0]	9
3	Hit	[2, 0, 3]	9
2	Hit	[0, 3, 2]	9
1	Miss, evict 0	[3, 2, 1]	10
2	Hit	[3, 1, 2]	10
0	Miss, evict 3	[1, 2, 0]	11

Total: 11 misses. Confirmed correct.

Test Case 2 Trace

Input: max_cache_size = 2, pages sequence of 9 elements.

Page	Event	Cache after (LRU → MRU)	Misses
2	Miss	[2]	1
3	Miss	[2, 3]	2
1	Miss, evict 2	[3, 1]	3
3	Hit	[1, 3]	3
2	Miss, evict 1	[3, 2]	4
1	Miss, evict 3	[2, 1]	5
4	Miss, evict 2	[1, 4]	6
3	Miss, evict 1	[4, 3]	7
2	Miss, evict 4	[3, 2]	8

Total: 8 misses. Confirmed correct.

---

Problem 2: Sorted Circular Linked List Insertion

A sorted circular linked list keeps its nodes in ascending order, but the last node points back to the first instead of to None. Your function inserts a new integer into the correct position and returns a pointer to the newly inserted node.

The C struct for this problem:

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

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

Three Cases to Handle

Every insertion falls into one of three structural cases. Missing any one of them fails the test batch.

• Case A: Standard insertion. The new value n satisfies curr.value <= n <= curr.next.value for some consecutive pair. Insert the new node between curr and curr.next.
• Case B: Wrap-around insertion. At the point where the list “circles” back, curr.value is the current maximum and curr.next.value is the current minimum. Insert here when n >= curr.value (new maximum) or n <= curr.next.value (new minimum).
• Case C: Empty list. Create a single node that points to itself.

Python Implementation

class CNode:
    def __init__(self, value):
        self.value = value
        self.next = None

def insert_sorted_list(start, n):
    new_node = CNode(n)

    if start is None:
        new_node.next = new_node
        return new_node

    curr = start
    while True:
        # Case A: standard position
        if curr.value <= n <= curr.next.value:
            break
        # Case B: wrap-around point
        if curr.value > curr.next.value:
            if n >= curr.value or n <= curr.next.value:
                break
        curr = curr.next
        if curr == start:
            break   # full circle: insert anywhere (e.g. equal values)

    new_node.next = curr.next
    curr.next = new_node
    return new_node

Test Case 1 Trace

Input list (circular): 3 → 4 → 6 → 1 → 2 → (back to 3). Insert n = 5.

• At node 3: does 3 <= 5 <= 4? No. 3 > 4? No. Move on.
• At node 4: does 4 <= 5 <= 6? Yes. Case A applies. Insert after node 4.
• List after insertion: 3 → 4 → 5 → 6 → 1 → 2 → (back to 3).
• Function returns the new node (value = 5). Traversal from node 5: [5 → 6 → 1 → 2 → 3 → 4 → ^]. Confirmed correct.

Test Case 2 Trace

Input list (circular): 1 → 2 → 3 → 4 → 5 → (back to 1). Insert n = 0.

• At node 1: 1 <= 0 <= 2? No. 1 > 2? No. Move on.
• At node 2: 2 <= 0 <= 3? No. 2 > 3? No. Move on.
• At node 3: 3 <= 0 <= 4? No. 3 > 4? No. Move on.
• At node 4: 4 <= 0 <= 5? No. 4 > 5? No. Move on.
• At node 5: 5 <= 0 <= 1? No. 5 > 1? Yes (wrap-around). 0 >= 5? No. 0 <= 1? Yes. Case B applies. Insert after node 5.
• List after insertion: 5 → 0 → 1 → 2 → 3 → 4 → (back to 5, through 0).
• Function returns the new node (value = 0). Traversal from node 0: [0 → 1 → 2 → 3 → 4 → 5 → ^]. Confirmed correct.

---

What the AMCAT Automata Grader Measures

The automated grader on the AMCAT test portal does not simply check whether your output matches a single expected answer. It evaluates code on four axes simultaneously.

Correctness is split into three tiers: basic test cases (the visible examples in the problem), advanced test cases (variations on the pattern), and boundary cases (empty inputs, single-element lists, cache size of 1). Passing only the basic cases gives a partial score.

Time complexity is inferred from how your solution performs on large inputs. The LRU cache list approach runs in O(n times cache_size); a hash map approach runs in O(n). Both pass at AMCAT scale, but the hash map approach scores higher when the grader measures timing differences on large test inputs.

Runtime errors are scored separately from wrong output. A null pointer dereference in the circular list traversal, or an index out of range in the cache array, costs points independently of whether the algorithm is correct for the cases it does reach.

Approach quality compares your solution structure against known patterns for the problem type. For LRU cache, the list-based simulation and the hash map approach are both recognised. For circular linked list insertion, the three-case while-loop is the expected pattern.

For a breakdown of how AMCAT scores translate to shortlisting thresholds across IT-services companies, see AMCAT test pattern and most repeated questions.

---

The LRU Cache Pattern in AI Systems

The LRU cache pattern you traced above reappears in transformer KV-cache implementations, where models manage which attention keys and values to retain as context grows. In a long-context inference session, the model cannot hold all prior tokens in active memory. It evicts the least recently used attention vectors, using the same replacement logic you just traced through the page-reference sequence. What looks like a placement-prep exercise is the same data structure decision that production AI systems make per inference call.

The 2026 AI roadmap for Indian engineering students covers where cache-layer knowledge fits into the AI engineering hiring stack. TinkerLLM at ₹299 gives you a hands-on environment to build and instrument these patterns directly, without any local setup.