Task 1: Smallest Multiple
Write a script to accept a positive number N and print the smallest multiple of N consisting only of digits 0 and 1.
Example Output
Input: 55
Output: 110
Logic
Perform a Breadth-First Search (BFS) over remainder modulo N to find the shortest string representation containing only 0 and 1 that results in a remainder of 0.
Perl Solution
ch-1.pl
sub find_multiple_0_1 {
my $input = shift;
my $count = 0;
while ($input !~ /^[01]+$/) {
$input += $input;
return -1 if $count == 1000;
$count++;
}
return $input;
}
Python Solution
ch-1.py
def smallest_multiple_01(n: int) -> str:
start = 1 % n
if start == 0:
return "1"
parent = {start: -1}
digit = {start: "1"}
q = deque([start])
while q:
r = q.popleft()
for d in ("0", "1"):
nr = (r * 10 + (1 if d == "1" else 0)) % n
if nr in parent:
continue
parent[nr] = r
digit[nr] = d
if nr == 0:
out = []
cur = nr
while cur != -1:
out.append(digit[cur])
cur = parent[cur]
return "".join(reversed(out))
q.append(nr)
Task 2: LRU Cache
Write a script to demonstrate LRU (Least Recently Used) Cache feature, supporting `get` and `set` operations with a defined capacity.
Logic
Use an ordered structure (like Cache::LRU in Perl or OrderedDict in Python) to keep track of access order. Move recently accessed keys to the end and discard the oldest keys when capacity is exceeded.
Perl Solution
ch-2.pl
use Cache::LRU;
my $cache = Cache::LRU->new(
size => $size
);
$cache->set(1=>3);
$cache->set(2=>5);
$cache->get(2); # returns 5
Python Solution
ch-2.py
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity: int):
self._capacity = capacity
self._data = OrderedDict()
def get(self, key):
if key not in self._data:
return None
self._data.move_to_end(key)
return self._data[key]
def set(self, key, value):
if key in self._data:
self._data.move_to_end(key)
self._data[key] = value
if len(self._data) > self._capacity:
self._data.popitem(last=False)