Domanda di colloquio

Colloquio per Front End Engineer

-Menlo Park, CA

Meta

Given input: // could be potentially more than 3 keys in the object above items = [ {color: 'red', type: 'tv', age: 18}, {color: 'silver', type: 'phone', age: 20} ... ] excludes = [ {k: 'color', v: 'silver'}, {k: 'type', v: 'tv'}, .... ] function excludeItems(items, excludes) { excludes.forEach(pair => { items = items.filter(item => item[pair.k] === item[pair.v]); }); return items; } 1. Describe what this function is doing... 2. What is wrong with that function ? 3. How would you optimize it ?

Risposta

Risposte di colloquio

24 risposte

6

I agree with converting the excludes to an object, but in order to get linear performance that doesn't depend on the number of excluded things, you have to concatenate the k and v into one value to be used as the key in the object: let excludesObject = {}; excludes.forEach(pair => excludesObject[`${pair.k}_${pair.v}`] = true); Then you can check if an item should be excluded in O(k) time where k is the number of keys in an item. And the whole thing will run in O(nk) where n is the number of items. // if there is some key which is found in the excludesObject, the filter will return false items = items.filter(item => !Object.keys(item).some(key => excludesObject[`${key}_${item[key]}`]); ); Facebook, hire me! lol

Anonimo su

2

function excludeItems(items, excludes) { let excludesMap = excludes.reduce((entry, result)=>{ entry[result.k + result.v] = true; return entry; },{}); return items.reduce( (result, item) => { let updatedObject = Object.keys(item).reduce( (result,key) => { if(!excludesMap[key + item[key]]){ result[key] = item[key] } return result; }, {}) result.push(updatedObject) return result; }, []) }

MJ su

1

This solution will give much faster and immutable result. You can test with performance.now items.reduce((allItems, item) => { if(!excludes.some(exclude=>item[exclude.k] === exclude.v)){ allItems.push(item); } return allItems; }, []);

Anonimo su

1

Time complexity O(n*k) where k is the number of excludes. Nothing change if you change from: for(const item of items){ for(const exclude of excludes) { ... } } to for(const exclude of excludes){ for(const item of items) { ... } } time complexity will be the same. Main problems in this code I see next: 1. typo in the line ```item[pair.k] === item[pair.v]``` should be ```item[pair.k] === pair.v``` 2. overriding incoming parameter, it does not mutate the global items, but still it's bad practice in my opinion. 3. we can rewrite the code without using extra variables. my try: const excludeItems = (items, excludes) => items.filter(item => !excludes.some(({k,v}) => item[k] === v))

evilive su

0

1. new a Map with the key of property names and the value of a Set of values 2. With this random access support, time complexity is the length of items. const map=new Map(); function excludeItems(items, excludes) { excludes.forEach((e)=>{ const key=e[k]; const val=e[v]; if(!map.has(key)) { map.set(key,new Set()); } else map.get(key).add(val); }); items.filter((i)=>{ for(let [key,val] of Object.entries(i)){ if(map.has(key) && map.get(key).has(val)) return false; return true; } }); }

Anonymous su

0

(fix typos in previous post) 1. new a Map with the key of property names and the value of a Set of values 2. With this random access support, time complexity is the length of items. 3. Space complexity is size of excludes function excludeItems(items, excludes) { const map=new Map(); excludes.forEach((e)=>{ const key=e[k]; const val=e[v]; if(!map.has(key)) { map.set(key,new Set()); } map.get(key).add(val); }); items.filter((i)=>{ for(let [key,val] of Object.entries(i)){ if(map.has(key) && map.get(key).has(val)) return false; return true; } }); return items; }

Anonimo su

0

you can map the exclude array into objects of object to make it run in constant time. var excludes = turnIntoMap(excludes); function turnIntoMap(arr){ var hash = {}; arr.forEach(function(val){ if(hash[val[k]]){ hash[val[k]][val[v]] = 1 } else { hash[val[k]] = {}; hash[val[k]][val[v]] = 1 } }); } items.filter(function(item){ for(var key in item){ if(excludes[key]){ if(excludes[key][item[key]]){ return false; } } } return true; });

Anonimo su

0

let newItems = items.reduce((acc, item) => { let result = excludes.some(exclude => item[exclude['k']] === exclude['v']); if (!result) { acc.push(item); } return acc; }, []); console.log(newItems);

use reduce and some to get fast result su

0

function excludeItems(items, excludes) { const keyFormat =(key,value)=>`${key}_${value}`; excludes = excludes.reduce((result, exclude)=>{ result[keyFormat(exclude['k'], exclude['v'])] = true; return result; },{}); return items.filter((item)=>{ for(let key of Object.keys(item)){ if(excludes[keyFormat(key,item[key])]) return false; } return true; }); } const items = [{ color: 'red', type: 'tv', age: 18 }, { color: 'silver', type: 'phone', age: 20 }]; const excludes = [{ k: 'color', v: 'silver' },] console.log(excludeItems(items, excludes)); //Time Complexity: O(E + K * n) {where E: is excludes length, K: keys in the items, n: Total number of items }

Anonimo su

0

// space O(n) time 0(n * k) function excludeItemsBetter(items, excludes) { const map = new Map(); // O(n) for (let i = 0; i { for (const key in item) { const mapKey = `key:${key}-val:${item[key]}`; if (map.has(mapKey)) { return false; } } return true; }); }

Anon su

0

