Interview Question

Front End Engineer Interview

-Menlo Park, CA

Facebook

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 ?

Answer

Interview Answers

23 Answers

2

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

Anonymous on

1

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

Anonymous on

0

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

Anonymous on

0

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

Anonymous on

0

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

Anonymous on

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

Anonymous on

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 on

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 on

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 on

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

Anonymous on

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 on

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

Anonymous on

0

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

Dmitry on

0

Except for a typo, it has O(n^2) complexity which I believe is the main problem here. I think they expect you to come up with search indexes for each key with O(1) lookup. Here's an example of how it might look like → https://gist.github.com/vitkarpov/02e53a29dd786771d33ea499c5a400ed. If you're preparing for interviews and want to find a community to find some help & share with other people as well → drop me a line, I created a dedicated Slack for that 😊

Viktor Karpov on

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

Anonymous on

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 on

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 on

0

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 on

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 }

Anonymous on

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 on

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 on

0

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 on

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

Anonymous on

One or more comments have been removed.
Please see our Community Guidelines or Terms of Service for more information.

Add Answers or Comments

To comment on this, Sign In or Sign Up.