Data Structures & Algorithms

<?php
$data = range(0, 999_999);
$target = 999_999;

$linearSteps = 0;
foreach ($data as $x) {
    $linearSteps++;
    if ($x === $target) break;
}

$binarySteps = 0;
$lo = 0;
$hi = count($data) - 1;
while ($lo <= $hi) {
    $binarySteps++;
    $mid = intdiv($lo + $hi, 2);
    if ($data[$mid] === $target) break;
    if ($data[$mid] < $target) $lo = $mid + 1;
    else $hi = $mid - 1;
}

echo "Linear search: $linearSteps steps\n";
echo "Binary search: $binarySteps steps\n";

<?php
$list = [10, 20, 30];
$list[] = 40;
echo count($list), "\n";

unset($list[1]);
var_dump(array_is_list($list));
echo json_encode($list), "\n";

$list = array_values($list);
var_dump(array_is_list($list));
echo json_encode($list), "\n";

<?php
$seen = [];
foreach (['php', 'sql', 'php', 'docker', 'sql'] as $tag) {
    $seen[$tag] = true;
}
echo implode(', ', array_keys($seen)), "\n";
var_dump(isset($seen['docker']), isset($seen['redis']));

$counts = array_count_values(explode(' ', 'the cat and the hat and the bat'));
arsort($counts);
foreach ($counts as $word => $n) {
    echo "$word: $n\n";
}

<?php
final class Stack
{
    private array $items = [];

    public function push(mixed $x): void { $this->items[] = $x; }

    public function pop(): mixed
    {
        if ($this->items === []) throw new UnderflowException('pop from empty stack');
        return array_pop($this->items);
    }

    public function peek(): mixed { return $this->items[array_key_last($this->items)] ?? null; }
    public function isEmpty(): bool { return $this->items === []; }
}

$s = new Stack();
foreach (['a', 'b', 'c'] as $x) $s->push($x);
echo $s->peek(), "\n";
while (!$s->isEmpty()) echo $s->pop(), ' ';
echo "\n";

try {
    $s->pop();
} catch (UnderflowException $e) {
    echo 'Error: ', $e->getMessage(), "\n";
}

<?php
function balanced(string $s): bool
{
    $pairs = [')' => '(', ']' => '[', '}' => '{'];
    $stack = new SplStack();
    foreach (str_split($s) as $ch) {
        if (in_array($ch, $pairs, true)) {
            $stack->push($ch);
        } elseif (isset($pairs[$ch])) {
            if ($stack->isEmpty() || $stack->pop() !== $pairs[$ch]) return false;
        }
    }
    return $stack->isEmpty();
}

foreach (['{[()]}', '([)]', '((', 'f(x[0])'] as $s) {
    echo str_pad($s, 8), ' ', balanced($s) ? 'yes' : 'no', "\n";
}

<?php
$q = new SplQueue();
foreach (['order-1', 'order-2', 'order-3'] as $job) {
    $q->enqueue($job);
}
echo 'waiting: ', count($q), "\n";

while (!$q->isEmpty()) {
    $job = $q->dequeue();
    echo "processing $job\n";
    if ($job === 'order-1') {
        $q->enqueue('order-1-retry');
    }
}

<?php
$n = 20_000;

$q = range(1, $n);
$start = hrtime(true);
while ($q) array_shift($q);
$shiftMs = (hrtime(true) - $start) / 1e6;

$spl = new SplQueue();
foreach (range(1, $n) as $x) $spl->enqueue($x);
$start = hrtime(true);
while (!$spl->isEmpty()) $spl->dequeue();
$splMs = (hrtime(true) - $start) / 1e6;

echo $shiftMs > $splMs * 5 ? "array_shift is much slower\n" : "about the same\n";

<?php
final class Node
{
    public function __construct(public int $value, public ?Node $next = null) {}
}

final class LinkedList
{
    private ?Node $head = null;

    public function pushFront(int $v): void { $this->head = new Node($v, $this->head); }

    public function append(int $v): void
    {
        if ($this->head === null) { $this->head = new Node($v); return; }
        $cur = $this->head;
        while ($cur->next !== null) $cur = $cur->next;
        $cur->next = new Node($v);
    }

    public function reverse(): void
    {
        $prev = null;
        $cur = $this->head;
        while ($cur !== null) {
            $next = $cur->next;
            $cur->next = $prev;
            $prev = $cur;
            $cur = $next;
        }
        $this->head = $prev;
    }

