[Programming Problem] Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

Example 1:
Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.

Example 2:
Input: grid = [[1,2,3],[4,5,6]]
Output: 12

[Problem Link]

Memoize by simply storing the minimum path to a cell via the top or left cell.

Input:
[[1, 3, 1],
[1, 5, 1],
[4, 2, 1]]

Memoized:
[[ 1, 4, 5 ],
[ 2, 7, 6 ],
[ 6, 8, 7 ]]

Solution will be the bottom right cell in the memoized array.

/**
 * @param {number[][]} grid
 * @return {number}
 */
var minPathSum = function(grid) {
    let ret = new Array(grid.length).fill(0).map((x) => new Array(grid[0].length).fill(0));
    for ( let i = 0 ; i < grid.length ; i++ ) {
        for ( let j = 0 ; j < grid[0].length ; j++ ) {
            if (i===0 && j===0) ret[i][j] = grid[i][j];
            else if (i===0) ret[i][j] = grid[i][j] + ret[i][j-1];
            else if (j===0) ret[i][j] = grid[i][j] + ret[i-1][j];
            else ret[i][j] = grid[i][j] + Math.min(ret[i-1][j], ret[i][j-1]);
        }
    }
    return ret[grid.length-1][grid[0].length-1];
};

[Programming Problem] Verifying an Alien Dictionary

In an alien language, surprisingly they also use english lowercase letters, but possibly in a different order. The order of the alphabet is some permutation of lowercase letters.

Given a sequence of words written in the alien language, and the order of the alphabet, return true if and only if the given words are sorted lexicographicaly in this alien language.

[Problem Link]

  • Create a custom comparator which will compare two words based on the order. The custom comparator basically loops through character by character to check order. Do account for cases where one word is smaller than the other or both words are same length.
  • Compare adjacent words in the array using the comparator. If any of them out of place, return false;
/**
 * @param {string[]} words
 * @param {string} order
 * @return {boolean}
 */
var isAlienSorted = function(words, order) {
    const orderMap = {};
    for (var i = 0; i < order.length; i++) orderMap[order[i]] = i;
    for (var i = 0 ; i < words.length-1 ; i++ ) {
        if (compare(words[i], words[i+1], orderMap) === 1) return false;
    }
    return true;    
};
 
var compare = function(a, b, orderMap) {
    for ( var i = 0 ; i < Math.min(a.length, b.length) ; i++ ) {
        if (orderMap[a[i]] < orderMap[b[i]]) return -1;
        else if (orderMap[a[i]] > orderMap[b[i]]) return 1;
    }    
    if (a.length === b.length) return 0;
    return a.length < b.length ? -1 : 1;
}

[Programming Problem] Design Tic-Tac-Toe

Assume the following rules are for the tic-tac-toe game on an n x n board between two players:

– A move is guaranteed to be valid and is placed on an empty block.
– Once a winning condition is reached, no more moves are allowed.
– A player who succeeds in placing n of their marks in a horizontal, vertical, or diagonal row wins the game.

Implement the TicTacToe class:

– TicTacToe(int n) Initializes the object the size of the board n.
– int move(int row, int col, int player) Indicates that player with id player plays at the cell (row, col) of the board. The move is guaranteed to be a valid move.

Follow up:
Could you do better than O(n2) per move() operation?

[Problem Link]

Key here is that every move is going to be valid, so we don’t need to check for invalid or repeat moves! Instead of keeping track of the whole board and checking for winners we can simply keep track of number of times a player has hit a row, col, or either of the diagonals. If count for any of them for a player hits ‘N’ we have a winner!

Few things to keep in mind:-

  • Keep player status (i.e. hits for rows, cols, and both diagonals) for both players. A single object wont do.
  • Remember we have 2 diagonals. When calculating hits for diagonals, treat those diagonals as separate variables! (not single diagonal)
/**
 * Initialize your data structure here.
 * @param {number} n
 */
