Top Interview Questions [letcode]

letcode_top_interview_questions.php

<?php

/**
 * My solutions for the "Top Interview Questions" on the leetcode
 */
class SolutionTopInterviewQuestions
{
    //<editor-fold desc="Array block">
    /**
     * Remove Duplicates from Sorted Array
     * https://leetcode.com/explore/featured/card/top-interview-questions-easy/92/array/727/
     *
     * @param int[] $nums
     *
     * @return int
     */
    public function removeDuplicates(&$nums): int
    {
        $nums = array_unique($nums);

        return count($nums);
    }

    /**
     * Best Time to Buy and Sell Stock II
     * https://leetcode.com/explore/interview/card/top-interview-questions-easy/92/array/564/
     *
     * @param int[] $prices
     *
     * @return int
     */
    public function maxProfit(array $prices): int
    {
        $maxProfit = 0;
        $valley = $prices[0];
        $peak = $prices[0];

        for ($i = 1, $iMax = count($prices); $i < $iMax; $i++) {
            if ($prices[$i] >= $prices[$i - 1]) {
                $peak = $prices[$i];

                // If the last price is a peak value.
                if ($i === count($prices) - 1) {
                    $maxProfit += $peak - $valley;
                }
            } else {
                $maxProfit += $peak - $valley;
                // New transaction should start from ith day.
                $valley = $prices[$i];
                $peak = $valley;
            }
        }

        return $maxProfit;
    }

    /**
     * Rotate Array
     * https://leetcode.com/explore/interview/card/top-interview-questions-easy/92/array/646/
     *
     * @param int[] $nums
     * @param int   $k
     *
     * @return void
     */
    public function rotate(array &$nums, int $k): void
    {
        if ($k !== 0 && count($nums) >= 2) {
            for ($i = 0, $iMax = count($nums); $i < $iMax; $i++) {
                $newIndex = ($i + $k) % count($nums);
                $res[$newIndex] = $nums[$i];
            }

            //assign back to original array
            for ($i = 0, $iMax = count($nums); $i < $iMax; $i++) {
                $nums[$i] = $res[$i];
            }
        }
    }

    /**
     * Contains Duplicate
     * https://leetcode.com/explore/interview/card/top-interview-questions-easy/92/array/578/
     *
     * @param int[] $nums
     *
     * @return bool
     */
    public function containsDuplicate(array $nums): bool
    {
        return count($nums) !== count(array_unique($nums));
    }

    /**
     * Single Number
     * https://leetcode.com/explore/interview/card/top-interview-questions-easy/92/array/549/
     *
     * @param int[] $nums
     *
     * @return int
     */
    public function singleNumber(array $nums): int
    {
        return array_flip(array_count_values($nums))[1];
    }

    /**
     * Plus One
     * https://leetcode.com/explore/interview/card/top-interview-questions-easy/92/array/559/
     *
     * @param int[] $digits
     *
     * @return int[]
     */
    public function plusOne(array $digits)
    {
        return str_split(bcadd(implode('', $digits), 1));
    }

    /**
     * Two Sum
     * https://leetcode.com/explore/interview/card/top-interview-questions-easy/92/array/546/
     *
     * @param int[] $nums
     * @param int   $target
     *
     * @return int[]
     */
    public function twoSum(array $nums, int $target): array
    {
        $num1 = 0;
        $num2 = 1;

        foreach ($nums as $key1 => $value1) {
            $num1 = $key1;

            foreach ($nums as $key2 => $value2) {
                if ($key1 === $key2) {
                    continue;
                }

                $num2 = $key2;
                if ($value1 + $value2 === $target) {
                    break 2;
                }
            }
        }

        return [$num1, $num2];
    }

    /**
     * Intersection of Two Arrays II
     * https://leetcode.com/explore/interview/card/top-interview-questions-easy/92/array/674/
     *
     * @param int[] $nums1
     * @param int[] $nums2
     *
     * @return int[]
     */
    public function intersect(array $nums1, array $nums2): array
    {
        $result = [];
        foreach ($nums1 as $num) {
            if (($key = array_search($num, $nums2)) !== false) {
                $result[] = $num;

                unset($nums2[$key]);
            }
        }

        return $result;
    }

    /**
     * Move Zeroes
     * https://leetcode.com/explore/interview/card/top-interview-questions-easy/92/array/567/
     *
     * @param Integer[] $nums
     *
     * @return void
     */
    public function moveZeroes(array &$nums): void
    {
        foreach ($nums as $i => $iValue) {
            if ($iValue === 0) {
                unset($nums[$i]);
                $nums[] = 0;
            }
        }
    }

