This problem sort of made me think about how going for best time on leetcode will sometimes breed bad habits.
This discussion is about problem 1143 : https://leetcode.com/problems/longest-common-subsequence/
When I started to think about what this program could realistically be used for, I tried to extrapolate to different kinds of collections, maybe two articles where the items being compared are words, or other objects. It seems to me that in real
applications, collections could have much more mismatches than would be seen in these strings.
When I submitted the unoptimized solution, I got 97% percentile for time
When I submitted the optimized solution, I got 10% percentile.
So I sort of felt incentivised by the reward system to make the code more limited, but when I tested it on my machine, with a custom worst-case scenario, the code that was slow on leetcode was much faster on some custom "worst case" strings.
Another bad habit I think can come from treating the problem entirely as an abstract exercise, since that too would result in a better time. The question here is asking "what is the length of the longest common subsequence", If you limit your thinking to that question alone, the fastest way would be just to find that number, but in actual application, wouldn't you also want to know what that subsequence is? I don't think that the fast DP way is able to answer that question, if you needed to return the collection, you would need to code it in an entirely different, obviously slower way.
But that would mean more memory and time load on the servers.
I love practicing here, but I also feel like sometimes the format of these questions forces me to think in a way that is
limited to an abstract exercise, and it gets too easy to forget to think about how these algorithms could be adapted for
practical needs. It's too easy to get in the 95th percentile, pat yourself on the back, and move on. There''s a lot more that
can be learned from these solutions if you paste them back into your own machine and experiement with how they might
actually be used in application. What are other bad habits to avoid?
def longestCommonSubsequence_O(collection1, collection2):
# optimized for collections with many mismatches
# to weed out all of the mismatches right away
matches = set.intersection(set(collection1), set(collection2))
collection1 = [item for item in collection1 if item in matches]
collection2 = [item for item in collection2 if item in matches]
dp_array = [0]*(len(collection2) + 1)
for i, item1 in enumerate(collection1):
memory_bit = 0
for j, item2 in enumerate(collection2, 1):
cur_val = dp_array[j]
if item1 == item2:
dp_array[j] = memory_bit + 1
else:
dp_array[j] = max(dp_array[j], dp_array[j-1])
memory_bit = cur_val
return dp_array[-1]
def longestCommonSubsequence(collection1, collection2):
dp_array = [0]*(len(collection2) + 1)
for i, item1 in enumerate(collection1):
memory_bit = 0
for j, item2 in enumerate(collection2, 1):
cur_val = dp_array[j]
if item1 == item2:
dp_array[j] = memory_bit + 1
else:
dp_array[j] = max(dp_array[j], dp_array[j-1])
memory_bit = cur_val
return dp_array[-1]
if __name__ == '__main__':
import time
#lots of mismatches in collections
collection1 = ['a','b','c','d','e','f','g','h','i','j','k','l','m']
collection2 = ['m','n','o','p','q','r','s','t','u','v','w','x','y','z']
start_time = time.perf_counter()
for _ in range(100000):
longestCommonSubsequence(collection1, collection2)
print('non-optimized finished in', time.perf_counter() - start_time)
start_time = time.perf_counter()
for _ in range(100000):
longestCommonSubsequence_O(collection1, collection2)
print('optimized finished in', time.perf_counter() - start_time)
# run
# the method that's slower in leetcode is much faster here, but I wouldn't have known that
'''
non-optimized finished in 5.617266239001765
optimized finished in 0.3257247389992699
'''