Solutions - FB Technical Screen Interview Guide (Algorithms)

fbTechnicalScreen.js

// Max Ice Cream (3/3)
var maxIceCream = function(costs, coins) {
    costs.sort();
    for (let i = 0; i < costs.length; i++) {
        if (coins >= costs[i]) {
            coins -= costs[i];
        } else {
            return i
        }
    }
    
    return costs.length;
};



// Queue with Two Stacks (3/2)
// https://www.youtube.com/watch?v=7ArHz8jPglw



// Balanced Brackets (3/1)
// if stack length is ever bigger than string length / 2, then return false
// if we finish processing string and stack isn't empty, return false

function isBalanced(s) {
    const map = { '}': '{', ')': '(', ']': '[' };
    const stack = [];
    
    for (let i = 0; i < s.length; i++) {
        if (stack.length > s.length / 2) return 'NO';
        const char = s[i];
        if (!(char in map)) {
            stack.push(char);
            continue;
        }
        const closingBracket = stack.pop();
        if (map[char] === closingBracket) continue;
        
        return 'NO';
    }
    
    return stack.length === 0 ? 'YES' : 'NO';
}



// Cycle Detection (3/1)
// note: getting runtime compile error on hacker rank, seems to be their test
function hasCycle(head) {
    if (head === null) return 0;
    let fast = head.next;
    let slow = head;
    while (fast !== slow) {
        if (fast === null || fast.next === null) return 0;
        slow = slow.next;
        fast = fast.next.next;
    }
    
    return 1;
}



// Singly Linked List - Insert Node At Position (3/1) 
function insertNodeAtPosition(llist, data, position) {
    const newNode = new SinglyLinkedListNode(data, null);
    if (llist === null) return newNode;
    if (position === 0) {
        const temp = llist;
        newNode.next = temp;
        return newNode;
    }
    
    let node = llist;
    let currPos = 0;
    
    // stop before position to insert at
    while (node !== null) {
        if (currPos === position - 1) break;
        node = node.next;
        currPos++;
    }
    
    if (node.next === null) {
        node.next = newNode;
    } else {
        const temp = node.next;
        node.next = newNode;
        newNode.next = temp;
    }
    
    return llist;
}



// Rotate Left (3/1)
// would it be possible to do it in o(1) time if we create R temp arrays of length arr.length
// where R is # of rotations, where for every temp arr, 
//
// tbd



// Designer PDF Viewer (3/1)
// how can solution improve?
// 1. could also use word.charCodeAt(i) - 97
// where code 97 to 122 are a-z in charCode
// 2. instead of -infinity, could just also use 0 (height can't be less than that)
// 3. re-think solution using something like `max < h[word.charCodeAt(i) - 97]`
function designerPdfViewer(h, word) {
    const alpha = [
    'a', 'b', 'c', 'd', 'e', 'f',
    'g', 'h', 'i', 'j', 'k', 'l',
    'm', 'n', 'o', 'p', 'q', 'r',
    's', 't', 'u', 'v', 'w', 'x',
    'y', 'z'
    ];
    
    const letterIndicies = {};
    // generate letterIndicies table from string
    for (const letter of word) {
        if (!(letter in letterIndicies)) letterIndicies[letter] = null;
    }
    
    // if char in letterIndicies, store it's index
    for (let i = 0; i < alpha.length; i++) {
        const letter = alpha[i];
        // if letter from alphabet is in letterIndicies, store letter's index
        if (letter in letterIndicies) {
            letterIndicies[letter] = i;
        }
    }
    
    // letterIndicies of letters and their corresponding indicies
    // instead of popularing array, we'll do it in constant space
    // by tracking maxHeight
    let maxHeight = -Infinity;
    for (const letter in letterIndicies) {
        const index = letterIndicies[letter];
        const letterHeight = h[index];
        if (letterHeight > maxHeight) maxHeight = letterHeight; 
    }
    
    return maxHeight * word.trim().length;
}