2022-2023 - Class 2 | Legion of Learners

clarkipeng · 2022-09-20T03:38:58.712Z

Class slides I added annotations to the solutions to the problems from the previous class. Solution to problem on slide 2: # best solution for this problem(in terms of time complexity) is to have a hashtable that stores the numbers present in the array then for each nums[i] you can search if you have already seen a value that is target-nums[i]. Time complexity is O(n) (linear time) present_vals = {} for i,v in enumerate(nums): if target-v in present_vals: return [i, present_vals[target-v]] present_vals[v] = i Solution to problem on slide 3: # solution for this problem is just to iterate through the string of the number and check if each character corresponds to its opposite. Time complexity is O(n) where n is length of base-10 int as string. You can also just use math operations to iterate through the decimal integer(which is faster) but this is more straightforward. x = str(x) length = len(x) for i in range((length +1)/2): # only check first half of string with opposite if x[i] != x[length-i-1]: # or x[i] != x[-1-i] return False return True Solution to problem on slide 6: (I'm not sure whether this is a homework problem or not, if it is, look at the solution after attempting the problem yourself) # solution for this problem is to iterate through each value in each string using native python, you can use zip to concatenate each string row-wise then iterate through them like that. Each iteration you check if all characters in each string is identical. This zip makes makes the code much faster in python compared to iterating with 2 for-loops. Its time complexity is O(n*m). There is a faster way using binary search which is O(m*log(n)). # O(n*m) solution prefix = [] num = len(strs) for x in zip(*strs): if len(set(x))==1: prefix.append(x[0]) else: break return "".join(prefix) # O(log(n)*m) solution (slower in submission because python's native operations are slow, would be faster in compiled languages) n = len(strs[0]) l = 0 r = n ans=0 while(l<=r): m = (l+r)/2 flag = False for str_ in strs: if str_[:m] != strs[0][:m]: r=m-1 flag = True break if flag: continue l = m+1 ans=m return strs[0][:ans] Let me know if you have any questions about the slides or code in this post or need help understanding a problem or its solution (discord is probably your best bet).

top of page

Legion of Learners

www.lol-101.com

Home
Classrooms
Courses
About Us
Resources
Members
More

Use tab to navigate through the menu items.

Questions? Email us at legionoflearners@gmail.com or join our WeChat group!

bottom of page