Questions d'entretien

Entretien pour Front End Engineer

-Menlo Park, CA

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 ?

Répondre

Réponses aux questions d'entretien

24 réponse(s)

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

Utilisateur anonyme le

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 le

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; }, []);

Utilisateur anonyme le

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 le

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 le

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; }

Utilisateur anonyme le

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; });

Utilisateur anonyme le

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 le

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 }

Utilisateur anonyme le

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 le

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 le

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; }) }

1

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

Utilisateur anonyme le

0

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

Utilisateur anonyme le

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; }

Utilisateur anonyme le

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 le

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));

Utilisateur anonyme le

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 le

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))

Utilisateur anonyme le

0

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

Dmitry le

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; }

Utilisateur anonyme le

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 le

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 le

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; }

Utilisateur anonyme le

Ajouter des réponses ou des commentaires

Pour commenter ceci, connectez-vous ou inscrivez-vous.