4 ms·
> How would you compare three sets of numbers to see if any number was common to all three? Ahm ... I would probably just naively brute force loop over the set
by ralfd 10y ago
> How would you compare three sets of numbers to see if any number was common to all three?
Ahm ... I would probably just naively brute force loop over the sets, because modern CPUs are insanely fast and I am filthy lazy. And if there is a performance problem I super lazily look up the filtering methods of the language-library.
What would the correct answer here be? Make a hash or something for constant lookup cost?
- TN1ck 10y agoIf it's already a set in the language, use intersect. If the numbers are in a array or sth. similiar, make a set and use intersect. https://en.wikipedia.org/wiki/Intersection_(set_theory) https://en.wikipedia.org/wiki/Intersection_(set_theory)
- WorldMaker 10y agoWe here at Company X believe that math is not useful unless it is bespoke, hand-made, artisanal. Please pretend that set theory does not yet exist in this universe, and describe to us the smell of the algorithm you might write to solve this problem.
- dTal 10y agoYou just described the "what", not the "how". The implied context is algorithmic. It'd be like answering a question about sorting lists with "use sort()" - true enough in practical terms, but smart-arsey and deliberately avoiding the meat of the question.
- scriptkiddy 10y agoAssuming whatever language I'm using has an honest implementation of a set data structure and that these sets of numbers are true sets, and thus, contain no duplicate values; I would perform an intersection. With Python(my bread and butter), I would simply use the built in intersection set class method: https://docs.python.org/3/library/stdtypes.html?highlight=set#set.intersection https://docs.python.org/3/library/stdtypes.html?highlight=se...
- wyager 10y agoIf the language has a set data structure available, intersect all 3 sets. If it doesn't, sort all three arrays and iteratively go past the smallest value in each array until you arrive at the same value in each array.
- thebradbain 10y agoWouldn't that have O(n*logn) time at worst: sorting [O(nlogn)] + traversal [O(n)] ? If space complexity is not a requirement, wouldn't it be better to iterate over each list and keep track of the occurrences of a digit in a dictionary (whichever keys have 3 occurrences are thus shared)? That way you could get the value in O(n) time. Or is there something I'm missing?
- mook 10y agoIterating each list is at least O(n) (because you just visited each item). So your dictionary building is in itself O(nlogn). As a minor optimization, when you walk the last list you can build the final list incrementally (check for things with two existing visits).
- StavrosK 10y ago> What would the correct answer here be? "How many times is this going to run? Is it going to be cheaper to do any naive thing and move on to the next ticket, or should I take the time to actually optimize this?" That's usually the correct answer, and one I never see in interviews (either asked or offered).