var TicTacToe = function(n) {
 
    // - Gotcha 1: Please add player status for both players, single object wont do
    // We need to keep track if specifically one players rows, cols, or diagonals have hit 'N'
    // - Gotcha 2: Please remember we have 2 diagonals!
    // - Gotcha 3: 
 
    // Player status objects!
    this.playerOne = {
        rows: new Array(n).fill(0),
        cols: new Array(n).fill(0),
        diagonal: [0, 0],
    }
 
    this.playerTwo = {
        rows: new Array(n).fill(0),
        cols: new Array(n).fill(0),
        diagonal: [0, 0],
    }
 
    // N
    this.n = n;
 
    // rows, cols in diagonal one (and diagonal two)
    this.diagonal_one_set = new Set();
    this.diagonal_two_set = new Set();
 
    // diagonal 1 and diagonal 2
    let i = this.n-1;
    let j = 0;
    while (i >=0 && j < this.n ) {        
      this.diagonal_two_set.add(i + '' + j);
      i--;
      j++;
    }
 
    i = 0;
    j = 0;
    while (i < this.n && j < this.n ) {        
      this.diagonal_one_set.add(i + '' + j);
      i++;
      j++;
    }
};
 
/**
 * Player {player} makes a move at ({row}, {col}).
        @param row The row of the board.
        @param col The column of the board.
        @param player The player, can be either 1 or 2.
        @return The current winning condition, can be either:
                0: No one wins.
                1: Player 1 wins.
                2: Player 2 wins. 
 * @param {number} row 
 * @param {number} col 
 * @param {number} player
 * @return {number}
 */
TicTacToe.prototype.move = function(row, col, player) {
    const playerStatus = player === 1 ? this.playerOne : this.playerTwo;
 
    playerStatus.rows[row]++;
    playerStatus.cols[col]++;
    if (this.diagonal_one_set.has(row + '' + col)) playerStatus.diagonal[0]++;
    if (this.diagonal_two_set.has(row + '' + col)) playerStatus.diagonal[1]++;
 
    if ( 
        playerStatus.rows[row] === this.n ||
        playerStatus.cols[col] === this.n ||
        playerStatus.diagonal[0] === this.n ||
        playerStatus.diagonal[1] === this.n) {        
        return player;
    } else {
        return 0;
    }
};
 
/** 
 * Your TicTacToe object will be instantiated and called as such:
 * var obj = new TicTacToe(n)
 * var param_1 = obj.move(row,col,player)
 */

[Programming Problem] House Robber

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Example 1:

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

Example 2:

Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.

[Problem Link]

At every step i we have two options:-

  • Rob current house i and house i-2 …(nums[i] + dp[i-2])
  • Only rob house i-1, and don’t rob current house …(dp[i-1])

opt(i) = Max(dp[i-1], nums[i] + dp[i-2])

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
    if (nums.length === 0 ) return 0;
    if (nums.length === 1 ) return nums[0];
    if (nums.length === 2 ) return Math.max(nums[0], nums[1]);
 
    const dp = new Array(nums.length);
    dp[0] = nums[0];
    dp[1] = Math.max(nums[0], nums[1]);
    for (let i = 2 ; i < nums.length ; i++ ) {
        dp[i] = Math.max(dp[i-1], nums[i] + dp[i-2]);
    }
    return dp[nums.length-1];
};

[Programming Problem] Paint Fence

You are painting a fence of n posts with k different colors. You must paint the posts following these rules:

  • Every post must be painted exactly one color.
  • At most one pair of adjacent fence posts can have the same color.

Given the two integers n and k, return the number of ways you can paint the fence.

[Link]

The recursive solution times out! So let’s think of a dynamic programming solution!

Single Fence
opt(0) = k options

Double Fence
opt(1) = k^2 options

Third Fence
When first two fences are same color: k * (k-1) = opt(0) * (k-1)
When first two fences are diff color: k * (k-1) * k = k^2 * (k-1) = opt(1) * (k-1)
opt(2) = opt(0) * (k-1) + opt(1) * (k-1)

Nth Fence??
opt(i) = opt(i-2) * (k-1) + opt(i-1) * (k-1)

