As I know, Object in Javascript acts like a hash (associative array). Therefore, I think the time complexity will be always O(1) when I get a value by a key in an Object like this obj['a'], no matter how many keys in obj. However, an interviewer challenged me about this.
He gave me a question: find the intersection between two unsorted arrays (no duplicate).
My solution is that go through the first array and create hash for every elements, and then loop the second array, if elements in second array are in hash, then push it to output.
The code likes this:
function findIntersection(ary1, ary2) {
var hash = {};
var output = [];
ary1.forEach((v) => {
hash[v] = true;
});
ary2.forEach((v) => {
if (hash[v]) {
output.push(v);
}
});
return output;
}
I explained that the complexity is O(m+n), m and n are the length of input arrays. But the interviewer seemed not agree this. He kept ask that are you sure hash[v] to get a value is O(1), tell me how Javascript achieves hash[v].
Is the time complexity of hash[v] not O(1)? If it's not, how to re-write my code to achieve linear time complexity using correct hash structure ?
This struck at the very foundations of my Javascript learnings.