    public function __toString(): string
    {
        $parts = [];
        for ($n = $this->head; $n !== null; $n = $n->next) $parts[] = $n->value;
        return implode(' -> ', $parts) ?: '(empty)';
    }
}

$list = new LinkedList();
$list->append(2);
$list->append(3);
$list->pushFront(1);
echo $list, "\n";
$list->reverse();
echo $list, "\n";

<?php
function sumDigits(int $n): int
{
    if ($n < 10) return $n;              // base case
    return $n % 10 + sumDigits(intdiv($n, 10));
}

function fib(int $n, array &$memo = []): int
{
    if ($n <= 1) return $n;
    return $memo[$n] ??= fib($n - 1, $memo) + fib($n - 2, $memo);
}

echo sumDigits(98_765), "\n";
echo fib(10), "\n";
echo fib(90), "\n";

<?php
function flatten(array $items): array
{
    $out = [];
    foreach ($items as $item) {
        if (is_array($item)) {
            array_push($out, ...flatten($item));
        } else {
            $out[] = $item;
        }
    }
    return $out;
}

echo json_encode(flatten([1, [2, [3, [4]], 5], [], 6])), "\n";

<?php
final class TreeNode
{
    public ?TreeNode $left = null;
    public ?TreeNode $right = null;
    public function __construct(public int $value) {}
}

function insert(?TreeNode $node, int $v): TreeNode
{
    if ($node === null) return new TreeNode($v);
    if ($v < $node->value) $node->left = insert($node->left, $v);
    elseif ($v > $node->value) $node->right = insert($node->right, $v);
    return $node;
}

function contains(?TreeNode $node, int $v): bool
{
    while ($node !== null) {
        if ($v === $node->value) return true;
        $node = $v < $node->value ? $node->left : $node->right;
    }
    return false;
}

function inOrder(?TreeNode $node, array &$out): void
{
    if ($node === null) return;
    inOrder($node->left, $out);
    $out[] = $node->value;
    inOrder($node->right, $out);
}

function height(?TreeNode $node): int
{
    return $node === null ? 0 : 1 + max(height($node->left), height($node->right));
}

$root = null;
foreach ([50, 30, 70, 20, 40, 60, 80] as $v) $root = insert($root, $v);

$sorted = [];
inOrder($root, $sorted);
echo implode(' ', $sorted), "\n";
var_dump(contains($root, 60), contains($root, 65));
echo 'height: ', height($root), "\n";

$chain = null;
foreach ([1, 2, 3, 4, 5, 6, 7] as $v) $chain = insert($chain, $v);
echo 'height after sorted inserts: ', height($chain), "\n";

<?php
$heap = new SplMinHeap();
foreach ([42, 7, 19, 3, 25] as $x) $heap->insert($x);
echo 'smallest: ', $heap->top(), "\n";

$out = [];
while (!$heap->isEmpty()) $out[] = $heap->extract();
echo implode(' ', $out), "\n";

$tasks = new SplPriorityQueue();
$tasks->insert('write tests', 2);
$tasks->insert('fix production bug', 10);
$tasks->insert('update README', 1);
$tasks->insert('review pull request', 5);
while (!$tasks->isEmpty()) echo $tasks->extract(), "\n";

<?php
function topK(iterable $values, int $k): array
{
    $heap = new SplMinHeap();
    foreach ($values as $v) {
        if (count($heap) < $k) {
            $heap->insert($v);
        } elseif ($v > $heap->top()) {
            $heap->extract();
            $heap->insert($v);
        }
    }
    $out = iterator_to_array($heap, false);
    rsort($out);
    return $out;
}

echo implode(', ', topK([5, 91, 17, 64, 3, 88, 42, 70], 3)), "\n";

<?php
$graph = [
    'home'    => ['blog', 'tools'],
    'blog'    => ['post-a', 'post-b'],
    'tools'   => ['ats'],
    'post-a'  => ['ats'],
    'post-b'  => [],
    'ats'     => ['pricing'],
    'pricing' => [],
];

