Mid AlgoExp - 16-24

16 - Invert Binary Tree

Write a function that takes in a Binary Tree and inverts it. In other words, the function should swap every left node in the tree for its corresponding right node.

Starter Code

function invertBinaryTree(tree) {
  // Write your code here.
}

// This is the class of the input binary tree.
class BinaryTree {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

👨‍🔬 Javascript Solution

function invertBinaryTree(tree) {
    // Write your code here.
    const queue = [tree];
    while (queue.length) {
        const current = queue.shift();
        if (current === null) continue;
        swapLeftAndRight(current);
        queue.push(current.left);
        queue.push(current.right);
    }



}

function swapLeftAndRight(tree) {
    const left = tree.left;
    tree.left = tree.right;
    tree.right = left;
}
}

17 - Binary Tree Diameter

Write a function that takes in a Binary Tree and returns its diameter. The diameter of a binary tree is defined as the length of its longest path, even if that path doesn't pass through the root of the tree.

Starter Code

// This is an input class. Do not edit.
class BinaryTree {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

function binaryTreeDiameter(tree) {
  // Write your code here.
  return -1;
}

👨‍🔬 Javascript Solution

Solution Code
}

17b - Find Successor

Write a fucntion that takes in a Binary Tree ( Where nodes have an additional pointer to their parend node) as welll as a node contained in that tree and return the given node's successor.

Starter Code

// This is an input class. Do not edit.
class BinaryTree {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
    this.parent = null;
  }
}

function findSuccessor(tree, node) {
  // Write your code here.
  return null;
}

👨‍🔬 Javascript Solution

class BinaryTree {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
    this.parent = null;
  }
}

function findSuccessor(tree, node) {
  const inOrderTraversalOrder = getInOrderTraversalOrder(tree);

  for (let idx = 0; idx < inOrderTraversalOrder.length; idx++) {
    const currentNode = inOrderTraversalOrder[idx];
    if (currentNode !== node) continue;

    if (idx === inOrderTraversalOrder.length - 1) return null;

    return inOrderTraversalOrder[idx + 1];
  }
}

function getInOrderTraversalOrder(node, order = []) {
  if (node === null) return order;
  getInOrderTraversalOrder(node.left, order);
  order.push(node);
  getInOrderTraversalOrder(node.right, order);

  return order;
}

Advanced Solution

function findSuccessor(tree, node) {
  if (node.right !== null) return getLeftMostChild(node.right);
  return getRightMostParent(node);
}

function getLeftMostChild(node) {
  let currentNode = node;
  while (currentNode.left !== null) {
    currentNode = currentNode.left;
  }

  return currentNode;
}

function getRightMostParent(node) {
  let currentNode = node;
  while (
    currentNode.parent !== null &&
    currentNode.parent.right == currentNode
  ) {
    currentNode = currentNode.parent;
  }
  return currentNode.parent;
}

18 - Height Balanced Binary Tree

You're given the root node of a Binary Tree. Write a function that returns true if this Binary Tree is height balanced and false if it isn't

Starter Code

