/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val = 0, $next = null) {
 *         $this->val = $val;
 *         $this->next = $next;
 *     }
 * }
 */
class Solution {

    /**
     * @param ListNode $l1
     * @param ListNode $l2
     * @return ListNode
     */
    function addTwoNumbers($l1, $l2) {
        $ans = new ListNode(0, null);
        $p = $l1;
        $q = $l2;
        $current = $ans;
        $carry=0;

        while ($p != null || $q != null) {
            $x = isset($p) ? $p->val : 0;
            $y = isset($q) ? $q->val : 0;
            $sum = $carry + $x + $y;
            $carry = (int) ($sum/10);
            $current->next = new ListNode($sum%10);
            $current = $current->next;
            if ($p != null) $p = $p->next;
            if ($q != null) $q = $q->next;
        }
        if ($carry > 0) {
            $current->next = new ListNode($carry);
        }

        return $ans->next;
    }
}

# get running docker containers
docker ps

# get all docker containers including those that have exited
docker ps -a

# stop container by its id or name
docker stop first_few_chars_of_id

# list docker images stored on the host
docker images

# remove image
docker rmi image_name

# download a new image
docker pull image_name
docker pul image_name:specific_tag

# append a command
docker run image_name command to run with parameters
docker run ubuntu sleep 5

# execute command in a conatiner
docker exec container_id cat /etc/hosts

# interactive session inside container
docker exec -it conatiner_id /bin/bash

# run container in background/daemon mode
docker run -d webapp

# tail logs
docker logs -f conatiner_id

# attach to conatiner running in detach/daemon mode
docker attach container_id

# map ports, for example, to map port 80 on host to port 8080 in container
dokcer run -p 80:8080 webapp

/**
 * @param {number} x
 * @return {number}
 */
var reverse = function(x) {

    let ans = '';
    if (x<0) {
        ans = '-';
        x*=-1;
    }

    str = x.toString();

    for (let i=str.length-1; i>=0; i--) {
        ans += str[i];
    }

    ans = parseInt(ans);
    if (ans>2**31-1 || ans<(-2)**31) {
        return 0;
    }
    return ans;
};

/**
 * @param {number} x
 * @return {number}
 */
var reverse = function(x) {

    const max = 2**31-1;
    const min = (-2)**31;
    let ans = 0;

    while (x != 0) {
        const pop = x%10;
        x = Math.trunc(x/10);
        if (ans > max/10) return 0;
        if (ans < min/10) return 0;

        ans = ans * 10 + pop;
    }

    return ans;
};

class Solution {

    /**
     * @param String $s
     * @return Integer
     */
    function lengthOfLongestSubstring($s) {
        $n = strlen($s);
        $ans = 0;
        $i = 0;
        $j = 0;

        $arr = [];

        while ($i < $n && $j < $n) {
            if (!in_array($s[$j], $arr)) {
                $arr[] = $s[$j++];
                $ans = max($ans, $j-$i);
            } else {
                array_splice($arr, 0, 1);
                $i++;
            }
        }


        return $ans;
    }
}

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    if (s.length <= 1) return s.length;

    const seenChars = {};
    let i=0, longest=0;

    for (let j=0; j<s.length; j++) {
        const currentChar = s[j];
        const currentCharIndex = seenChars[currentChar];

        if (currentCharIndex>=i) {
            i = currentCharIndex+1;
        }

        longest = Math.max(longest, j-i+1);
        seenChars[currentChar] = j;
    }

    return longest;
};

class Solution {

    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function waysToMakeFair($nums) {
        $len = count($nums);
        $ans = 0;

        $leftOdd = 0;
        $rightOdd = 0;
        $leftEven = 0;
        $rightEven = 0;

        for ($i=0; $i<$len; $i++) {
            if ($i%2 === 0)
                $rightEven += $nums[$i];
            else
                $rightOdd += $nums[$i];
        }

        for ($i=0; $i<$len; $i++) {
            if ($i%2 === 0)
                $rightEven -= $nums[$i];
            else
                $rightOdd -= $nums[$i];

            if ($leftEven + $rightOdd === $rightEven + $leftOdd) $ans++;

            if ($i%2 === 0)
                $leftEven += $nums[$i];
            else
                $leftOdd += $nums[$i];
        }

        return $ans;
    }
}

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    const stack = [];
    const brackets = {
        '(': ')',
        '{': '}',
        '[': ']'
    };

    for (i=0; i<s.length; i++) {
        if (s.length === 0) return true;

        const c = s[i];
        if (brackets[c]) {
            stack.push(c);
        } else {
            const lastBracket = stack.pop();
            if (brackets[lastBracket] !== c) return false;
        }
    }

    if (stack.length > 0) return false;

    return true;
};

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var backspaceCompare = function(s, t) {
    s = processString(s);
    t = processString(t);
    //console.log({s, t})
    return s===t;
};

let processString = function(s) {
    const a = [];
    let skip = 0;
    for (let i = s.length-1; i >= 0; i--) {
        if (s[i] === '#') {
            skip++;
        } else if (skip > 0) {
            skip--;
        } else {
            a.push(s[i]);
        }
        //console.log({a, skip, i})
    }
    let re = '';
    //console.log({ a: a.length})
    while (a.length > 0) {
        re += a.pop();
        //console.log({i, re, a: a.length})
    }
    return re;
}

/**
* Definition for Employee.
* class Employee {
*     public $id = null;
*     public $importance = null;
*     public $subordinates = array();
*     function __construct($id, $importance, $subordinates) {
*         $this->id = $id;
*         $this->importance = $importance;
*         $this->subordinates = $subordinates;
*     }
* }
*/

class Solution {
/**
 * @param Employee[] $employees
 * @param Integer $id
 * @return Integer
 */

function getImportance($employees, $id) {
  if (empty($employees)) return 0;
  $emap = [];
  foreach ($employees as $e) {
    $emap[$e->id] = $e;
  }

  return $this->recurse($emap, $id);
 }

function recurse($emap, $id) {
  $e = $emap[$id];
  $ans = $e->importance;
  foreach ($e->subordinates as $sub) {
    $ans += $this->recurse($emap, $sub);
  }
  return $ans;
 }
}

/**
 * @param {string} s
 * @return {string}
 */
var minRemoveToMakeValid = function(s) {
    const stack = [];
    const charArray = s.split("");
    const rightBracketsToRemove = [];

    for (let i=0;i<charArray.length;i++) {
        if (charArray[i] === '(') {
            stack.push(i);
        } else if (charArray[i] === ')' && stack.length > 0) {
            stack.pop();
        } else if (charArray[i] === ')') {
            charArray[i] = '';
        }
    }

    while (stack.length > 0) {
        const i = stack.pop();
        charArray[i] = '';
    }

    return charArray.join('');
};

class Solution {

    private $v = ['M' => 1000, 'D' => 500, 'C' => 100, 'L' => 50, 'X' => 10, 'V' => 5, 'I' => 1];
    /**
     * @param String $s
     * @return Integer
     */
    function romanToInt($s) {
        $n = 0;
        $last = '';
        for ($i=0;$i<strlen($s); $i++) {
            $n += $this->v[$s[$i]];
            if (($s[$i] == 'V' || $s[$i] == 'X') && $last == 'I') {
                $n = $n - 2;
            } elseif (($s[$i] == 'L' || $s[$i] == 'C') && $last == 'X') {
                $n -= 20;
            } elseif (($s[$i] == 'D' || $s[$i] == 'M') && $last == 'C') {
                $n -= 200;
            }
            $last = $s[$i];
        }

        return $n;
    }
}