    /**
     * Rotate Image
     * https://leetcode.com/explore/interview/card/top-interview-questions-easy/92/array/770/
     *
     * @param int[][] $matrix
     *
     * @return void
     */
    public function rotateImage(array &$matrix): void
    {
        $reverseMatrix = array_reverse($matrix);
        foreach ($matrix as $matrixKey => $matrixValue) {
            foreach ($reverseMatrix as $reverseKey => $reverseValue) {
                $matrix[$matrixKey][$reverseKey] = $reverseValue[$matrixKey];
            }
        }
    }

    /**
     * Valid Sudoku
     * https://leetcode.com/explore/interview/card/top-interview-questions-easy/92/array/769/
     *
     * @param String[][] $board
     *
     * @return bool
     */
    public function isValidSudoku(array $board): bool
    {
        if ((count($board)) !== 9) {
            return false;
        }

        $isValidFn = static function ($array) {
            $clearArray = array_filter($array, static fn($x) => $x !== '.');

            return count($clearArray) === count(array_unique($clearArray));
        };

        for ($i = 0, $iMax = 9; $i < $iMax; $i++) {
            // check row
            if (!$isValidFn($board[$i])) {
                return false;
            }

            // check column
            $column = [];
            for ($iColumn = 0, $iMaxColumn = 9; $iColumn < $iMaxColumn; $iColumn++) {
                $column[] = $board[$iColumn][$i];
            }

            if (!$isValidFn($column)) {
                return false;
            }
        }

        // check 3x3
        for ($i = 0, $iMax = 9; $i < $iMax; $i += 3) {
            for ($iBox = 0, $iBoxMax = 9; $iBox < $iBoxMax; $iBox += 3) {
                $box3x3 = [
                    $board[$i][$iBox],     $board[$i][$iBox + 1],     $board[$i][$iBox + 2],
                    $board[$i + 1][$iBox], $board[$i + 1][$iBox + 1], $board[$i + 1][$iBox + 2],
                    $board[$i + 2][$iBox], $board[$i + 2][$iBox + 1], $board[$i + 2][$iBox + 2]
                ];

                if (!$isValidFn($box3x3)) {
                    return false;
                }
            }
        }

        return true;
    }
    //</editor-fold>
    //<editor-fold desc="Strings block">
    /**
     * Reverse String
     * https://leetcode.com/explore/interview/card/top-interview-questions-easy/127/strings/879/
     *
     * @param String[] $s
     */
    public function reverseString(array &$s): void
    {
        $s = array_reverse($s);
    }

    /**
     * Reverse Integer
     * https://leetcode.com/explore/interview/card/top-interview-questions-easy/127/strings/880/
     *
     * @param int $x
     *
     * @return int
     */
    public function reverse(int $x): int
    {
        $result = (int)strrev(ltrim($x, "-"));
        if ($x < 0) {
            $result *= -1;
        }

        // 32-bit integer range only
        if ($result > (2 ** 31) - 1 || $result < (2 ** 31) * -1) {
            return 0;
        }

        return $result;
    }

    /**
     * First Unique Character in a String
     * https://leetcode.com/explore/interview/card/top-interview-questions-easy/127/strings/881/
     *
     * @param string $s
     *
     * @return int
     */
    public function firstUniqChar(string $s): int
    {
        for ($i = 0, $iMax = strlen($s); $i < $iMax; $i++) {
            if (substr_count($s, $s[$i]) === 1) {
                return $i;
            }
        }

        return -1;
    }

    /**
     * Valid Anagram
     * https://leetcode.com/explore/interview/card/top-interview-questions-easy/127/strings/882/
     *
     * @param string $s
     * @param string $t
     *
     * @return bool
     */
    public function isAnagram(string $s, string $t): bool
    {
        return count_chars($s, 1) === count_chars($t, 1);
    }

    /**
     * Valid Palindrome
     * https://leetcode.com/explore/interview/card/top-interview-questions-easy/127/strings/883/
     *
     * @param string $s
     *
     * @return bool
     */
    public function isPalindrome(string $s): bool
    {
        $tmp = preg_replace("/[^a-z0-9]+/i", "", strtolower($s));

        return $tmp === strrev($tmp);
    }

    /**
     * String to Integer (atoi)
     * https://leetcode.com/explore/interview/card/top-interview-questions-easy/127/strings/884/
     *
     * @param string $str
     *
     * @return int
     */
    public function myAtoi(string $str): int
    {
        $result = (int) str_replace('e', 'x', trim($str));

        if ($result === 0) {
            return $result;
        }

        if ($result > (2 ** 31) - 1) {
            return (2 ** 31) - 1;
        }

        if ($result < (2 ** 31) * -1) {
            return (2 ** 31) * -1;
        }

        return $result;
    }

    //</editor-fold>
}