Interview Question - e-reader

gistfile1.txt

// other questions
// 1. open ended questions, how do you think gmail optimize
// 3. design google search box, autocomplete etc
Interview Questions:
// Given a passage and range of highlighted words, find the most popular phrase
const highlightedPhrases = [
    [0, 2],             //      xxx
    [0, 10],            //      xxxxXXxxxxx
    [0, 10],            //      xxxxXXxxxxx
    [3, 5],             //         xXX
    [4, 7],             //          XXx
    [4, 7],             //          XXx
    [8, 8],             //             x
    [8, 12],            //              xxxxx
    [4, 12],            //          XXxxxxxxx
];
//Write code that will take passages as input, and returns the range that occurs the most [4, 5].
// BRUTE FORCE SOLUTION
// const rangeCounts = [ 3,3,3,3,6,6,5,5,5,4,4,2,2 ];
// returns [4, 5]
function mostCommonRange(passages) {
    const rangeCounts = [];
    passages.forEach(function(passage) {
        for (let i = passage[0]; i <= passage[1]; i++) {
            rangeCounts[i] = rangeCounts[i] || 0;
            rangeCounts[i]++;
        }
    });
    console.log(rangeCounts.join(","));
    let startRange = -1;
    let endRange = -1;
    let max = -1;
  
    rangeCounts.forEach(function(rangeCount, idx) {
      if (rangeCount > max) {
            max = rangeCount;
            endRange = idx;
            startRange = idx;
        } else if (rangeCount === max) {
            endRange = idx;
        }
    });
    return [startRange, endRange];
}
console.log(mostCommonRange(passagesTest))
// What if [4, 7] became [4, 8]?
// const rangeCounts = [ 3,3,3,3,6,6,5,5,6,4,4,2,2 ];
// There are 2 ranges w/ 6. 
// Candidate should ask for requirements should they return first, second, both, error, etc.
// Return the first. Just ask them how they would change their code to handle this.
// Return the longest. Just ask them how they would change their code again.
// RECURSIVE MERGE SOLUTION
function _merge(passage1, passage2) {
    const start = Math.max(passage1[0], passage2[0]);
    const end = Math.min(passage1[1], passage2[1]);
    
    if (start >= end) {
        return [];
    }
    
    return [Math.max(passage1[0], passage2[0]), Math.min(passage1[1], passage2[1])];
}
function _mergeAll(passages) {
    if (!passages.length) {
        return [];
    }
    
    let merged = passages[0];
    
    for (let i = 1; i < passages.length; i++) {
        merged = _merge(merged, passages[i]);
        if (!merged.length) {
            return [];
        }
    }
    
    return merged;
}
function _mostCommonRangeHelper(passages, idx, curList) {
    if (idx === passages.length) {
        const res = _mergeAll(curList);
        if (!res.length) {
            return [];
        }
        
        return curList;
    }
    
    curList.push(passages[idx]);
    const includeCur = _mostCommonRangeHelper(passages, idx + 1, curList.slice());
    curList.pop();
    const excludeCur = _mostCommonRangeHelper(passages, idx + 1, curList.slice());
    
    if (includeCur.length > excludeCur.length) {
        return includeCur;
    }
    
    return excludeCur;
}
function mostCommonRange(passages) {
    const mostFreq = {};
    return _mergeAll(_mostCommonRangeHelper(passages, 0, []));
}
console.log(mostCommonRange(passagesTest));