End Course Capstone Project (Module Data Structures) - Solution

00_End Course Capstone Project.md

End Course Capstone Project (Module Data Structures) - Solution

01_getDecimalValue.js

module.exports = { getDecimalValue };

const getDecimalValue = head => {
  let val = 0;
  while (head) {
    val = (val << 1) | head.val;
    head = head.next;
  }
  return val;
};

02_middleNode.js

module.exports = { middleNode };

var middleNode = function(head) {
    let slow = head;
    let fast = head;
    
    while (fast && fast.next){
        fast = fast.next.next;
        slow = slow.next;
    }
    return slow;
   
};

03_isPalindrome.js

module.exports = { isPalindrome };

var isPalindrome = function(head) {
    let arr = []
    while(head) {
        arr.push(head.val)
        head = head.next
    }
    return arr.join('') == arr.reverse().join('')
};

04_reverseList.j

module.exports = { reverseList };

var reverseList = function(head) {
    let prev = null
    while (head !== null) {
        let current = head
        head = head.next
        current.next = prev
        prev = current
    }
    return prev
};

05_removeElements.js

module.exports = { removeElements };

var removeElements = function(head, val) {
    
    let tempHead = head,prev
    while (!tempHead){
        if (tempHead.val ===val){
            if (prev){
                head = head.next
                tempHead=tempHead.next
            }else{
                prev.next =tempHead.next
                tempHead=tempHead.next
                
            }
        }else{
            prev=tempHead
            tempHead.next = tempHead  
        }
    }
    
    return head
};

06_countBits.js

module.exports = { countBits };

var countBits = function(num) {
    let res = [0]
    for(let i=1;i<=num;i++){
        const half = i>>1
        const odd = i&1
        res[i] = res[half] + odd
    }
    return res
};

07_sumOfLeftLeaves.js

module.exports = { sumOfLeftLeaves };

var sumOfLeftLeaves = function(root) {
    if(!root) return 0; const { left, right } = root;
    
    let [sumLeft, sumRight] = [sumOfLeftLeaves(left), sumOfLeftLeaves(right)];
    
    if(!sumLeft && left && !left.left && !left.right) sumLeft = left.val;
    
    return Number(sumLeft) + Number(sumRight);
};

08_diameterOfBinaryTree.js

module.exports = { diameterOfBinaryTree };

function diameterOfBinaryTree(root) {
    let max = 0
     
     function maxDepth(root) {
         if (root === null) return 0 
         let left = maxDepth(root.left) 
         let right = maxDepth(root.right) 
     
         
         max = Math.max(max, left + right) 
         return Math.max(left, right) + 1 
     }

     maxDepth(root)
     return max
 };

09_preorder.js

module.exports = { preorder };

var preorder = function(root) {
    if(!root) return [];
    const queue =[root];
    const arr = [];
    
    while(queue.length){
        const node = queue.shift();
        arr.push(node.val);
        queue.unshift(...node.children);

    }
  return arr ;
};

10_mergeTrees.js

module.exports = ={ mergeTrees };

const mergeTrees = function(root1, root2) {
    if (!root1) return root2
    if (!root2) return root1
    
    const res = root1
    
    const queue = []
    queue.push({v1:res, v2:root2}) 
    
    while (queue.length) {
        const {v1, v2} = queue.shift()
        v1.val += v2.val
        
        if (v1.left && v2.left) queue.push({v1:v1.left, v2:v2.left})
        if (!v1.left && v2.left) v1.left = v2.left
        
        if (v1.right && v2.right) queue.push({v1:v1.right, v2:v2.right})
        if (!v1.right && v2.right) v1.right = v2.right  
        
    }
    
    return res
     
};

11_minimizeArrayValue.js

module.exports = {minimizeArrayValue };

var minimizeArrayValue = function(nums) {
    let max = 0;
    for (let i = 1, sum = 0; i <= nums.length; i++)
        sum += nums[i - 1], max = Math.max(max, Math.ceil(sum / i));

    return max;
};

12_minimumTime.js

module.exports = { minimumTime };

function minimumTime(time, totalTrips) {
  let left = 1; // minimum time needed to complete all trips
  let right = 1e18; // maximum time (for practical purposes)
  while (left < right) {
    const mid = Math.floor((left + right) / 2); // mid-point of the search range
    let tripsCompleted = 0;
    for (let i = 0; i < time.length && tripsCompleted < totalTrips; i++) {
      tripsCompleted += Math.floor(mid / time[i]); // number of trips completed by this bus in mid time
    }
    if (tripsCompleted >= totalTrips) {
      right = mid; // search the left half of the range
    } else {
      left = mid + 1; // search the right half of the range
    }
  }
  return left;
}

13_maxTaxEarnings.js

module.exports = { maxTaxEarnings };

var maxTaxEarnings = function(n, rides) {
    const map = new Map();
    
    for (let i = 0; i < rides.length; ++i) {
        const [start, end, tips] = rides[i];
        
        if (!map.has(end)) map.set(end, []);
        map.get(end).push(i);
    }
   
    const dp = new Array(n + 1).fill(0);
    
    for (let point = 1; point <= n; ++point) {
        if (!map.has(point)) {
            dp[point] = dp[point - 1];
        }
        else {
            dp[point] = dp[point - 1];
            
            const indexes = map.get(point);
            
            for (const idx of indexes) {
                const [start, end, tips] = rides[idx];
                const currProfit = end - start + tips;
                const prevProfit = dp[start];
                
                dp[point] = Math.max(dp[point], prevProfit + currProfit);
            }
        }
    }
    
    return dp[n];
};