// This is an input class. Do not edit.
class BinaryTree {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

function heightBalancedBinaryTree(tree) {
  // Write your code here.
  return false;
}

// Do not edit the lines below.
exports.BinaryTree = BinaryTree;
exports.heightBalancedBinaryTree = heightBalancedBinaryTree;

👨‍🔬 Javascript Solution

class BinaryTree {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

class TreeInfo {
    constructor(isBalanced, height) {
        this.isBalanced = isBalanced;
        this.height = height;
    }
}

function heightBalancedBinaryTree(tree) {
    const treeInfo = getTreeInfo(tree);
    return treeInfo.isBalanced;
}

function getTreeInfo(node) {
    if (node === null) return new TreeInfo(true, -1);
    const leftSubtreeInfo = getTreeInfo(node.left);
    const rightSubtreeInfo = getTreeInfo(node.right);

    const isBalanced = leftSubtreeInfo.isBalanced && rightSubtreeInfo.isBalanced && Math.abs(leftSubtreeInfo.height - rightSubtreeInfo.height) <=1;
    const height = Math.max(leftSubtreeInfo.height, rightSubtreeInfo.height) + 1;
    return new TreeInfo(isBalanced, height);

}
// Do not edit the lines below.
exports.BinaryTree = BinaryTree;
exports.heightBalancedBinaryTree = heightBalancedBinaryTree;

}

19 - Max Subset Sum No Adjacent

Write a function that takes in an array of positive integers and returns the maximum sum of non-adjacent elements in the array.

Starter Code

function maxSubsetSumNoAdjacent(array) {
  // Write your code here.
}

👨‍🔬 Javascript Solution

function maxSubsetSumNoAdjacent(array) {
  if (!array.length) return 0;
  if (array.length === 1) return array[0];

  const maxSums = array.slice();
  maxSums[1] = Math.max(array[0], array[1]);
  for (let i = 2; i < array.length; i++) {
    maxSums[i] = Math.max(maxSums[i - 1], maxSums[i - 2] + array[i]);
  }
  return maxSums[maxSums.length - 1];
}

20 - Number of Ways to Make Change

Given an array of distinc positive integers representing coin denominations and a single non-negative integer n representing a target amount of money, write a function that returns the number of ways to make change for that target amount using hte given coin denominations.

Note that an unlimited amount of coins is at your disposal

Starter Code

function numberOfWaysToMakeChange(n, denoms) {
  // Write your code here.
}

👨‍🔬 Javascript Solution

function numberOfWaysToMakeChange(n, denoms) {
    const ways = new Array(n + 1).fill(0);
    ways[0] = 1;
    for (let denom of denoms) {
        for (let amount = 1; amount < n + 1; amount++) {
            if (denom <= amount) ways[amount] += ways[amount - denom];
        }
    }
    return ways[n];

}

}

21 - Min Number of Coins for Change

Given an Array of Positive single non-negative integer n representing a target amount of money, wirte a function...

Starter Code

starter Code

👨‍🔬 Javascript Solution

Solution Code
}

22 - Levenshtein Distance

Write a function that takes in two strings and returns the minimum number of edit operations that need to be performed on the first string to obtain the second string.

There are three edit operations:

Insertion fo a character
Deletion of a character
Substitution of a character

How I would solve this

Try computing all potential changes from abc and yabd

Starter Code

function levenshteinDistance(str1, str2) {}

👨‍🔬 Javascript Solution

We can create a table to compare which is the distance between them

function levenshteinDistance(str1, str2) {
  const edits = [];
  for (let i = 0; i < str2.length + 1; i++) {
    const row = [];
    for (let j = 0; j < str1.length + 1; j++) {
      row.push(j);
    }

    row[0] = i;
    edits.push(row);
  }

  for (let i = 1; i < str2.length + 1; i++) {
    for (let j = 1; j < str1.length + 1; j++) {
      if (str2[i - 1] === str1[j - 1]) {
        edits[i][j] = edits[i - 1][j - 1];
      } else {
        edits[i][j] =
          1 + Math.min(edits[i - 1][j - 1], edits[i - 1][j], edits[i][j - 1]);
      }
    }
  }
  return edits[str2.length][str1.length];
}

// Do not edit the line below.
exports.levenshteinDistance = levenshteinDistance;

23a - Number of ways to Traverse Graph

You are given two positive integers representing the width and height of a grid-shaped, rectangular graph. Write a fucntion that returns the number of ways to reach the bottom right corner of the graph when starting at the top left corner. Each move you take must either go down or riight. In other words, you cna never move up or left in the graph.

Starter code
function numberOfWaysToTraverseGraph(width, height) {
  // Write your code here.
  return 0;
}

👨‍🔬 Solutions

Js
Py
Java
C++

function numberOfWaysToTraverseGraph(width, height) {
  // Write your code here.
  const ways = [];
  for (let i = 0; i < height; i++) {
    ways.push([]);
    for (let j = 0; j < width; j++) {
      ways[i].push(0);
    }
  }

  for (let i = 0; i < height; i++) {
    for (let j = 0; j < width; j++) {
      if (i == 0 || j == 0) {
        ways[i][j] = 1;
      } else {
        ways[i][j] = ways[i - 1][j] + ways[i][j - 1];
      }
    }
  }
  return ways[height - 1][width - 1];
}

def status():
    print("On Development - Coming Soon using Python!")

class HelloWorld {
    public static void main(String[] args) {
        System.out.println("On Development - Coming Soon using Java!");
    }
}

