Algorithm - HackerRank, Leetcode Problems

HackerRank Problem : Cats and a Mouse

• Two cats and a mouse are at various positions on a line. You will be given their starting positions. Your task is to determine which cat will reach the mouse first, assuming the mouse does not move and the cats travel at equal speed. If the cats arrive at the same time, the mouse will be allowed to move and it will escape while they fight.
• You are given queries in the form of x, y, and z representing the respective positions for cats A and B, and for mouse C. Complete the function catAndMouse to return the appropriate answer to each query, which will be printed on a new line.
  • If cat A catches the mouse first, print Cat A.
  • If cat B catches the mouse first, print Cat B.
  • If both cats reach the mouse at the same time, print Mouse C as the two cats fight and mouse escapes.
  • Constraints
    • 1 <= q <= 100
    • 1 <= x, y, z <= 100

Solution

function catAndMouse(x, y, z) {
    const distanceOfA = Math.abs(z - x);
    const distanceOfB = Math.abs(z - y);
    if (distanceOfA < distanceOfB) {
        return 'Cat A';
    } else if (distanceOfA > distanceOfB) {
        return 'Cat B';
    } else {
        return 'Mouse C';
    }
}

HackerRank Problem : Electronics Shop

• A person wants to determine the most expensive computer keyboard and USB drive that can be purchased with a give budget. Given price lists for keyboards and USB drives and a budget, find the cost to buy them. If it is not possible to buy both items, return -1.
  • Input Format
    • b : the budget, the number of keyboard models and the number of USB drive models.
    • n : The second line contains n space-separated integers keyboards[i], the prices of each keyboard model.
    • m : The third line contains m space-separated integers drives, the prices of the USB drives
  • Constraints
    • 1 <= n, m <= 1000
    • 1 <= b <= 10^6
• Example

b = 60
keyboards = [40, 50, 60]
drives = [5, 8, 12]

• The person can buy a 40 keyboard + 12 USB drive = 52, or a 50 keyboard + 8 USB drive = 58. Choose the latter as the more expensive option and return 58.

Solution

function getMoneySpent(keyboards, drives, b) {
    let costCases = [];
    for (let i = keyboards.length - 1; i >= 0; i--) {
        let keyboardCount = keyboards[i];
        let restBudget = b - keyboardCount;
        if (restBudget <= 0) continue;
        let buyableDrives = drives.filter(drive => drive <= restBudget).sort((a,b) => b - a);
        if (buyableDrives.length > 0) {
            const cost = keyboardCount + buyableDrives[0];
            costCases.push(cost);
            continue;
        }
    }
    if (costCases.length === 0) return -1;
    costCases.sort((a,b) => b - a);
    return costCases[0];
}

LeetCode Problem : Minimum Number of Steps to Make Two Strings Anagram

• You are given two strings of the same length s and t. In one step you can choose any character of t and replace it with another character.

• Return the minimum number of steps to make t an anagram of s.

• An Anagram of a string is a string that contains the same characters with a different (or the same) ordering.

• Example

  • Input: s = "bab", t = "aba"
  • Output: 1
  • Explanation: Replace the first 'a' in t with b, t = "bba" which is anagram of s.

Solution

var minSteps = function(s, t) {
    let replacedCount = 0;
    for (let i = 0; i < t.length; i++) {
        const strT = t[i];
        const indexS = s.indexOf(strT);
        if (indexS !== -1) {
           s = s.replace(strT, '');
       } else {
           replacedCount++;
       }
    }
    return replacedCount;
};

LeetCode Problem : Evaluate Boolean Binary Tree

• You are given the root of a full binary tree with the following properties

  • Leaf nodes have either the value 0 or 1, where 0 represents False and 1 represents True.
  • Non-leaf nodes have either the value 2 or 3, where 2 represents the boolean OR and 3 represents the boolean AND

• The evaluation of a node is as follows

  • If the node is a leaf node, the evaluation is the value of the node, i.e. True or False.
  • Otherwise, evaluate the node's two children and apply the boolean operation of its value with the children's evaluations.

• Return the boolean result of evaluating the root node.

  • A full binary tree is a binary tree where each node has either 0 or 2 children.
  • A leaf node is a node that has zero children.

• Example

  • Input: root = [2,1,3,null,null,0,1]
  • Output: true
  • Explanation: The AND node evaluates to False AND True = False.
    The OR node evaluates to True OR False = True.
    The root node evaluates to True, so we return true.

Solution

/**
 * 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 {boolean}
 */
var evaluateTree = function(root) {
    if (!root.left && !root.right) {
        return root.val ? true : false;
    }
    
    let left = evaluateTree(root.left);
    let right = evaluateTree(root.right);
    
    return root.val === 2 ? left || right : left && right;
};

LeetCode Problem : Range Sum of BST

• Given the root node of a binary search tree and two integers low and high, return the sum of values of all nodes with a value in the inclusive range [low, high].

• Example
  • Input: root = [10,5,15,3,7,null,18], low = 7, high = 15
  • Output: 32
  • Explanation: Nodes 7, 10, and 15 are in the range [7, 15]. 7 + 10 + 15 = 32.

Solution

/**
 * 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
 * @param {number} low
 * @param {number} high
 * @return {number}
 */
var rangeSumBST = function(root, low, high) {
    let result = 0;
    function traverse(node){
        if (node.left) traverse(node.left);
        if (node.val >= low && node.val <= high) result += node.val;
        if (node.right) traverse(node.right);
    }
    traverse(root);
    return result;
};

LeetCode Problem : Search in a Binary Search Tree

• You are given the root of a binary search tree (BST) and an integer val.
• Find the node in the BST that the node's value equals val and return the subtree rooted with that node. If such a node does not exist, return null.

• Example
  • Input: root = [4,2,7,1,3], val = 2
  • Output: [2,1,3]

Solution

/**
 * 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
 * @param {number} val
 * @return {TreeNode}
 */
var searchBST = function(root, val) {
    let queue = [root];
    let result = null;
    
    while(queue.length) {
        let node = queue.shift();
        if (node.val === val) {
            result = node;
            break;
        }
        if (node.left) {
            queue.push(node.left);
        }
        if (node.right) {
            queue.push(node.right);
        }
    }
    
    return result;
};