function excludeItemsBetter(items, excludes) { const map = new Map(); for (let i = 0; i { for (const key in item) { const mapKey = `key:${key}-val:${item[key]}`; if (map.has(mapKey)) { return false; } } return true; }); }

Anon su

0

Another solution without remapping the exclusions. function excludeItems(items, excludes) { return items.filter((item) => { return excludes.filter((exclusion) => { return item[exclusion.k] === exclusion.v }).length === 0; }) }

Interview Answer su

1

I guess there's a typo in the question? I don't really get the purpose of "item[pair.k] === item[pair.v]"

Anonimo su

0

function excludeItems(items, excludes) { return excludes.reduce((arr, pair) => { arr.push(items.filter(item => item[pair.k] === pair.v)); return arr; },[]); }

Anonimo su

1

If the objetive is exclude the elements using the excludes filters the function should be: function excludeItems(items, excludes) { excludes.forEach(pair => { items = items.filter(item => item[pair.k] !== pair.v); }); return items; }

Anonimo su

0

build excludes table as follows map = { color: { red: 1, green:1 }, type: { tv: 1 } } Solution: function excludeItems(items, excludes) { let map = {}; for (let exclude of excludes) { let { k, v } = exclude; if (map[k] != null) { map[k][v] = 1; } else { map[k] = { [v]: 1 }; } } return items.filter(item => { for (let key in item) { if (map[key] && map[key][item[key]]) { return false; } } return true; }); }

O(n) time solution su

0

const items = [ {color: 'black', type: 'phone', age: 20}, {color: 'red', type: 'tv', age: 18}, {color: 'silver', type: 'tv', age: 20}, ]; const excludes = [ {k: 'type', v: 'tv'}, {k: 'color', v: 'silver'}, ]; function excludeItems(items, excludes) { excludesObject = {}; excludes.forEach(pair => { excludesObject[pair.k] = pair.v; }); items = items.filter(item => { for (key in excludesObject) { if (item[key] === excludesObject[key]) { return false; }; } return true; }); return items; } console.log(excludeItems(items, excludes));

Anonimo su

0

function excludeItems(items, excludes) { const map = new Map( excludes.map( el => [ el.v, el.k ] ) ); return items.filter(item => ( !Object.keys(item).some(key => map.has(item[key]) && map.get(item[key]) === key) )); }

Alexander su

0

1. Excluding any items that is has an element in the "excludes" collection. 2. (a) "filter" returns anything that is true in the conditional. This is doing the opposite. (b) it's checking item[pair.v], which will never return a value. It should be "item[pair.k] !== pair.v" 3. Currently, it's O(n^2). For each excluding element, it's traversing through the entire 'items' list. A start would be to condense the "excludes" object by creating lists. Ex: excludes = {['k': 'color', 'v': ['blue', 'red', 'purple']] "item[pair.k].includes(pair.v)" ***NOTE: (this is still O(n^2), but it's more efficient than before)*** Not sure how to condense it down to O(n log(n))

Anonimo su

0

"excludes table as follows" answer from above can be improved if replace the constructed object (aka excludes table) with Set.

Dmitry su

0

1. fixing a bug in the filter function. function excludeItems(items, excludes) { excludes.forEach(pair => { items = items.filter(item =>item[pair.k] !== pair.v); }); return items; } 2. optimizing... the function is O(n^2). still we can optimize in worst case O(n^2) but , as soon as it finds excluded condition meets, no need to see remaining excluded pairs. just jumping to next item. Array.forEach or Array.map does not allow bread in the middle of loop while for sentence does. So, I replaved Array.forEach to 'for' sentence. function excludeItems(items, excludes) { let result = items.filter(item => { for(let e = 0; e < excludes.length; e++) { let pair = excludes[e]; if((item[pair.k] === pair.v)) { return false; // moving to next item. no need to see next excluded element } } return true; }); return result; }

Anonimo su

0

(fixing typo) 1. fixing a bug in the filter function. function excludeItems(items, excludes) { excludes.forEach(pair => { items = items.filter(item =>item[pair.k] !== pair.v); }); return items; } 2. optimizing... the function is O(n^2). still we can optimize in worst case O(n^2) but , as soon as it finds an excluded condition meets, no need to see remaining excluded pairs. just jumping to next item. Array.forEach or Array.map does not allow 'break' in the middle of loop while regular FOR sentence does. So, I replaced Array.forEach with FOR sentence. function excludeItems(items, excludes) { let result = items.filter(item => { for(let e = 0; e < excludes.length; e++) { let pair = excludes[e]; if((item[pair.k] === pair.v)) { return false; // moving to next item. no need to see next excluded element } } return true; }); return result; }

Susie.K su

0

I got this problem to in my video interview, The way I solved the problem is re-estrcuturing the excludes array with and Object that the keys are the attributes of the items and the value is a set I was told that the number of attributes of one item is always less than 10 so the overall complexity of my solution was O(10*n)

Anonymous su

2

1. excluding the items according to "excludes" array 2. (a) it's mutable. (b) it runs in a O(n^2) complexity 3. first turn "excludes" array into a map like so: excludes = { color: ['silver', 'gold' ...], type: ['tv', 'phone' ...] } then, rewrite the function like so: function excludeItems(items, excludes) { const newItems = []; items.forEach(item => { let isExcluded = false; for (let key in item) { if (excludes[key].indexOf(item[key]) !== -1) { isExcluded = true; break; } } if (!isExcluded) { newItems.push(item); } }); return newItems; }

Anonimo su

Aggiungi risposte o commenti

Per lasciare un commento, accedi o registrati.