/**
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
 
var numWays = function(n, k) {
    if (n===0) return 0;
    if (n===1) return k;
 
    const dp = new Array(n);
    dp[0] = k;
    dp[1] = k*k;
 
    for (let i = 2; i < n ; i++ ) {
        dp[i] = (dp[i-2] * (k-1)) + (dp[i-1] * (k-1));
    }
 
    return dp[n-1];
};

The recursive solution (this will timeout).

/**
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
 
var numWays = function(n, k) {
    if (n <= 2) return Math.pow(k, n);
    return countForOneColor([], 0, n, k);
};
 
var countForOneColor = function(curr, level, n, k) {
    if (level === n) return 1;
    let ret = 0;
    for (let i = 0 ; i < k ; i++) {
        if (level >= 2 && curr[level-1] === curr[level-2] && i === curr[level-1]) continue;
        curr[level] = i;
        ret += countForOneColor(curr, level+1, n, k);
        curr.pop();
    }
    return ret;
}

[Programming Problem] Time Based Key-Value Store

Create a timebased key-value store class TimeMap, that supports two operations.

  1. set(string key, string value, int timestamp)
    Stores the key and value, along with the given timestamp.
  2. get(string key, int timestamp)
    Returns a value such that set(key, value, timestamp_prev) was called previously, with timestamp_prev <= timestamp. If there are multiple such values, it returns the one with the largest timestamp_prev. If there are no values, it returns the empty string ("").

[Problem Link]

Note that key-values are inserted in timestamp order (meaning when we set multiple values for a key, we wont request timestamp 10 before timestamp 1-9). So, the timestamp’s for a key will be in sorted order.

The problem essentially boils down to running a binary search for a target (or next smallest target). At every step, we return value if it matches exactly, otherwise go left or right. When we get a return from the recursion, we have a choice between returning a.) returned value or b.) current (mid) value. We return the one lower than target. If both values are lower than target, we return the one closer to target.

/**
 * Initialize your data structure here.
 */
 
var closest = function(i, j, arr, val) {
    if ( i > j ) return {value: '', timestamp: Number.MAX_VALUE};
 
    let mid = i + Math.round((j-i)/2);
    if ( arr[mid].timestamp === val ) return arr[mid];
 
    let ret = Number.MAX_VALUE;
    if ( arr[mid].timestamp > val )
        ret = closest(i, mid-1, arr, val);
    else 
        ret = closest(mid+1, j, arr, val);
 
    if ( arr[mid].timestamp < val && ret.timestamp < val ) {
        return arr[mid].timestamp > val ? arr[mid] : ret;
    } else if ( arr[mid].timestamp < val ) {
        return arr[mid];
    } else {
        return ret;
    }
}
 
 
var TimeMap = function() {
    this.map = {};
};
 
/** 
 * @param {string} key 
 * @param {string} value 
 * @param {number} timestamp
 * @return {void}
 */
TimeMap.prototype.set = function(key, value, timestamp) {
    if (!this.map[key]) this.map[key] = [];
    this.map[key].push({value, timestamp});
};
 
/** 
 * @param {string} key 
 * @param {number} timestamp
 * @return {string}
 */
TimeMap.prototype.get = function(key, timestamp) {
    if (!this.map[key]) return "";
    let arr = this.map[key];
    let ret = closest(0, arr.length-1, arr, timestamp);
    return ret.value;
};
 
/** 
 * Your TimeMap object will be instantiated and called as such:
 * var obj = new TimeMap()
 * obj.set(key,value,timestamp)
 * var param_2 = obj.get(key,timestamp)
 */

[Programming Problem] Boundary of Binary Tree

Given a binary tree, return the values of its boundary in anti-clockwise direction starting from root. Boundary includes left boundary, leaves, and right boundary in order without duplicate nodes. (The values of the nodes may still be duplicates.)

Left boundary is defined as the path from root to the left-most node. Right boundary is defined as the path from root to the right-most node. If the root doesn’t have left subtree or right subtree, then the root itself is left boundary or right boundary. Note this definition only applies to the input binary tree, and not applies to any subtrees.

The left-most node is defined as a leaf node you could reach when you always firstly travel to the left subtree if exists. If not, travel to the right subtree. Repeat until you reach a leaf node.

