PHP Program to LRU Cache Simulator with Explanation
PHP
Hard
PHP OOP Basics
33 views
1 min read
108 words
This problem helps you practice core PHP fundamentals in a practical way. It builds intuition around get, line, lru. Let’s break it down step by step so you can implement it confidently.
Problem Statement
Capacity c. Commands: PUT k v, GET k. GET prints value or -1. Evict least recently used.
Input Format
First line c q. Next q lines.
Output Format
Outputs for GET.
Constraints
q
Code Solution
This explanation is written for learning purposes and to help beginners understand the concept clearly.
<?php
class Node{
public $k; public $v; public $prev=null; public $next=null;
function __construct($k,$v){ $this->k=$k; $this->v=$v; }
}
class LRU{
private $cap;
private $map=[];
private $head;
private $tail;
function __construct($cap){
$this->cap=$cap;
$this->head=new Node('__H__','');
$this->tail=new Node('__T__','');
$this->head->next=$this->tail;
$this->tail->prev=$this->head;
}
private function remove($node){
$prev=$node->prev;
$next=$node->next;
$prev->next=$next;
$next->prev=$prev;
}
private function addFront($node){
$n=$this->head->next;
$this->head->next=$node; $node->prev=$this->head;
$node->next=$n; $n->prev=$node;
}
function get($k){
if(!isset($this->map[$k])) return null;
$node=$this->map[$k];
$this->remove($node);
$this->addFront($node);
return $node->v;
}
function put($k,$v){
if(isset($this->map[$k])){
$node=$this->map[$k];
$node->v=$v;
$this->remove($node);
$this->addFront($node);
return;
}
$node=new Node($k,$v);
$this->map[$k]=$node;
$this->addFront($node);
if(count($this->map)>$this->cap){
$lru=$this->tail->prev;
$this->remove($lru);
unset($this->map[$lru->k]);
}
}
}
$inputLines=preg_split('/\\R/', rtrim(stream_get_contents(STDIN)));
if(!$inputLines || trim($inputLines[0])==='') exit;
$first=preg_split('/\\s+/', trim($inputLines[0]));
$c=intval($first[0] ?? 0);
$q=intval($first[1] ?? 0);
$cache=new LRU($c);
$output=[];
for($i=1;$i<=$q;$i++){
$tokens=preg_split('/\\s+/', trim($inputLines[$i] ?? ''));
$cmd=$tokens[0] ?? '';
if($cmd==='PUT') $cache->put($tokens[1] ?? '', $tokens[2] ?? '');
else{
$v=$cache->get($tokens[1] ?? '');
$output[] = ($v===null)?'-1':strval($v);
}
}
echo implode(PHP_EOL,$output);
?>
Output Example
Input:
2 6
PUT a 1
PUT b 2
GET a
PUT c 3
GET b
GET c
Common Mistakes
- Misreading input/output format.
- Not handling constraints and edge cases.
- Off-by-one errors in loops.
- Forgetting to reset variables between test cases (if any).
Solution Guide
Problem
Capacity c. Commands: PUT k v, GET k. GET prints value or -1. Evict least recently used.
Input / Output
Input
First line c q. Next q lines.
Examples
Input:
2 6
PUT a 1
PUT b 2
GET a
PUT c 3
GET b
GET c
Details
Common Mistakes
- Misreading input/output format.
- Not handling constraints and edge cases.
- Off-by-one errors in loops.
- Forgetting to reset variables between test cases (if any).
Official Solution
<?php
class Node{
public $k; public $v; public $prev=null; public $next=null;
function __construct($k,$v){ $this->k=$k; $this->v=$v; }
}
class LRU{
private $cap;
private $map=[];
private $head;
private $tail;
function __construct($cap){
$this->cap=$cap;
$this->head=new Node('__H__','');
$this->tail=new Node('__T__','');
$this->head->next=$this->tail;
$this->tail->prev=$this->head;
}
private function remove($node){
$prev=$node->prev;
$next=$node->next;
$prev->next=$next;
$next->prev=$prev;
}
private function addFront($node){
$n=$this->head->next;
$this->head->next=$node; $node->prev=$this->head;
$node->next=$n; $n->prev=$node;
}
function get($k){
if(!isset($this->map[$k])) return null;
$node=$this->map[$k];
$this->remove($node);
$this->addFront($node);
return $node->v;
}
function put($k,$v){
if(isset($this->map[$k])){
$node=$this->map[$k];
$node->v=$v;
$this->remove($node);
$this->addFront($node);
return;
}
$node=new Node($k,$v);
$this->map[$k]=$node;
$this->addFront($node);
if(count($this->map)>$this->cap){
$lru=$this->tail->prev;
$this->remove($lru);
unset($this->map[$lru->k]);
}
}
}
$inputLines=preg_split('/\\R/', rtrim(stream_get_contents(STDIN)));
if(!$inputLines || trim($inputLines[0])==='') exit;
$first=preg_split('/\\s+/', trim($inputLines[0]));
$c=intval($first[0] ?? 0);
$q=intval($first[1] ?? 0);
$cache=new LRU($c);
$output=[];
for($i=1;$i<=$q;$i++){
$tokens=preg_split('/\\s+/', trim($inputLines[$i] ?? ''));
$cmd=$tokens[0] ?? '';
if($cmd==='PUT') $cache->put($tokens[1] ?? '', $tokens[2] ?? '');
else{
$v=$cache->get($tokens[1] ?? '');
$output[] = ($v===null)?'-1':strval($v);
}
}
echo implode(PHP_EOL,$output);
?>
Solutions (0)
No solutions submitted yet. Be the first!
