I was scrolling through a lot of list vs. range related questions on StackOverflow when I came across in one of the answers that look up in a range
object is a CONSTANT TIME operation! It doesn't make sense how this can be done in O(1), you're going to have to iterate through the range to see if a number exists. Does the range object work like some hashmap/dictionary?
def usingRange(x):
return x in range(0, 100000000)
print(usingRange(9999999))
def noRange(x):
return x in list(range(0, 100000000))
print(noRange(9999999))
%timeit usingRange(9999999)
%timeit noRange(9999999)
I got the outputs as:
True
True
443 ns ± 8.83 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
6.89 s ± 380 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
The reason why I want to know why its constant time is because
I was told not to focus so much on learning "tricks" in Python for Programming Interviews! Because everything you do, you will have TO explain the time complexity, so you either memorize that
i in list1
is O(N) or you iterate using a for loop over the list:for j in range(len(list1)):
if list1[j] == i:
print(True)
else:
print(False)
and then come to the conclusion that it is, in fact, O(N) because to check if an element existed you go have to iterate over each element of the list till the end of the list (worst case). But some constant time operations seem less obvious! I can live with the fact that a loop in a hash table is O(1) because there is a big concept called Hashing (not gone over it yet), but not sure how it works for range
objects.
I was told that it is paramount to know the basics! And do your best to explain every line of what you're writing and why you're writing it in whiteboards. Someone I know was literally ASKED to implement a HASHMAP for an SWE position at a tech VERY FAMOUS company.
I have a LOT of time (1 year) to prepare and be inquisitive about stuff.
No comments:
Post a Comment