14_mostProfitablePath.js

module.exports = { mostProfitablePath };

var mostProfitablePath = function(edges, bob, amount) {
    const graph = Array.from({ length: edges.length + 1 }, () => []);

    for (const [i, j] of edges)
        graph[i].push(j), graph[j].push(i);
    
    function aliceMoves(node, parent, time) {
        let totalBobTime = node == bob ? 0 : Infinity, newScore = -Infinity;

        for (const child of graph[node]) {
            if (child == parent) continue;

            const [score, bobTime] = aliceMoves(child, node, time + 1);
            totalBobTime = Math.min(totalBobTime, bobTime + 1);
            newScore = Math.max(newScore, score)
        }

        if (newScore == -Infinity) newScore = 0;
        if (time < totalBobTime) newScore += amount[node];
        else if (time == totalBobTime) newScore += amount[node] / 2;

        return [newScore, totalBobTime];
    }
    
    return aliceMoves(0, -1, 0)[0];
};

15_edgeScore.js

module.exports = { edgeScore };

var edgeScore = function(edges) {
    let score=Array(edges.length).fill(0);
    
    for(let i=0;i<edges.length;i++){
        let neighNode=edges[i];
        score[neighNode]+=i;
    }
    
    let max=-Infinity;
    let index=0;
    
    for(let i=0;i<score.length;i++){
        
        if(score[i]>max){
            max=score[i];
            index=i;
        }
    }
    
    return index;
};

16_addTwoNumbers.js

module.exports = { addTwoNumbers };

var addTwoNumbers = function(l1, l2, carry) {
    if(!l1 && !l2 && !carry) return null;

    var total = (l1 ? l1.val : 0) + (l2 ? l2.val : 0) + (carry || 0);
    carry = parseInt(total / 10);
    return new ListNode(total % 10, addTwoNumbers(l1?.next, l2?.next, carry));
};

17_LRUCache.js

module.exports = { LRUCache };

class LRUCache {
    constructor(capacity) {
        this.map = new Map();
        this.capacity = capacity;
    }

    get(key) {
        if (!this.map.has(key)) return -1;
        const val = this.map.get(key);
        this.map.delete(key);
        this.map.set(key, val);
        return val;
    }

    put(key, value) {
        this.map.delete(key);
        this.map.set(key, value);
        if (this.map.size > this.capacity) {
          const firstItem = this.map.keys().next().value;
          this.map.delete(firstItem);
        }
    }
}

18_maximumSafenessFactor.js

module.exports = { maximumSafenessFactor };

var maximumSafenessFactor = function(grid) {
  const n = grid.length;
  const isInBound = (r, c) => r >= 0 && r < n && c >= 0 && c < n;
  const dist = new Array(n).fill(0).map(() => new Array(n).fill(Infinity));
  const queue = [];

  for (let r = 0; r < n; r++) {
    for (let c = 0; c < n; c++) {
      if (grid[r][c] === 1) {
        dist[r][c] = 0;
        queue.push([r, c]);
      }
    }
  }

  while (queue.length) {
    const [r, c] = queue.shift();
    const neighbors = [
      [r + 1, c],
      [r - 1, c],
      [r, c + 1],
      [r, c - 1],
    ];

    for (const [nr, nc] of neighbors) {
      if (isInBound(nr, nc) && dist[nr][nc] === Infinity) {
        dist[nr][nc] = dist[r][c] + 1;
        queue.push([nr, nc]);
      }
    }
  }

  const maxDistance = new Array(n).fill(0).map(() => new Array(n).fill(0));
  maxDistance[0][0] = dist[0][0];
  queue.push([0, 0]);

  while (queue.length) {
    const [r, c] = queue.shift();
    const neighbors = [
      [r + 1, c],
      [r - 1, c],
      [r, c + 1],
      [r, c - 1],
    ];

    for (const [nr, nc] of neighbors) {
      if (isInBound(nr, nc)) {
        const newDistance = Math.min(maxDistance[r][c], dist[nr][nc]);
        if (newDistance > maxDistance[nr][nc]) {
          maxDistance[nr][nc] = newDistance;
          queue.push([nr, nc]);
        }
      }
    }
  }

  return maxDistance[n - 1][n - 1];    
};

19_balanceBST.js

module.exports = { balanceBST };

var balanceBST = function(root) {
    const values = toArray(root);
    return toBST(values);
    
    function toBST(arr) {
        if (arr.length===0) return null;
        if (arr.length===1) return new TreeNode(arr[0]);
        const mid = Math.floor(arr.length / 2);
        const left = toBST(arr.slice(0, mid));
        const right = toBST(arr.slice(mid+1));
        return new TreeNode(arr[mid], left, right);
    }
    
    function toArray(node) {
        if (!node) return [];
        return [...toArray(node.left), node.val, ...toArray(node.right)];
    }
};

20_cloneGraph.js

module.exports = { cloneGraph };

var cloneGraph = function (node) {
    if (!node) return null;

    let dfs = (node, visited) => {
        if (visited.has(node)) return visited.get(node);
        let newNode = new Node(node.val);
        visited.set(node, newNode);
        for (let neighbor of node.neighbors) {
            newNode.neighbors.push(dfs(neighbor, visited));
        }
        return newNode;
    }
    return dfs(node, new Map());
}