function shortestPath(array $graph, string $from, string $to): ?array
{
    $queue = new SplQueue();
    $queue->enqueue($from);
    $cameFrom = [$from => null];
    while (!$queue->isEmpty()) {
        $node = $queue->dequeue();
        if ($node === $to) {
            $path = [];
            for ($n = $to; $n !== null; $n = $cameFrom[$n]) array_unshift($path, $n);
            return $path;
        }
        foreach ($graph[$node] as $next) {
            if (!array_key_exists($next, $cameFrom)) {
                $cameFrom[$next] = $node;
                $queue->enqueue($next);
            }
        }
    }
    return null;
}

function dfs(array $graph, string $node, array &$seen = []): array
{
    $seen[$node] = true;
    foreach ($graph[$node] as $next) {
        if (!isset($seen[$next])) dfs($graph, $next, $seen);
    }
    return array_keys($seen);
}

echo implode(' -> ', shortestPath($graph, 'home', 'pricing')), "\n";
echo implode(', ', dfs($graph, 'home')), "\n";
var_dump(shortestPath($graph, 'pricing', 'home'));

<?php
function lowerBound(array $sorted, int $target): int
{
    $lo = 0;
    $hi = count($sorted);
    while ($lo < $hi) {
        $mid = intdiv($lo + $hi, 2);
        if ($sorted[$mid] < $target) $lo = $mid + 1;
        else $hi = $mid;
    }
    return $lo;
}

$prices = [5, 9, 9, 14, 20, 31];
foreach ([9, 10, 1, 40] as $t) {
    $i = lowerBound($prices, $t);
    $found = ($prices[$i] ?? null) === $t ? 'found' : 'not found';
    echo "$t -> index $i ($found)\n";
}

<?php
function mergeSort(array $a): array
{
    if (count($a) <= 1) return $a;
    $mid = intdiv(count($a), 2);
    $left = mergeSort(array_slice($a, 0, $mid));
    $right = mergeSort(array_slice($a, $mid));

    $out = [];
    $i = $j = 0;
    while ($i < count($left) && $j < count($right)) {
        $out[] = $left[$i] <= $right[$j] ? $left[$i++] : $right[$j++];
    }
    return [...$out, ...array_slice($left, $i), ...array_slice($right, $j)];
}

echo implode(' ', mergeSort([38, 27, 43, 3, 9, 82, 10])), "\n";

<?php
$people = [
    ['name' => 'Ravi', 'dept' => 'data', 'salary' => 90],
    ['name' => 'Ana',  'dept' => 'web',  'salary' => 75],
    ['name' => 'Chen', 'dept' => 'data', 'salary' => 120],
    ['name' => 'Bola', 'dept' => 'web',  'salary' => 75],
];

// dept ascending, then salary descending
usort($people, fn($a, $b) => [$a['dept'], $b['salary']] <=> [$b['dept'], $a['salary']]);

foreach ($people as $p) {
    printf("%-5s %-4s %d\n", $p['name'], $p['dept'], $p['salary']);
}

<?php
// dp[a] = fewest coins that make amount a
function minCoins(array $coins, int $amount): int
{
    $dp = array_fill(0, $amount + 1, PHP_INT_MAX);
    $dp[0] = 0;
    for ($a = 1; $a <= $amount; $a++) {
        foreach ($coins as $c) {
            if ($c <= $a && $dp[$a - $c] !== PHP_INT_MAX) {
                $dp[$a] = min($dp[$a], $dp[$a - $c] + 1);
            }
        }
    }
    return $dp[$amount] === PHP_INT_MAX ? -1 : $dp[$amount];
}

echo minCoins([1, 5, 10, 25], 63), "\n";
echo minCoins([1, 3, 4], 6), "\n";
echo minCoins([5, 10], 3), "\n";

<?php
// dp[i][j] = length of the longest common subsequence of a[0..i) and b[0..j)
function lcs(string $a, string $b): int
{
    $m = strlen($a);
    $n = strlen($b);
    $dp = array_fill(0, $m + 1, array_fill(0, $n + 1, 0));
    for ($i = 1; $i <= $m; $i++) {
        for ($j = 1; $j <= $n; $j++) {
            $dp[$i][$j] = $a[$i - 1] === $b[$j - 1]
                ? $dp[$i - 1][$j - 1] + 1
                : max($dp[$i - 1][$j], $dp[$i][$j - 1]);
        }
    }
    return $dp[$m][$n];
}

echo lcs('ABCBDAB', 'BDCABA'), "\n";
echo lcs('kitten', 'sitting'), "\n";