Skip to content

Instantly share code, notes, and snippets.

@guilsa

guilsa/CS_algorithms.js

Last active May 31, 2022 00:15
Download ZIP

Revisions

  1. guilsa revised this gist May 31, 2022. 1 changed file with 13 additions and 21 deletions.
    34 changes: 13 additions & 21 deletions CS_algorithms.js
    View file
    Original file line number Diff line number Diff line change
    @@ -1997,27 +1997,19 @@ function mergeOverlappingIntervals(array) {

    // o(n) time | o(n) space
    function minHeightBst(array) {
    return helper(array, 0, array.length - 1, null);
    }

    function helper(array, start, end, bst) {
    if (end < start) return;
    const mid = Math.floor((start + end) / 2);
    const newBSTNode = new BST(array[mid]);
    if (bst === null) {
    bst = newBSTNode;
    } else {
    if (array[mid] < bst.value) {
    bst.left = newBSTNode;
    bst = bst.left;
    } else {
    bst.right = newBSTNode;
    bst = bst.right;
    }
    }
    helper(array, start, mid - 1, bst);
    helper(array, mid + 1, end, bst);

    return constructMinHeightBst(array, 0, array.length - 1);
    }

    function constructMinHeightBst(array, startIdx, endIdx) {
    if (endIdx < startIdx) return null;

    const midIdx = Math.floor((startIdx + endIdx) / 2);

    const bst = new BST(array[midIdx]);

    bst.left = constructMinHeightBst(array, startIdx, midIdx - 1);
    bst.right = constructMinHeightBst(array, midIdx + 1, endIdx);

    return bst;
    }

  2. guilsa revised this gist May 31, 2022. 1 changed file with 21 additions and 13 deletions.
    34 changes: 21 additions & 13 deletions CS_algorithms.js
    View file
    Original file line number Diff line number Diff line change
    @@ -1997,19 +1997,27 @@ function mergeOverlappingIntervals(array) {

    // o(n) time | o(n) space
    function minHeightBst(array) {
    return constructMinHeightBst(array, 0, array.length - 1);
    }

    function constructMinHeightBst(array, startIdx, endIdx) {
    if (endIdx < startIdx) return null;

    const midIdx = Math.floor((startIdx + endIdx) / 2);

    const bst = new BST(array[midIdx]);

    bst.left = constructMinHeightBst(array, startIdx, midIdx - 1);
    bst.right = constructMinHeightBst(array, midIdx + 1, endIdx);

    return helper(array, 0, array.length - 1, null);
    }

    function helper(array, start, end, bst) {
    if (end < start) return;
    const mid = Math.floor((start + end) / 2);
    const newBSTNode = new BST(array[mid]);
    if (bst === null) {
    bst = newBSTNode;
    } else {
    if (array[mid] < bst.value) {
    bst.left = newBSTNode;
    bst = bst.left;
    } else {
    bst.right = newBSTNode;
    bst = bst.right;
    }
    }
    helper(array, start, mid - 1, bst);
    helper(array, mid + 1, end, bst);

    return bst;
    }

  3. guilsa revised this gist May 30, 2022. 1 changed file with 44 additions and 0 deletions.
    44 changes: 44 additions & 0 deletions CS_algorithms.js
    View file
    Original file line number Diff line number Diff line change
    @@ -155,6 +155,50 @@ const minMeetingRooms = (intervals) => {



    // Course Schedule (5/1)
    var canFinish = function (numCourses, prerequisites) {
    const graph = makeGraph(prerequisites);
    const globalSeen = new Set();

    for (const [node, _] of Object.entries(graph)) {
    const seen = new Set();
    const isNotCyclic = checkForCycle(graph, globalSeen, seen, node);
    if (!isNotCyclic) return false;
    }

    return true;
    };

    function checkForCycle(graph, globalSeen, seen, node) {
    if (graph[node] === undefined) return true;
    if (globalSeen.has(node)) return true;

    seen.add(node);

    for (const next of graph[node]) {
    if (seen.has(next)) return false;
    const isNotCyclic = checkForCycle(graph, globalSeen, seen, next);
    if (!isNotCyclic) return false;
    }

    globalSeen.add(node);
    seen.delete(node);

    return true;
    }

    function makeGraph(prerequisites) {
    const graph = {};
    for (const [course, dependency] of prerequisites) {
    if (!graph[dependency]) graph[dependency] = [];
    graph[dependency].push(course);
    }

    return graph;
    }



    // Word Search (4/28)
    // for each char of word, we have 4 choices of neighbors to explore
    // so if total # of chars is S, one invocation of dfs is 4^S time
  4. guilsa revised this gist May 13, 2022. 1 changed file with 8 additions and 11 deletions.
    19 changes: 8 additions & 11 deletions CS_algorithms.js
    View file
    Original file line number Diff line number Diff line change
    @@ -127,17 +127,14 @@ class Trie {

    // Meeting Rooms 2 (5/3)

    // As we traverse through our meetings (sorted by their start time)
    // we keep track of all ongoing events and the next event that ends
    // - We do this using a heap for the constant time access to the next
    // event that ends and some other properties I speak about below.
    // - For each event:
    // - Run a comparison and remove (in log n time) the next meeting in
    // the min heap, if it's ended.
    // - Add the end time of our current meeting to the heap
    // (also a log n time operation)
    // - Finally, given that the total amount of ongoing events changes,
    // re-compute max rooms needed
    // Traverse through each event - a meeting - (sorted by their start time)
    // and track all ongoing events and the "next" one that will end.
    // A min heap gives us constant time access to this (next event that will end).
    // For each event:
    // - Compare and remove (in log n time) the next meeting in the min heap, if it's ended.
    // - Add the end time of our current meeting to the heap (also a log n time operation)
    // - Finally, given the total amount of ongoing events changes, re-compute max rooms needed

    const minMeetingRooms = (intervals) => {
    const compareFunc = (a, b) => a - b;
    const minHeap = new MinHeap(compareFunc);
  5. guilsa revised this gist May 13, 2022. 1 changed file with 37 additions and 17 deletions.
    54 changes: 37 additions & 17 deletions CS_algorithms.js
    View file
    Original file line number Diff line number Diff line change
    @@ -1,27 +1,47 @@
    /*
    Climbing Stairs (5/13)
    - can be modeled as a graph problem
    - starting from 0 we can take 1 step and get to 1 or take 2 steps and get to 2
    - then from 1 we can take 1 step and get to 2 or take 2 steps and get to 3, and so on
    - if we get to n from a branch, we've found one way
    - recursion can be used to count number of unique paths that can count to n
    - to avoid repeated work, we can cache
    - if we don't cache, it's 2^n time because we must branch out two ways, n times
    - if we cache, it's linear time/space
    - finally, we can reduce to constant space by computing total distinct ways
    on the fly from n stairs down to 0 stairs given the observation that
    there is 1 way to get to n, 2 ways to get to n-1 and 3 ways to get to n-2
    which I believe can be summarized in f(n - 1) + f(n - 2)
    */
    // Climbing Stairs (5/13)
    // - can be modeled as a graph problem
    // - starting from 0 we can take 1 step and get to 1 or take 2 steps and get to 2
    // - then from 1 we can take 1 step and get to 2 or take 2 steps and get to 3, and so on
    // - if we get to n from a branch, we've found one way
    // - recursion can be used to count number of unique paths that can count to n
    // - to avoid repeated work, we can cache
    // - if we don't cache, it's 2^n time because we must branch out two ways, n times
    // - if we cache, it's linear time/space
    // - finally, we can reduce to constant space by computing total distinct ways
    // on the fly from n stairs down to 0 stairs given the observation that
    // there is 1 way to get to n, 2 ways to get to n-1 and 3 ways to get to n-2
    // which I believe can be summarized in f(n - 1) + f(n - 2)

    // time o(n) | space o(1)
    function climbStairs(n) {
    if (n === 2) return 2;
    if (n === 1) return 1;
    if (n < 1) return 0;
    let nextPlusOne = 1;
    let next = 2;
    let distinctWays = 0;
    for (let i = n - 3; i >= 0; i--) {
    distinctWays = next + nextPlusOne;
    nextPlusOne = next;
    next = distinctWays;
    }
    return distinctWays;
    };

    // time o(n) | space o(n)
    function climbStairs(n, cache = {1: 1, 2: 2}) {
    if (n in cache) {
    return cache[n];
    }
    cache[n] = climbStairs(n - 1, cache) + climbStairs(n - 2, cache);
    return cache[n];
    };


    // Min Path Sum (5/9)

    // DP makes it o(n)
    // without it its more expensive, 2^n
    var minPathSum = function (grid) {
    function minPathSum(grid) {
    const seen = {};
    return dfs(grid, 0, 0, seen);
    };
  6. guilsa revised this gist May 13, 2022. 1 changed file with 50 additions and 1 deletion.
    51 changes: 50 additions & 1 deletion CS_algorithms.js
    View file
    Original file line number Diff line number Diff line change
    @@ -137,8 +137,57 @@ const minMeetingRooms = (intervals) => {
    };


    // IsPanlindrome (4/24)

    // Word Search (4/28)
    // for each char of word, we have 4 choices of neighbors to explore
    // so if total # of chars is S, one invocation of dfs is 4^S time
    // therefore upper bound is o(m*n*4^S) time where m is grid row and n is grid col

    // can be modeled as a graph problem and a dfs approach can be used to
    // explore every possible path starting from each cell to a target cell
    // so a possible start of a word to the end of a word
    // at each new location, slice a character off of the word if they match (2 base cases here)
    // we can optimize by initializing a visited set at the beginning of every exploration
    // adding to the set before visiting new locations and removing it if unsuccessful
    function wordExists(board, word) {
    for (let row = 0; row < board.length; row++) {
    for (let col = 0; col < board[row].length; col++) {
    if (board[row][col] !== word[0]) continue;
    const seen = new Set();
    if (dfs(board, word, row, col, seen)) return true;
    }
    }

    return false;
    };

    function dfs(board, word, row, col, seen) {
    if (word.length === 0) return true;
    if (seen.has(`${row}_${col}`)) return false;
    if (row < 0 || col < 0) return false;
    if (row > board.length - 1 || col > board[row].length - 1) return false;

    const char = board[row][col];
    if (char !== word[0]) return false;

    seen.add(`${row}_${col}`);
    const newWord = word.slice(1, word.length);

    if (
    dfs(board, newWord, row + 1, col, seen) ||
    dfs(board, newWord, row - 1, col, seen) ||
    dfs(board, newWord, row, col + 1, seen) ||
    dfs(board, newWord, row, col - 1, seen)
    )
    return true;

    seen.delete(`${row}_${col}`);
    return false;
    }



    // IsPanlindrome (4/24)
    // Basics of head/tail in recursion
    function isPalindrome(str) {
    if (str.length < 2) return true;
  7. guilsa revised this gist May 13, 2022. 1 changed file with 55 additions and 19 deletions.
    74 changes: 55 additions & 19 deletions CS_algorithms.js
    View file
    Original file line number Diff line number Diff line change
    @@ -1,23 +1,57 @@
    /*
    Climbing Stairs (May 13)
    - can be modeled as a graph problem
    - starting from 0 we can take 1 step and get to 1 or take 2 steps and get to 2
    - then from 1 we can take 1 step and get to 2 or take 2 steps and get to 3, and so on
    - if we get to n from a branch, we've found one way
    - recursion can be used to count number of unique paths that can count to n
    - to avoid repeated work, we can cache
    - if we don't cache, it's 2^n time because we must branch out two ways, n times
    - if we cache, it's linear time/space
    - finally, we can reduce to constant space by computing total distinct ways
    on the fly from n stairs down to 0 stairs given the observation that
    there is 1 way to get to n, 2 ways to get to n-1 and 3 ways to get to n-2
    which I believe can be summarized in f(n - 1) + f(n - 2)
    Climbing Stairs (5/13)
    - can be modeled as a graph problem
    - starting from 0 we can take 1 step and get to 1 or take 2 steps and get to 2
    - then from 1 we can take 1 step and get to 2 or take 2 steps and get to 3, and so on
    - if we get to n from a branch, we've found one way
    - recursion can be used to count number of unique paths that can count to n
    - to avoid repeated work, we can cache
    - if we don't cache, it's 2^n time because we must branch out two ways, n times
    - if we cache, it's linear time/space
    - finally, we can reduce to constant space by computing total distinct ways
    on the fly from n stairs down to 0 stairs given the observation that
    there is 1 way to get to n, 2 ways to get to n-1 and 3 ways to get to n-2
    which I believe can be summarized in f(n - 1) + f(n - 2)
    */



    // Add and Search Words (May 5)


    // Min Path Sum (5/9)

    // DP makes it o(n)
    // without it its more expensive, 2^n
    var minPathSum = function (grid) {
    const seen = {};
    return dfs(grid, 0, 0, seen);
    };

    function dfs(grid, row, col, seen) {
    if (seen[`${row}_${col}`]) return seen[`${row}_${col}`];

    if (
    row < 0 ||
    col < 0 ||
    row > grid.length - 1 ||
    col > grid[row].length - 1
    ) {
    return Number.POSITIVE_INFINITY;
    }

    if (row === grid.length - 1 && col === grid[row].length - 1) {
    return grid[row][col];
    }

    seen[`${row}_${col}`] =
    grid[row][col] +
    Math.min(dfs(grid, row, col + 1, seen), dfs(grid, row + 1, col, seen));

    return seen[`${row}_${col}`];
    }



    // Add and Search Words (5/5)

    // time - o(M) for well defined words, worse case o(M.26^N)
    // space - O(1) for well defined words, worst case o(M)
    @@ -71,7 +105,8 @@ class Trie {



    // Meeting Rooms 2 - May 3
    // Meeting Rooms 2 (5/3)

    // As we traverse through our meetings (sorted by their start time)
    // we keep track of all ongoing events and the next event that ends
    // - We do this using a heap for the constant time access to the next
    @@ -102,8 +137,9 @@ const minMeetingRooms = (intervals) => {
    };


    // Recursion (basics of head/tail in recursion) - April 24
    // IsPanlindrome
    // IsPanlindrome (4/24)

    // Basics of head/tail in recursion
    function isPalindrome(str) {
    if (str.length < 2) return true;
    const head = str[0];
  8. guilsa revised this gist May 13, 2022. No changes.
  9. guilsa revised this gist May 13, 2022. 1 changed file with 19 additions and 0 deletions.
    19 changes: 19 additions & 0 deletions CS_algorithms.js
    View file
    Original file line number Diff line number Diff line change
    @@ -1,3 +1,22 @@
    /*
    Climbing Stairs (May 13)
    - can be modeled as a graph problem
    - starting from 0 we can take 1 step and get to 1 or take 2 steps and get to 2
    - then from 1 we can take 1 step and get to 2 or take 2 steps and get to 3, and so on
    - if we get to n from a branch, we've found one way
    - recursion can be used to count number of unique paths that can count to n
    - to avoid repeated work, we can cache
    - if we don't cache, it's 2^n time because we must branch out two ways, n times
    - if we cache, it's linear time/space
    - finally, we can reduce to constant space by computing total distinct ways
    on the fly from n stairs down to 0 stairs given the observation that
    there is 1 way to get to n, 2 ways to get to n-1 and 3 ways to get to n-2
    which I believe can be summarized in f(n - 1) + f(n - 2)
    */



    // Add and Search Words (May 5)

    // time - o(M) for well defined words, worse case o(M.26^N)
  10. guilsa revised this gist May 6, 2022. 1 changed file with 54 additions and 0 deletions.
    54 changes: 54 additions & 0 deletions CS_algorithms.js
    View file
    Original file line number Diff line number Diff line change
    @@ -1,3 +1,57 @@
    // Add and Search Words (May 5)

    // time - o(M) for well defined words, worse case o(M.26^N)
    // space - O(1) for well defined words, worst case o(M)
    class WordDictionary {
    constructor() {
    this.trie = new Trie();
    }

    addWord(word) {
    this.trie.populate(word);
    }

    search(word) {
    return this.trie.contains(word);
    }
    }

    class Trie {
    constructor(string) {
    this.root = {};
    }

    populate(string) {
    let node = this.root;
    for (const char of string) {
    if (!(char in node)) node[char] = {};
    node = node[char];
    }
    node.isEnd = true;
    }

    contains(string, index = 0, node = this.root) {
    if (index === string.length && node.isEnd) return true;
    if (index === string.length) return false;

    const char = string[index];

    if (char === ".") {
    for (const key in node) {
    if (this.contains(string, index + 1, node[key])) return true;
    }
    } else {
    if (node[char] !== undefined) {
    return this.contains(string, index + 1, node[char]);
    }
    }

    return false;
    }
    }



    // Meeting Rooms 2 - May 3
    // As we traverse through our meetings (sorted by their start time)
    // we keep track of all ongoing events and the next event that ends
  11. guilsa revised this gist May 3, 2022. 1 changed file with 31 additions and 0 deletions.
    31 changes: 31 additions & 0 deletions CS_algorithms.js
    View file
    Original file line number Diff line number Diff line change
    @@ -1,3 +1,34 @@
    // Meeting Rooms 2 - May 3
    // As we traverse through our meetings (sorted by their start time)
    // we keep track of all ongoing events and the next event that ends
    // - We do this using a heap for the constant time access to the next
    // event that ends and some other properties I speak about below.
    // - For each event:
    // - Run a comparison and remove (in log n time) the next meeting in
    // the min heap, if it's ended.
    // - Add the end time of our current meeting to the heap
    // (also a log n time operation)
    // - Finally, given that the total amount of ongoing events changes,
    // re-compute max rooms needed
    const minMeetingRooms = (intervals) => {
    const compareFunc = (a, b) => a - b;
    const minHeap = new MinHeap(compareFunc);

    intervals.sort((a, b) => a[0] - b[0]);

    let maxRooms = 0;
    intervals.forEach((interval) => {
    if (minHeap.size > 0 && minHeap.peek() <= interval[0]) {
    minHeap.extract();
    }
    minHeap.insert(interval[1]);
    maxRooms = Math.max(maxRooms, minHeap.size);
    });

    return maxRooms;
    };


    // Recursion (basics of head/tail in recursion) - April 24
    // IsPanlindrome
    function isPalindrome(str) {
  12. guilsa revised this gist Apr 26, 2022. 1 changed file with 35 additions and 0 deletions.
    35 changes: 35 additions & 0 deletions CS_algorithms.js
    View file
    Original file line number Diff line number Diff line change
    @@ -1,3 +1,38 @@
    // Recursion (basics of head/tail in recursion) - April 24
    // IsPanlindrome
    function isPalindrome(str) {
    if (str.length < 2) return true;
    const head = str[0];
    const mid = str.slice(1, str.length - 1);
    const tail = str[str.length - 1];
    return head === tail && isPalindrome(mid);
    }

    isPalindrome('racecar')

    // Reverse (same as above)
    function reverse(str) {
    if (str.length === 0) return '';
    const head = str[0];
    const tail = reverse(str.slice(1, str.length));
    return tail + head;
    }

    reverse('gh')

    // Concat (same as above)
    function concat(arr) {
    console.log(COUNT)
    if (arr.length === 0) return '';
    const head = arr[0];
    const tail = concat(arr.slice(1, arr.length));
    return head + tail;
    }

    console.log(concat(['Hello', 'World', 'Gui', 'sa']))



    // Shorten Path (3/14)

    // this problem feels hard - it's important to separate out
  13. guilsa revised this gist Mar 15, 2022. 1 changed file with 151 additions and 0 deletions.
    151 changes: 151 additions & 0 deletions CS_algorithms.js
    View file
    Original file line number Diff line number Diff line change
    @@ -1,3 +1,154 @@
    // Shorten Path (3/14)

    // this problem feels hard - it's important to separate out
    // general structure from edge cases
    // maybe you can get help from interviewer about edge cases
    // so prep to set it up correctly by focusing on generalizing it
    // ie. what is considered more important

    // time o(n) | space o(n)
    function shortenPath(path) {
    const startWithSlash = path[0] === "/";
    const tokens = path.split("/").filter(isImportantToken);
    const stack = [];
    if (startWithSlash) {
    stack.push("");
    }
    for (const token of tokens) {
    if (token === "..") {
    if (stack.length === 0 || stack[stack.length - 1] === "..") {
    stack.push(token);
    } else if (stack[stack.length - 1] !== "") {
    stack.pop();
    }
    } else {
    stack.push(token);
    }
    }

    if (stack.length === 1 && stack[0] === "") return "/";
    return stack.join("/");
    }

    function isImportantToken(token) {
    return token.length > 0 && token !== ".";
    }



    // Multi String Search (3/14)
    // recognize there are various ways of solving this problem
    // either using small strings or with big strings
    // and maybe there would be benefits of doing it one way or another
    // or perhaps we really value are space complexity and we might want to go with
    // naive solution without building an auxilary data structure

    // build a modified suffix tree where we dont care for endSymbol at end of suffix
    // bc we'll traverse until we find just that a small string is contained in it
    // not necessarily that it denotes the end of an actual string (ends with *)
    // it will take o(b^2) time/space to build
    // then iterate through all small strings and for each, check if its contained in the suffix trie
    // since largest string in smallest strings has len s
    // there are n small strings so we'll be doing o(ns) time
    // so we have a time complexity of o(b^2) for building plus o(ns) for finding
    // so a total time of o(b^2+ns)
    // similarly space will be o(b^2+n) bc storing is b^2 space, then building same output array of len n

    // time o(b^2 + ns) | space o(b^2 + n)
    function multiStringSearch(bigString, smallStrings) {
    const trie = new SuffixTrie(bigString);
    return smallStrings.map((string) => trie.contains(string));
    }

    class SuffixTrie {
    constructor(string) {
    this.root = {};
    this.construct(string);
    }

    construct(string) {
    for (let i = 0; i < string.length; i++) this.insertAt(i, string);
    }

    insertAt(i, string) {
    let node = this.root;
    for (let j = i; j < string.length; j++) {
    if (!(string[j] in node)) node[string[j]] = {};
    node = node[string[j]];
    }
    }

    contains(string) {
    let node = this.root;
    for (const letter of string) {
    if (!(letter in node)) return false;
    node = node[letter];
    }
    return true;
    }
    }



    // Suffix Trie Construction (3/14)
    // methods
    // populate from string (string)
    // insert at (string, i)
    // contains (string)

    // populate - calls insert at for each index of string
    // insert at - initialize node as root
    // for each letter in string
    // if letter not in node, create new object
    // update node to node[letter]
    // afterwards insert end symbol in current node

    // contains
    // initialize node as root
    // for each letter in string, if not in node, return false
    // return this.endSymbol in node

    // contains - where m is length of input string we're looking for
    // creation - time o(n^2) | space o(n^2)
    // contains - time o(m) | space o(1)
    class SuffixTrie {
    constructor(string) {
    this.root = {};
    this.endSymbol = "*";
    this.populateSuffixTrieFrom(string);
    }

    populateSuffixTrieFrom(string) {
    // for each index in string, insertAt(string, index)
    for (let i = 0; i < string.length; i++) {
    this.insertAt(i, string);
    }
    }

    insertAt(i, string) {
    let node = this.root;
    for (let j = i; j < string.length; j++) {
    const letter = string[j];
    if (!(letter in node)) node[letter] = {};
    node = node[letter];
    }

    node[this.endSymbol] = true;
    }

    contains(string) {
    let node = this.root;
    for (const letter of string) {
    if (!(letter in node)) return false;
    node = node[letter];
    }

    return this.endSymbol in node;
    }
    }



    // Is Valid Subsequence
    // create a pointer to track sequence starting from 0
    // move it everytime we find it in array
  14. guilsa revised this gist Mar 11, 2022. 1 changed file with 1 addition and 0 deletions.
    1 change: 1 addition & 0 deletions CS_algorithms.js
    View file
    Original file line number Diff line number Diff line change
    @@ -2,6 +2,7 @@
    // create a pointer to track sequence starting from 0
    // move it everytime we find it in array
    // if pointer has reached end of sequence, return true
    // in case we reach end of sequence prior to end, break

    // [5, 1, 22, 25, 6, -1, 8, 10]
    // [1, 6, -1, 10]
  15. guilsa revised this gist Mar 11, 2022. 1 changed file with 23 additions and 0 deletions.
    23 changes: 23 additions & 0 deletions CS_algorithms.js
    View file
    Original file line number Diff line number Diff line change
    @@ -1,3 +1,26 @@
    // Is Valid Subsequence
    // create a pointer to track sequence starting from 0
    // move it everytime we find it in array
    // if pointer has reached end of sequence, return true

    // [5, 1, 22, 25, 6, -1, 8, 10]
    // [1, 6, -1, 10]
    // true

    // time o(n) | space o(1)
    function isValidSubsequence(array, sequence) {
    let j = 0;
    for (let i = 0; i < array.length; i++) {
    if (array[i] === sequence[j]) {
    j++;
    }
    }

    return j === sequence.length;
    }



    // Merge Overlapping Intervals (3/8)
    // sort first! with (a, b) => a[0] - b[0]
    // then merge item by item while updating last item from results array
  16. guilsa revised this gist Mar 8, 2022. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion CS_algorithms.js
    View file
    Original file line number Diff line number Diff line change
    @@ -1,11 +1,11 @@
    // Merge Overlapping Intervals (3/8)
    // sort first! with (a, b) => a[0] - b[0]
    // then merge item by item while updating last item from results array
    // recognize to use math.max (must decide between largest of two)
    // wasn't obvious at first - this is the caveat:
    // if prev end is greater than or equal to curr start
    // then set prev end to largest between prev end and curr end

    // we must sort first with (a, b) => a[0] - b[0]
    // time o(nlogn) | space o(1)
    function mergeOverlappingIntervals(array) {
    array.sort((a, b) => a[0] - b[0]);
  17. guilsa revised this gist Mar 8, 2022. 1 changed file with 28 additions and 0 deletions.
    28 changes: 28 additions & 0 deletions CS_algorithms.js
    View file
    Original file line number Diff line number Diff line change
    @@ -1,3 +1,31 @@
    // Merge Overlapping Intervals (3/8)
    // then merge item by item while updating last item from results array
    // recognize to use math.max (must decide between largest of two)
    // wasn't obvious at first - this is the caveat:
    // if prev end is greater than or equal to curr start
    // then set prev end to largest between prev end and curr end

    // we must sort first with (a, b) => a[0] - b[0]
    // time o(nlogn) | space o(1)
    function mergeOverlappingIntervals(array) {
    array.sort((a, b) => a[0] - b[0]);

    const merged = [array[0]];
    for (let i = 1; i < array.length; i++) {
    const intervalOne = merged[merged.length - 1];
    const intervalTwo = array[i];
    if (intervalOne[1] >= intervalTwo[0]) {
    merged[merged.length - 1][1] = Math.max(intervalOne[1], intervalTwo[1]);
    continue;
    }
    merged.push(intervalTwo);
    }

    return merged;
    }



    // First Duplicate Value (3/8)
    // we use indicies to map values to each other
    // since valus are 1..n and we can modify input array
  18. guilsa revised this gist Mar 8, 2022. 1 changed file with 46 additions and 0 deletions.
    46 changes: 46 additions & 0 deletions CS_algorithms.js
    View file
    Original file line number Diff line number Diff line change
    @@ -1,3 +1,49 @@
    // First Duplicate Value (3/8)
    // we use indicies to map values to each other
    // since valus are 1..n and we can modify input array
    // use indicies to represent values to generate index
    // if at array[index] we dont have a negative, we set it to be one
    // next time we get to that same value, we'll go to the same index
    // and know that we've seen that value before

    // time o(n) | space o(1)
    function firstDuplicateValue(array) {
    for (const value of array) {
    const absValue = Math.abs(value);
    if (array[absValue - 1] < 0) return absValue;
    array[absValue - 1] *= -1;
    }

    return -1;
    }



    // Array of Products (3/8)
    // array fill strategy
    // continue re-fill by re-computing prev vals at each index
    // gets us to o(n) runtime (good hint if you're stuck on a o(n^2) solution)

    // time o(n) | space o(n)
    function arrayOfProducts(array) {
    const products = new Array(array.length).fill(1);
    let currentProduct = 1;
    for (let i = 0; i < array.length; i++) {
    products[i] = currentProduct;
    currentProduct *= array[i];
    }

    currentProduct = 1;
    for (let i = array.length - 1; i >= 0; i--) {
    products[i] *= currentProduct;
    currentProduct *= array[i];
    }

    return products;
    }



    // Longest Peak (3/8)
    // instead of having i = 0 and inside while, skip if i is 0 or i === len - 1
    // just have i start at 1 and while should end at len - 1
  19. guilsa revised this gist Mar 8, 2022. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion CS_algorithms.js
    View file
    Original file line number Diff line number Diff line change
    @@ -1,10 +1,10 @@
    // Longest Peak (3/8)
    // since it asks for longestPeakDistance, we don't need a `positions` array aux space
    // instead of having i = 0 and inside while, skip if i is 0 or i === len - 1
    // just have i start at 1 and while should end at len - 1
    // instead of left/right, use leftIdx/rightIdx
    // longestPeakLength isn't initialized as -Infinity, just 0

    // since it asks for longestPeakDistance, we don't need a `positions` array aux space
    // time o(n) | space o(1)
    function longestPeak(array) {
    let i = 1;
  20. guilsa revised this gist Mar 8, 2022. 1 changed file with 38 additions and 0 deletions.
    38 changes: 38 additions & 0 deletions CS_algorithms.js
    View file
    Original file line number Diff line number Diff line change
    @@ -1,3 +1,41 @@
    // Longest Peak (3/8)
    // since it asks for longestPeakDistance, we don't need a `positions` array aux space
    // instead of having i = 0 and inside while, skip if i is 0 or i === len - 1
    // just have i start at 1 and while should end at len - 1
    // instead of left/right, use leftIdx/rightIdx
    // longestPeakLength isn't initialized as -Infinity, just 0

    // time o(n) | space o(1)
    function longestPeak(array) {
    let i = 1;
    let longestPeakLength = 0;
    while (i < array.length - 1) {
    const isPeak = array[i - 1] < array[i] && array[i] > array[i + 1];
    if (!isPeak) {
    i++;
    continue;
    }

    let leftIdx = i - 2;
    while (leftIdx >= 0 && array[leftIdx] < array[leftIdx + 1]) {
    leftIdx--;
    }

    let rightIdx = i + 2;
    while (rightIdx < array.length && array[rightIdx] < array[rightIdx - 1]) {
    rightIdx++;
    }

    const currentPeakLength = rightIdx - leftIdx - 1;
    longestPeakLength = Math.max(longestPeakLength, currentPeakLength);
    i = rightIdx;
    }

    return longestPeakLength;
    }



    // Spiral Traverse (3/7)
    // loop 3 and 4 need to break if there's a single row/row left
    // second loop is row = startRow + 1, everything else is minus one
  21. guilsa revised this gist Mar 8, 2022. 1 changed file with 39 additions and 0 deletions.
    39 changes: 39 additions & 0 deletions CS_algorithms.js
    View file
    Original file line number Diff line number Diff line change
    @@ -1,3 +1,42 @@
    // Spiral Traverse (3/7)
    // loop 3 and 4 need to break if there's a single row/row left
    // second loop is row = startRow + 1, everything else is minus one
    // last loop is row >, not row >=
    // last loop is row > startRow, not row > endRow
    // time o(n) | space o(n)
    function spiralTraverse(array) {
    let startRow = 0;
    let endRow = array.length - 1;
    let startCol = 0;
    let endCol = array[0].length - 1;
    const result = [];

    while (startRow <= endRow && startCol <= endCol) {
    for (let col = startCol; col <= endCol; col++) {
    result.push(array[startRow][col]);
    }
    for (let row = startRow + 1; row <= endRow; row++) {
    result.push(array[row][endCol]);
    }
    for (let col = endCol - 1; col >= startCol; col--) {
    if (startRow === endRow) break;
    result.push(array[endRow][col]);
    }
    for (let row = endRow - 1; row > startRow; row--) {
    if (startCol === endCol) break;
    result.push(array[row][startCol]);
    }
    startRow++;
    endRow--;
    startCol++;
    endCol--;
    }

    return result;
    }



    // Monotonic Array (3/7)
    // time o(n) | space o(1)
    function isMonotonic(array) {
  22. guilsa revised this gist Mar 7, 2022. 1 changed file with 15 additions and 0 deletions.
    15 changes: 15 additions & 0 deletions CS_algorithms.js
    View file
    Original file line number Diff line number Diff line change
    @@ -1,3 +1,18 @@
    // Monotonic Array (3/7)
    // time o(n) | space o(1)
    function isMonotonic(array) {
    let isNonDecreasing = true;
    let isNonIncreasing = true;
    for (let i = 1; i < array.length; i++) {
    if (array[i] > array[i - 1]) isNonDecreasing = false;
    if (array[i] < array[i - 1]) isNonIncreasing = false;
    }

    return isNonDecreasing || isNonIncreasing;
    }



    // Move to Element (3/7)
    // we need some left and right idx, i and j
    // iterate through array while incrementing i
  23. guilsa revised this gist Mar 7, 2022. 1 changed file with 28 additions and 0 deletions.
    28 changes: 28 additions & 0 deletions CS_algorithms.js
    View file
    Original file line number Diff line number Diff line change
    @@ -1,3 +1,31 @@
    // Move to Element (3/7)
    // we need some left and right idx, i and j
    // iterate through array while incrementing i
    // decrement j while its j is greater than i and array[j] === toMove
    // if array[i] equals toMove, swap

    // time o(n) - we only visit every index once
    // space o(1)
    function moveElementToEnd(array, toMove) {
    let i = 0;
    let j = array.length - 1;
    while (i < j) {
    while (j > i && array[j] === toMove) j--;
    if (array[i] === toMove) swap(i, j, array);
    i++;
    }

    return array;
    }

    function swap(i, j, array) {
    const temp = array[i];
    array[i] = array[j];
    array[j] = temp;
    }



    // Smallest Difference (3/7)
    // technique takes advantage of properties of a sorting array
    // either dec/inc to bring nums closer to each other
  24. guilsa revised this gist Mar 7, 2022. 1 changed file with 39 additions and 0 deletions.
    39 changes: 39 additions & 0 deletions CS_algorithms.js
    View file
    Original file line number Diff line number Diff line change
    @@ -1,3 +1,42 @@
    // Smallest Difference (3/7)
    // technique takes advantage of properties of a sorting array
    // either dec/inc to bring nums closer to each other
    // javascript .sort needs .((a, b) => a - b)
    // ask interviewer
    // is it ok to sort in place, otherwise account for extra space complexity

    // time - sorting (quicksort or mergesort)
    // time o(nlog(n) + mlog(m))
    // space - constant
    function smallestDifference(arrayOne, arrayTwo) {
    arrayOne.sort((a, b) => a - b);
    arrayTwo.sort((a, b) => a - b);
    let idxOne = 0;
    let idxTwo = 0;
    let smallest = Infinity;
    let smallestPair = [];
    while (idxOne < arrayOne.length && idxTwo < arrayTwo.length) {
    const firstNum = arrayOne[idxOne];
    const secondNum = arrayTwo[idxTwo];
    let current = Math.abs(firstNum - secondNum);
    if (firstNum === secondNum) {
    return [firstNum, secondNum];
    } else if (firstNum < secondNum) {
    idxOne++;
    } else {
    idxTwo++;
    }
    if (current < smallest) {
    smallest = current;
    smallestPair = [firstNum, secondNum];
    }
    }

    return smallestPair;
    }



    // Three Number Sum (3/7)
    // left/right inc/dec based on currentSum
    // but inside a for i loop from 0 through array.length - 2
  25. guilsa revised this gist Mar 7, 2022. 1 changed file with 33 additions and 0 deletions.
    33 changes: 33 additions & 0 deletions CS_algorithms.js
    View file
    Original file line number Diff line number Diff line change
    @@ -1,3 +1,36 @@
    // Three Number Sum (3/7)
    // left/right inc/dec based on currentSum
    // but inside a for i loop from 0 through array.length - 2
    // while resetting left to i + 1 and right to array.length - 1

    // time - iterate through main array once and left/right pointer need to iterate through main array once
    // space - might store every number in array if they are used in some triplets
    // time o(n^2) | space o(n)
    function threeNumberSum(array, targetSum) {
    const triplets = [];
    array.sort((a, b) => a - b);
    for (let i = 0; i < array.length - 2; i++) {
    let left = i + 1;
    let right = array.length - 1;
    while (left < right) {
    let currentSum = array[i] + array[left] + array[right];
    if (currentSum === targetSum) {
    triplets.push([array[i], array[left], array[right]]);
    left++;
    right--;
    } else if (currentSum < targetSum) {
    left++;
    } else {
    right--;
    }
    }
    }

    return triplets;
    }



    // Merge Linked List (2/16)

    // n length of 1st, m length of 2nd
  26. guilsa revised this gist Feb 16, 2022. 1 changed file with 30 additions and 0 deletions.
    30 changes: 30 additions & 0 deletions CS_algorithms.js
    View file
    Original file line number Diff line number Diff line change
    @@ -1,3 +1,33 @@
    // Merge Linked List (2/16)

    // n length of 1st, m length of 2nd
    // time o(n+m) | space o(1)

    // class LinkedList {...}

    function mergeLinkedLists(headOne, headTwo) {
    let p1 = headOne;
    let p1Prev = null;
    let p2 = headTwo;
    while (p1 !== null && p2 !== null) {
    if (p1.value < p2.value) {
    p1Prev = p1;
    p1 = p1.next;
    } else {
    if (p1Prev !== null) p1Prev.next = p2;
    p1Prev = p2;
    p2 = p2.next;
    p1Prev.next = p1;
    }
    }
    // we've runned out of p1 but still have values in p2
    if (p1 === null) p1Prev.next = p2;
    // what is the new correct head of merged linked list
    return headOne.value < headTwo.value ? headOne : headTwo;
    }



    // Reverse Linked List (2/15)
    // three pointers, move them together
    // so long as p2 isnt null, do operations
  27. guilsa revised this gist Feb 15, 2022. 1 changed file with 30 additions and 15 deletions.
    45 changes: 30 additions & 15 deletions CS_algorithms.js
    View file
    Original file line number Diff line number Diff line change
    @@ -1,3 +1,29 @@
    // Reverse Linked List (2/15)
    // three pointers, move them together
    // so long as p2 isnt null, do operations
    // p2 is analogous to "current node" so initialize p1 to null and p2 to head
    // p3 = p2.next, then p2.next = p1, then p1 = p2, then p2 = p3
    // notice the order (reading in reverse helps)
    // we loose p1 the second we do p1 = p2, so before we override p1, we do p2.next = p1, etc

    // time o(n) | space o(1)

    // class LinkedList {...}

    function reverseLinkedList(head) {
    let prevNode = null;
    let currentNode = head;
    while (currentNode !== null) {
    const nextNode = currentNode.next;
    currentNode.next = prevNode;
    prevNode = currentNode;
    currentNode = nextNode;
    }
    return prevNode;
    }



    // Find Loop (2/14)
    // set first/second node to head
    // make second node travel 2x as fast until they meet
    @@ -18,13 +44,8 @@

    // 2nd pointer doesn't matter, it's travelling at a faster than normal pace
    // time o(n) | space o(1)
    // This is an input class. Do not edit.
    class LinkedList {
    constructor(value) {
    this.value = value;
    this.next = null;
    }
    }

    // class LinkedList {...}

    function findLoop(head) {
    let first = head.next;
    @@ -67,12 +88,8 @@ function findLoop(head) {
    // whatever the longest linked list dictates the length
    // plus 1 is if we have a carry at end, there's another loop
    // time o(max(n, m)) + 1 | space o(max(n, m) + 1)
    class LinkedList {
    constructor(value) {
    this.value = value;
    this.next = null;
    }
    }

    // class LinkedList {...}

    function sumOfLinkedLists(linkedListOne, linkedListTwo) {
    const newLinkedListHeaderPointer = new LinkedList(0);
    @@ -102,7 +119,6 @@ function sumOfLinkedLists(linkedListOne, linkedListTwo) {


    // Remove Kth Node from From End (2/14)

    // move first/second pointer, remember to stop on items prev to your "targets"
    // start by moving second to k (counter from 1 to k inclusive)
    // if second is null, remove first (update head.value and head.next), return
    @@ -140,7 +156,6 @@ function removeKthNodeFromEnd(head, k) {


    // Number of Binary Tree Topologies (2/10)

    // time o(n^2) | space o(n)
    function numberOfBinaryTreeTopologies(n, cache = { 0: 1 }) {
    if (n in cache) return cache[n];
  28. guilsa revised this gist Feb 15, 2022. 1 changed file with 5 additions and 6 deletions.
    11 changes: 5 additions & 6 deletions CS_algorithms.js
    View file
    Original file line number Diff line number Diff line change
    @@ -102,13 +102,12 @@ function sumOfLinkedLists(linkedListOne, linkedListTwo) {


    // Remove Kth Node from From End (2/14)
    // move 2nd pointer to k inclusive, from 1 to k
    // if it's null, override head value/next with head.next.value/head.next.next, return
    // otherwise, move both pointers simultaneously until second.next isn't null
    // override first.next to first.next.next (no need to override value, just pointer)

    // careful with off by one errors - work with it shifted left by one
    // this is since we operate on things after leaving while loops
    // move first/second pointer, remember to stop on items prev to your "targets"
    // start by moving second to k (counter from 1 to k inclusive)
    // if second is null, remove first (update head.value and head.next), return
    // otherwise, move first and second together
    // lastly, remove first by updating it entirely (first.next = first.next.next)

    // time o(length) | space o()
    class LinkedList {
  29. guilsa revised this gist Feb 14, 2022. 1 changed file with 48 additions and 1 deletion.
    49 changes: 48 additions & 1 deletion CS_algorithms.js
    View file
    Original file line number Diff line number Diff line change
    @@ -1,5 +1,52 @@
    // Sum of Linked Lists (2/14)
    // Find Loop (2/14)
    // set first/second node to head
    // make second node travel 2x as fast until they meet
    // reset first to head
    // then make both travel together until they meet

    // 1st pointer travels D + P distance
    // try to visualize this where D is linear distance before loop
    // and P is some arc
    // 2nd pointer travels 2D + 2P distance
    // so total distance is whatever 2nd pointer travelled minus P (so minus the arc)
    // which turns out to be 2D + P
    // and then R equals 2D + P - P - D (which is what F travelled)
    // so R = D
    // but we're almost done
    // now we know we need to traverse distance D from where our pointers are
    // that's why we reset first to head and move them together until they meet again

    // 2nd pointer doesn't matter, it's travelling at a faster than normal pace
    // time o(n) | space o(1)
    // This is an input class. Do not edit.
    class LinkedList {
    constructor(value) {
    this.value = value;
    this.next = null;
    }
    }

    function findLoop(head) {
    let first = head.next;
    let second = head.next.next;
    while (first !== second) {
    first = first.next;
    second = second.next.next;
    }
    first = head;

    while (first !== second) {
    first = first.next;
    second = second.next;
    }

    return first;
    }




    // Sum of Linked Lists (2/14)
    // it's ok to start from left to right from least significant digits
    // get sum per column (sumOfValues % 10), get carry per column (sumOfValues // 10)
    // create new linked list node per column
  30. guilsa revised this gist Feb 14, 2022. 1 changed file with 56 additions and 0 deletions.
    56 changes: 56 additions & 0 deletions CS_algorithms.js
    View file
    Original file line number Diff line number Diff line change
    @@ -1,3 +1,59 @@
    // Sum of Linked Lists (2/14)

    // it's ok to start from left to right from least significant digits
    // get sum per column (sumOfValues % 10), get carry per column (sumOfValues // 10)
    // create new linked list node per column
    // add pointers from the last node we had to this next new node
    // move current node to new node

    // things to watch out for:
    // (1)
    // lots of variables
    // carry, nodeOne/Two, valueOne/Two, sumOfValues, newValue, newNode
    // (2)
    // set current node's pointer to next linked list node we just created (currentNode.next = newNode)
    // update current node to be last node we created (currentNode = newNode)
    // (3)
    // while loop contains three OR conditions (keeps running if truthy values found)
    // so instead of creating inner conditions, we conditionalize our values to 0 if null

    // whatever the longest linked list dictates the length
    // plus 1 is if we have a carry at end, there's another loop
    // time o(max(n, m)) + 1 | space o(max(n, m) + 1)
    class LinkedList {
    constructor(value) {
    this.value = value;
    this.next = null;
    }
    }

    function sumOfLinkedLists(linkedListOne, linkedListTwo) {
    const newLinkedListHeaderPointer = new LinkedList(0);
    let currentNode = newLinkedListHeaderPointer;
    let carry = 0;

    let nodeOne = linkedListOne;
    let nodeTwo = linkedListTwo;
    while (nodeOne !== null || nodeTwo !== null || carry !== 0) {
    const valueOne = nodeOne !== null ? nodeOne.value : 0;
    const valueTwo = nodeTwo !== null ? nodeTwo.value : 0;
    const sumOfValues = valueOne + valueTwo + carry;

    const newValue = sumOfValues % 10;
    const newNode = new LinkedList(newValue);
    currentNode.next = newNode;
    currentNode = newNode;

    carry = Math.floor(sumOfValues / 10);
    nodeOne = nodeOne !== null ? nodeOne.next : null;
    nodeTwo = nodeTwo !== null ? nodeTwo.next : null;
    }

    return newLinkedListHeaderPointer.next;
    }



    // Remove Kth Node from From End (2/14)
    // move 2nd pointer to k inclusive, from 1 to k
    // if it's null, override head value/next with head.next.value/head.next.next, return