Canva tech interview - no job offer

canva-tech-interview.js

/**
 * The input string can contain any of: -, *, ^ alongside any valid numerical number (including decimals).
 * Standard operator precedence applies with ^ being higher than * higher than - .
 An example program input might be 5 * 4 - 3 - 5 ^ 3 which should output -108
 For the purposes of this program you can assume that negative numbers and parenthesis are not allowed. Additionally,
 we are not concerned about floating point precision or numbers that would exceed the float type size.
 While some languages have built in support for eval-ing expressions, we ask you don’t use these features when designing
 a solution.
 */

/**
 * Solution, build a tree with the highest priority operation at the lowest part of the tree, and build your way up
 * to the lowest priority. To do so find the last index of the current lowest operation priority (on first occurrence
 * it is either - or +) and split the operation in two part, left (lh) and right (rh).
 *
 * Right is either a number or an equation, if it's an equation rerun algorithm with the next operation in
 * ascending priority.
 *
 * Left is also either a number or an equation, but the equation can contain the current operation, so we rerun the
 * algorithm with the same operation.
 *
 * If operation cannot be found in equation, rerun algorithm with next operation.
 *
 * If no operation exist in equation, it must be a number.
 *
 *
 * Once the tree is built, we step through it by executing depth first (highest priority equation part)
 */
//5 * 4 - 3 - 5 ^ 3
const tree = {
  op: "-",
  lh: {
    op: "-",
    lh: {
      op: "*",
      lh: 5,
      rh: 4,
    },
    rh: 3,
  },
  rh: {
    op: "^",
    lh: 5,
    rh: 3,
  },
};

//5 * 4 - 3 * 5 ^ 3 - 7 * 5 ^ 4
const tree1 = {
  op: "-",
  lh: {
    op: "-",
    lh: {
      op: "*",
      lh: 5,
      rh: 4,
    },
    rh: {
      op: "*",
      lh: 3,
      rh: {
        op: "^",
        lh: 5,
        rh: 3,
      },
    },
  },
  rh: {
    op: "*",
    lh: 7,
    rh: {
      op: "^",
      lh: 5,
      rh: 4,
    },
  },
};

const operationByPriorityOrder = [["-", "+"], ["*", "/"], "^"];

const tokenise = (equation) => {
  const step = (equation, operation) => {
    const [op, ...nextOps] = operation;

    let idx;
    if (Array.isArray(op)) {
      idx = furthestIndex(equation, op);
    } else {
      idx = equation.lastIndexOf(op);
    }

    const left = equation.slice(0, idx - 1);
    const right = equation.slice(idx + 2, equation.length);

    if (idx !== -1) {
      return {
        op: equation[idx],
        lh: step(left, operation),
        rh: nextOps.length !== 0 ? step(right, nextOps) : Number(right),
      };
    } else {
      if (nextOps.length !== 0) {
        return step(equation, nextOps);
      }
      return Number(equation);
    }
  };

  return step(equation, operationByPriorityOrder);
};

const calc = (lh, rh, op) => {
  if (op === "^") {
    return Math.pow(lh, rh);
  }
  if (op === "*") {
    return lh * rh;
  }
  if (op === "-") {
    return lh - rh;
  }
  if (op === "+") {
    return lh + rh;
  }
  if (op === "/") {
    return lh / rh;
  }
};

// depth first traversal
const treeTraversalDFS = (tree) => {
  const { lh, rh, op } = tree;

  const numOrTraverse = (v) =>
    typeof v === "number" ? v : treeTraversalDFS(v);

  return calc(numOrTraverse(lh), numOrTraverse(rh), op);
};

const furthestIndex = (str, strAr) => {
  return strAr.reduce((acc, toFind) => {
    const lastIndex = str.lastIndexOf(toFind);
    if (acc > lastIndex) {
      return acc;
    }
    return lastIndex;
  }, -1);
};

describe("Canva interview", function () {
  describe("furthestIndex", () => {
    describe("for str=1234567890", () => {
      it("when searching for 3 and 1 it finds", () => {
        expect(furthestIndex("1234567890", ["3", "1"])).toEqual(2);
      });

      it("when searching for nothing it returns -1", () => {
        expect(furthestIndex("1234567890", ["99"])).toEqual(-1);
      });

      it("when searching for something not in str it returns -1", () => {
        expect(furthestIndex("1234567890", ["99"])).toEqual(-1);
      });
    });
  });

  describe("tokenise", () => {
    it("tokenises 5 * 4 - 3 - 5 ^ 3", () => {
      expect(tokenise("5 * 4 - 3 - 5 ^ 3")).toEqual(tree);
    });

    it("tokenises 5 * 4 - 3 * 5 ^ 3 - 7 * 5 ^ 4", () => {
      expect(tokenise("5 * 4 - 3 * 5 ^ 3 - 7 * 5 ^ 4")).toEqual(tree1);
    });
  });

  it("2 - 2 = 0", () => {
    expect(treeTraversalDFS(tokenise("2 - 2"))).toEqual(0);
  });

  it("2 + 2 = 4", () => {
    expect(treeTraversalDFS(tokenise("2 + 2"))).toEqual(4);
  });

  it("2 / 2 = 1", () => {
    expect(treeTraversalDFS(tokenise("2 / 2"))).toEqual(1);
  });

  it("2 + 2 - 9 = -5", () => {
    expect(treeTraversalDFS(tokenise("2 + 2 - 9"))).toEqual(-5);
  });

  it("2 - 2 * 7 = -12", () => {
    expect(treeTraversalDFS(tokenise("2 - 2 * 7"))).toEqual(-12);
  });

  it("2 ^ 9 - 2 * 7 = 498", () => {
    expect(treeTraversalDFS(tokenise("2 ^ 9 - 2 * 7"))).toEqual(498);
  });

  it("5 * 4 - 3 * 5 ^ 3 - 7 * 5 ^ 4 = -4730", () => {
    expect(treeTraversalDFS(tokenise("5 * 4 - 3 * 5 ^ 3 - 7 * 5 ^ 4"))).toEqual(
      -4730,
    );
  });

  it("5 * 4 - 3 - 5 ^ 3 = -108", () => {
    expect(treeTraversalDFS(tokenise("5 * 4 - 3 - 5 ^ 3"))).toEqual(-108);
  });

  it("5 * 4 - 3 - 5 ^ 3 + 5 = -103", () => {
    expect(treeTraversalDFS(tokenise("5 * 4 - 3 - 5 ^ 3 + 5"))).toEqual(-103);
  });

  it("5 * 4 - 3 - 5 ^ 3 + 5 - 108 / 3 = -139", () => {
    expect(
      treeTraversalDFS(tokenise("5 * 4 - 3 - 5 ^ 3 + 5 - 108 / 3")),
    ).toEqual(-139);
  });

  it("8 + 8 + 8 + 8 + 8 + 8 + 8 + 8 + 8 + 8 ^ 2 = 136", () => {
    expect(
      treeTraversalDFS(tokenise("8 + 8 + 8 + 8 + 8 + 8 + 8 + 8 + 8 + 8 ^ 2")),
    ).toEqual(136);
  });

  it("1 / 0 = Infinity", () => {
    expect(treeTraversalDFS(tokenise("1 / 0"))).toEqual(Infinity);
  });
});