The right-most node is also defined by the same way with left and right exchanged.

Example 1

Input:
  1
   \
    2
   / \
  3   4
 
Ouput:
[1, 3, 4, 2]
 
Explanation:
The root doesn't have left subtree, so the root itself is left boundary.
The leaves are node 3 and 4.
The right boundary are node 1,2,4. Note the anti-clockwise direction means you should output reversed right boundary.
So order them in anti-clockwise without duplicates and we have [1,3,4,2].

Example 2

Input:
    ____1_____
   /          \
  2            3
 / \          / 
4   5        6   
   / \      / \
  7   8    9  10  
 
Ouput:
[1,2,4,7,8,9,10,6,3]
 
Explanation:
The left boundary are node 1,2,4. (4 is the left-most node according to definition)
The leaves are node 4,7,8,9,10.
The right boundary are node 1,3,6,10. (10 is the right-most node).
So order them in anti-clockwise without duplicate nodes we have [1,2,4,7,8,9,10,6,3].

[Problem Link]

The solution to this problem can be constructed using 3 sets:-

  • Left boundary
  • Leaf Nodes (left to right)
  • Right boundary

Generating these sets is straightforward but we need to be mindful of double counting nodes.

  • Left boundary and right boundary will contain root so best to separate that out.
  • Left boundary’s leftmost node will also be a leaf node (same for right boundary’s rightmost node). Again, best to remove these from those sets.

Our solution will be concatenation of

  • Root Node
  • Left Boundary Nodes (without the last leaf node)
  • Leaf nodes (from left to right)
  • In reverse, Right Boundary Nodes (without the last leaf node)
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
 
// get all leaf nodes (left to right)
var preOrder = function(root, level, leafs) {
    if (!root) return;
    if (!root.left && !root.right && level !== 0) leafs.push(root.val);    
    preOrder(root.left, level+1, leafs);
    preOrder(root.right, level+1, leafs);
}
 
var boundaryOfBinaryTree = function(root) {
 
    if (!root) return [];
 
    // get all left boundary nodes
    let leftList = [];
    let curr = root.left;
    while (curr) {
        leftList.push(curr.val);
        if (curr.left) curr = curr.left;
        else curr = curr.right;
    }
    // without the leftmost leaf (because that will already be part of the leaf's list)
    leftList.pop();
 
    // get all right boundary nodes
    let rightList = [];
    curr = root.right;
    while (curr) {
        rightList.push(curr.val);
        if (curr.right) curr = curr.right;
        else curr = curr.left;
    }
    // without the rightmost leaf (because that will already be part of the leaf's list)
    rightList.pop();
 
    // get all leaf nodes
    let leafList = [];
    preOrder(root, 0, leafList);
 
    // Solution is:
    // Root All_Left_Nodes All_Leaf_Nodes Reverse(All_Right_Nodes)
    // Remember to remove last leaf node from All_Left_Nodes and All_Right_Nodes otherwise you will double count!
 
    return ([root.val]).
            concat(leftList).
            concat(leafList).
            concat(rightList.reverse());
};

[Programming Problem] Deepest Leaves Sum

Given a binary tree, return the sum of values of its deepest leaves.

Example 1:

Input: root = [1,2,3,4,5,null,6,7,null,null,null,null,8]
Output: 15

[Problem Link]

Algorithm

  • Traverse through the tree using a level variable (which tells you which level you’re at).
  • When you reach a leaf, maintain a key map of level->sum.
  • In the end, pick the highest key from the map and output the value (as result).

Also TIL, that Property order is predictable in JavaScript objects since ES2015. Quoting from this article “All properties that are integer indices appear first in the overall object property order and are sorted numerically.”. This means we don’t need to sort the leaf map (by key) before returning the result.

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
 
var calcLeafMap = function(root, level, leafMap) {
    if (!root) return;
    if (!root.left && !root.right) {
        if (!leafMap[level]) leafMap[level] = 0;
        leafMap[level] += root.val;
    }    
    calcLeafMap(root.left, level+1, leafMap);
    calcLeafMap(root.right, level+1, leafMap);
};
 
