SE-1

Tip 1: Presence of mind
Tip 2: Math
Tip 3: Reasoning

Intuition:

The intuition is to maintain a fixed-size cache of key-value pairs using a doubly linked list and an unordered map. When accessing or adding a key-value pair, it moves the corresponding node to the front of the linked list, making it the most recently used item. This way, the least recently used item is always at the end of the list. When the cache is full and a new item is added, it removes the item at the end of the list (least recently used) to make space for the new item, ensuring the LRU property is maintained.

Explanation:

Node Class:
This is a nested class representing a doubly linked list node.
Each node contains an integer key, an integer value, and pointers to the previous and next nodes in the linked list.
LRUCache Class:
This is the main LRU Cache class.
It has a fixed capacity (cap) that is specified during its instantiation.
It uses an unordered_map named m to store key-value pairs, where the key is the integer key, and the value is a pointer to the corresponding Node.
head and tail Nodes:
The LRUCache class has two dummy nodes: head and tail.
These nodes act as sentinels in the doubly linked list, helping to simplify the edge cases and avoid dealing with null pointers.
head is the first node in the linked list, and tail is the last node.
addNode Function:
This function is used to add a new node to the front of the doubly linked list (right after head).
It takes a Node* newnode as input, representing the node to be added.
The function updates the pointers of the new node, the previous first node, and head to include the new node as the new first node.
deleteNode Function:
This function is used to delete a node from the doubly linked list.
It takes a Node* delnode as input, representing the node to be deleted.
The function updates the pointers of the previous and next nodes to exclude the node to be deleted, effectively removing it from the linked list.
get Function:
This function is used to retrieve a value from the cache based on the given key.
If the key exists in the cache (m.find(key) != m.end()), it retrieves the corresponding node (resNode), extracts its value (ans), and performs the following steps:
Erase the key-value pair from the m unordered map.
Delete the node from its current position in the linked list using deleteNode.
Add the node to the front of the linked list using addNode, making it the most recently used node.
Update the m map to store the key with the most recently used node.
If the key doesn't exist in the cache, it returns -1.
put Function:
This function is used to insert or update a key-value pair in the cache.
If the key already exists in the cache, it updates the value by performing the following steps:
Erase the existing key-value pair from the m unordered map.
Delete the corresponding node from its current position in the linked list using deleteNode.
If the cache is full (i.e., m.size() == cap), it removes the least recently used node from the cache by erasing the key-value pair from the m map and deleting the node from the end of the linked list using deleteNode.
After handling the eviction (if needed), it creates a new node using a new Node(key, value) and adds it to the front of the linked list using addNode.
Finally, it updates the m map to store the key with the newly added node.

Intuition

The intuition behind this code is that it uses a breadth-first search (BFS) algorithm to find the minimum number of moves required to reach the last cell of the board from the first cell. BFS is an algorithm that explores all the vertices of a graph or all the nodes of a tree level by level.

Approach

The method starts by creating a vector of pairs called "cells" that store the row and column of each cell in the board. It also creates a vector of integers called "dist" that stores the minimum number of moves required to reach each cell and initializes it to -1.

It then uses a queue to keep track of the cells to be visited and starts by pushing the first cell (cell 1) into the queue. The method then enters a while loop that continues until the queue is empty. In each iteration of the loop, it takes the front element of the queue, which is the current cell, and pops it from the queue.

For the current cell, the method loops through all the possible next cells which are from curr+1 to min(curr+6,n*n) (because in each move we can move to a dice roll max 6 steps) and checks if the minimum number of moves required to reach that cell has not been assigned yet. If it has not been assigned yet, the method assigns the minimum number of moves required to reach that cell as the minimum number of moves required to reach the current cell plus one. It also pushes the next cell into the queue to be visited in the next iteration.

The method then continues this process until all the cells have been visited, and the minimum number of moves required to reach each cell has been assigned. Finally, the method returns the minimum number of moves required to reach the last cell, which is stored in dist[n*n].

Intuition

The problem is about simulating a queue using two stacks. A queue operates on a First-In-First-Out (FIFO) basis, while a stack operates on a Last-In-First-Out (LIFO) basis. To emulate a queue using two stacks, the idea is to maintain one stack (stack1) for inserting new elements and another stack (stack2) for retrieving elements in the correct order. By only transferring elements between the two stacks when necessary, we can achieve efficient queue operations.

Approach

Push Operation:

Simply push the new element onto stack1. This operation is efficient (O(1)) since no element rearrangement is needed during insertion.
Pop Operation:

If stack2 is not empty, pop the element directly from stack2.
If stack2 is empty, transfer all elements from stack1 to stack2 by popping from stack1 and pushing onto stack2. This effectively reverses the order of elements to match the FIFO order required by the queue.
After the transfer, pop from stack2.
Peek Operation:

Similar to the pop operation: If stack2 is empty, transfer elements from stack1 to stack2 and return the top element from stack2. If stack2 already contains elements, just peek the top without transferring.
Empty Operation:

Return true if both stack1 and stack2 are empty, indicating that the queue has no elements. Push Operation:

Simply push the new element onto stack1. This operation is efficient (O(1)) since no element rearrangement is needed during insertion.
Pop Operation:

If stack2 is not empty, pop the element directly from stack2.
If stack2 is empty, transfer all elements from stack1 to stack2 by popping from stack1 and pushing onto stack2. This effectively reverses the order of elements to match the FIFO order required by the queue.
After the transfer, pop from stack2.
Peek Operation:

Similar to the pop operation: If stack2 is empty, transfer elements from stack1 to stack2 and return the top element from stack2. If stack 2 already contains elements, just peek at the top without transferring.
Empty Operation:

Return true if both stack1 and stack2 are empty, indicating that the queue has no elements.