3 ms·
Quadratic algorithms are slow (and hashmaps are fast)
- raymondh 5y agoFor those interested in how Python's hashmaps (dictionaries) work, here is a video that starts with first principles and then covers all the other innovations present in CPython (versioning, compactness, ordering, etc): https://www.youtube.com/watch?v=npw4s1QTmPg https://www.youtube.com/watch?v=npw4s1QTmPg
- vlovich123 5y agoI mean if you're already converting to set, why not just do return list(set(list1).intersection(list2)) The downside of the "convert to set approach" is O(n) memory (+ time spent converting to a set that's ignored by big-O analysis). If the 2 lists are both sorted (as they are in the original example), then there's an O(n) algorithm that uses O(1) space by keeping offsets into each list & moving the pointer forward on the list with the smaller value at the pointer (noting spots of equality). There's some care that has to be done for duplicate elements but it should be trivial.