#include <iostream>

int main() {
    std::cout << "On Development - Coming Soon using C++!";
    return 0;
}

23b - Kadane's Algorithm

Write a function that takes in a non-empty array of integers and returns the maximum sum that can be obtained by summing up all of the integers ina non-empty subarray of the input array. A subarray must only contain adjacent number (numbers next to each other in the input array)

Starter code
function kadanesAlgorithm(array) {
  // Write your code here.
}

👨‍🔬 Solutions

Js
Py
Java
C++

function kadanesAlgorithm(array) {
  // Write your code here.
  let maxSoFar = array[0];
  let maxTemp = array[0];

  for (let i = 1; i < array.length; i++) {
    maxTemp = Math.max(array[i], array[i] + maxTemp);
    maxSoFar = Math.max(maxSoFar, maxTemp);
  }
  return maxSoFar;
}

def status():
    print("On Development - Coming Soon using Python!")

class HelloWorld {
    public static void main(String[] args) {
        System.out.println("On Development - Coming Soon using Java!");
    }
}

#include <iostream>

int main() {
    std::cout << "On Development - Coming Soon using C++!";
    return 0;
}

24 - Single Cycle Check

You are given an array of integers where each integer represents a jump of its value in the array. For instance, the integer 2 represents a jump of two indices forward in the array: the integer -3 represents a jump of three indices backward in the array.

If a jump spills past the array's bounds, it wraps over to the other side. For instance, a jump of -1 at index 0 bring us to the last index in the array. Similarly, a jump of 1 at the last index in the array bring us to index 0

Write a function that returns a boolean representing whether the jumps in the array form a single cycle. A single cycle occurs if, starting at any index in the array and following the jumps, every element in the array is visited exactly once before landing back on the starting index.

Starter code
function numberOfWaysToTraverseGraph(width, height) {
  return 0;
}

👨‍🔬 Solutions

Js+logs
Js
Py
Java
C++

function hasSingleCycle(array) {
  let numElementVisited = 0;
  let currentIdx = 0;

  while (numElementVisited < array.length) {
    if (numElementVisited > 0 && currentIdx == 0) return false;
    currentIdx = getNextIdx(currentIdx, array);
    console.log(currentIdx);
    numElementVisited++;
  }
  return currentIdx === 0;
}

function getNextIdx(currentIdx, array) {
  let nextIdx = (currentIdx + array[currentIdx]) % array.length;
  console.log(
    `currentIdx: ${currentIdx} arrel: ${array[currentIdx]} += ${nextIdx}`
  );
  return nextIdx < 0 ? array.length + nextIdx : nextIdx;
}

function hasSingleCycle(array) {
  // Write your code here.
  currentIdx = 0;
  amountOfTraversed = 0;

  while (amountOfTraversed < array.length) {
    if (amountOfTraversed > 0 && currentIdx === 0) return false;
    currentIdx = getNext(currentIdx, array);
    amountOfTraversed++;
  }

  return currentIdx === 0;
}

function getNext(idx, array) {
  nextIdx = (idx + array[idx]) % array.length;
  return nextIdx < 0 ? array.length + nextIdx : nextIdx;
}

def status():
    print("On Development - Coming Soon using Python!")

class HelloWorld {
    public static void main(String[] args) {
        System.out.println("On Development - Coming Soon using Java!");
    }
}

#include <iostream>

int main() {
    std::cout << "On Development - Coming Soon using C++!";
    return 0;
}

16 - Invert Binary Tree​

17 - Binary Tree Diameter​

17b - Find Successor​

18 - Height Balanced Binary Tree​

19 - Max Subset Sum No Adjacent​

20 - Number of Ways to Make Change​

21 - Min Number of Coins for Change​

22 - Levenshtein Distance​

23a - Number of ways to Traverse Graph​

23b - Kadane's Algorithm​

24 - Single Cycle Check​

16 - Invert Binary Tree

17 - Binary Tree Diameter

17b - Find Successor

18 - Height Balanced Binary Tree

19 - Max Subset Sum No Adjacent

20 - Number of Ways to Make Change

21 - Min Number of Coins for Change

22 - Levenshtein Distance

23a - Number of ways to Traverse Graph

23b - Kadane's Algorithm

24 - Single Cycle Check