var deepestLeavesSum = function(root) {
    let leafMap = {};
    calcLeafMap(root, 0, leafMap);
    let sortedLevels = Object.keys(leafMap);
    return leafMap[sortedLevels[sortedLevels.length-1]];
};

[Programming Problem] Minimum Remove to Make Valid Parentheses

Given a string s of ‘(‘ , ‘)’ and lowercase English characters.

Your task is to remove the minimum number of parentheses ( ‘(‘ or ‘)’, in any positions ) so that the resulting parentheses string is valid and return any valid string.

Formally, a parentheses string is valid if and only if:

It is the empty string, contains only lowercase characters, or
It can be written as AB (A concatenated with B), where A and B are valid strings, or
It can be written as (A), where A is a valid string.

Example 1:
Input: s = “lee(t(c)o)de)”
Output: “lee(t(c)o)de”
Explanation: “lee(t(co)de)” , “lee(t(c)ode)” would also be accepted.

Example 2:
Input: s = “a)b(c)d”
Output: “ab(c)d”

Example 3:
Input: s = “))((”
Output: “”
Explanation: An empty string is also valid.

Example 4:
Input: s = “(a(b(c)d)”
Output: “a(b(c)d)”

[Problem Link]

Initial thought was do a BFS search where each outgoing node is the string without a bracket. At any level if we find a solution, we stop there (for e.g. in below example we would stop at Level 1 itself since we find “ab(c)d”).

                         "a)b(c)d"
 
        "ab(c)d" ✔️      "a)bc)d"      "a)b(cd"
 
  "abc)d"   "ab(cd"        ...           ...

However, above solution will time out.

Instead we use the stack data structure to determine the brackets that cause invalidity of parentheses. These are simply the brackets remaining in the stack (at the end of validity test). With the bracket, we also store the index of the bracket (in the string) which makes it quicker to delete characters from those positions and rebuild valid string.

/**
 * @param {string} s
 * @return {string}
 */
 
// Node representing bracket and its index (in the string)
var Node = function(c, idx) {
    this.c = c;
    this.idx = idx;
}
 
var minRemoveToMakeValid = function(s) {
    let sChars = Array.from(s);
 
    // Use a stack to determine which brackets are causing 'invalidity'
    // We use Node data strcuture so that we know its index's (which makes it easy to remove)
    let stk = [];
    for ( let i = 0 ; i < sChars.length ; i++ ) {
        let curr = new Node(sChars[i], i);
        if ( curr.c === '(' || (curr.c === ')' && stk.length === 0) ) {
            stk.push(curr);
        } else if ( curr.c === ')' ) {
            let prev = stk.pop();
            if ( prev.c === ')' ) {
                stk.push(prev);
                stk.push(curr);
            }
        }
    }
 
    // index'es which we need to remove
    let toDelete = stk.map(function(n) {
        return n.idx;
    });
 
    // build new string!
    let newS = '';
    for ( let i = 0 ; i < sChars.length ; i++ ) {
        if (toDelete.includes(i)) continue;
        newS += sChars[i];
    }
 
    return newS;
};

Insert Delete GetRandom O(1) – Duplicates allowed

Design a data structure that supports all following operations in average O(1) time.

Note: Duplicate elements are allowed.
insert(val): Inserts an item val to the collection.

remove(val): Removes an item val from the collection if present.

getRandom: Returns a random element from current collection of elements. The probability of each element being returned is linearly related to the number of same value the collection contains.

Example:

// Init an empty collection.
RandomizedCollection collection = new RandomizedCollection();
 
// Inserts 1 to the collection. Returns true as the collection did not contain 1.
collection.insert(1);
 
// Inserts another 1 to the collection. Returns false as the collection contained 1. Collection now contains [1,1].
collection.insert(1);
 
// Inserts 2 to the collection, returns true. Collection now contains [1,1,2].
collection.insert(2);
 
// getRandom should return 1 with the probability 2/3, and returns 2 with the probability 1/3.
collection.getRandom();
 
// Removes 1 from the collection, returns true. Collection now contains [1,2].
collection.remove(1);
 
// getRandom should return 1 and 2 both equally likely.
collection.getRandom();

[Problem Link]

The idea here is to use a HashMap and Array. As we insert val’s, we have a mapping of val’s and nodes (containing value and index). We also insert the node into an array. At any point of time if we need a random value, we simply generate a random number (between 1 to length of array) and return the value from the array (in O(1) time).

How do we remove an element in O(1) time? First we use the map, to find the node where this element is stored. We then swap that with the last element and finally remove the last element. This works because when we look for a random number, we don’t care about order of elements in the array.

This wont work if you don’t store index’es in Nodes.

Let’s look at an example for remove. Below is the status of the HashMap and array at some point of the program. Note that, #xxx is the reference to the Node object (where we store index and value).

1 -> [#abc  #def  #ghi]
2 -> [#jkl  #mno]
3 -> [#pqr]
 
[#abc  #def  #mno  #ghi  #jkl  #pqr]
 
#abc = { idx: 0, val: 1 }
#def = { idx: 1, val: 1 }
#mno = { idx: 2, val: 2 }
#ghi = { idx: 3, val: 1 }
#jkl = { idx: 4, val: 2 }
#pqr = { idx: 5, val: 3 }
 
After remove(2)
 
1 -> [#abc  #def  #ghi]
2 -> [#jkl]
3 -> [#pqr]
 
[#abc  #def  #pqr  #ghi  #jkl]
 
#abc = { idx: 0, val: 1 }
#def = { idx: 1, val: 1 }
#mno = { idx: 2, val: 2 } (DELETED)
#ghi = { idx: 3, val: 1 }
#jkl = { idx: 4, val: 2 }
#pqr = { idx: 2, val: 3 } (UPDATED INDEX AND POSITION IN ARRAY)

Here is what we need todo to remove(2)

  1. Using the HashMap find positions where ‘2’ is stored. We could pick any position to remove it from (we pick #mno pointing to { idx: 2, val: 2 }).
  2. We then pop the last element (i.e. #pqr pointing to { idx: 5, val: 3 })
  3. We need to replace the reference in the array from #mno to #pqr.
    this.arr[removeNode.idx] = lastNode;
  4. Note, at this point #pqr index is still 5, we simply update that to the correct index
    lastNode.idx = removeNode.idx;
/**
 * Initialize your data structure here.
 */
var RandomizedCollection = function() {
    this.arr = [];
    this.map = {};
    this.Node = function(val, idx) {
        this.val = val;
        this.idx = idx;
    }
};
 
/**
 * Inserts a value to the collection. Returns true if the collection did not already contain the specified element. 
 * @param {number} val
 * @return {boolean}
 */
RandomizedCollection.prototype.insert = function(val) {
    if (!this.map[val]) this.map[val] = [];
    let newNode = new this.Node(val, this.arr.length);
    this.arr.push(newNode);
    this.map[val].push(newNode);
    //console.log('insert', val, this.arr);
    return this.map[val].length === 1;
};
 
/**
 * Removes a value from the collection. Returns true if the collection contained the specified element. 
 * @param {number} val
 * @return {boolean}
 */
RandomizedCollection.prototype.remove = function(val) {
    if (!this.map[val] || this.map[val].length === 0) return false;
    let removeNode = this.map[val].pop();
    let lastNode = this.arr.pop();
    if ( removeNode.idx !== lastNode.idx ) {
        lastNode.idx = removeNode.idx;
        this.arr[removeNode.idx] = lastNode;
    }
    //console.log('remove', val, this.map);
    //console.log(this.arr)
    return true;
};
 
/**
 * Get a random element from the collection.
 * @return {number}
 */
RandomizedCollection.prototype.getRandom = function() {
    if (this.arr.length < 1) return;
    let randomIdx = Math.floor(Math.random() * this.arr.length);
    //console.log('random', randomIdx, this.arr, this.arr.length)
    return this.arr[randomIdx].val;
};
 
/** 
 * Your RandomizedCollection object will be instantiated and called as such:
 * var obj = new RandomizedCollection()
 * var param_1 = obj.insert(val)
 * var param_2 = obj.remove(val)
 * var param_3 = obj.getRandom()
 */