2022-2023 - Class 2

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).