daily log 11.12.20

Goals for today: No side chatter Say time/space complexity Break the problem down into smaller problems and solve those first

without using length, tell me the length of the string Counter = 0 For s in string: Counter +=1 Return counter

TIME: O(N) SPACE: O(1)

ignoring space and time complexity, return a reversed string

My_stack = [] My_reversed_string = ‘’ For s in string: My_stack.append(s)

While len(my_stack) != 0: My_reversed_string = My_reversed_string + my_stack.pop()

Return my_reversed_string

TIME: O(2N) –> O(N) SPACE: O(2N) → O(N)

what is the most frequently repeated character in a string

Test_string = ‘books’ My_dict = {} For s in string: If s in my_dict: My_dict[s] = my_dict[s] + 1 Else: My_dict[s] = 1

Current_max_value = 0 Current_max_key = 0 For key, value in my_dict.items(): If value > current_max_value: Current_max_value = value Current_max_key = key

Return current_max_key

TESTING: My_dict { b: 1, o: 2, k: 1, s: 1}

TIME: O(N) SPACE: O(26) → O(1) (bound by alphabet)

Given a string, find the first non-repeating character in it and return its index. If it doesn’t exist, return -1

Test_string = ‘tacoocat’

frequency = {} For s in string: If s in frequency: Frequency[s] = frequency[s] + 1 Else: Frequency[s] = 1

For i,s in enumerate(string): If frequency[s] == 1: Return i

Return -1

TIME: O(2N) → O(N) SPACE: O(26) → O(1)

Test_string = ‘tacocat’ Test_string = ‘tacocard’

reverse a string in-place For i, s in enumerate(string): // 0,t Halfwaypoint = Math.floor(len(string)/2) // 4 If i <= Halfwaypoint: Temp = s // t String[i] = string[len(string) - i] // d string[len(string) - i] = temp // t

TIME: O(½ N) → O(N) SPACE: O(1)

Two pointers: I = 1 J = len(string) -1

j i Ta

i j tad

While i != j
//swap I = i + 1 J = j - 1

While i <= j
//swap I = i + 1 J = j - 1

in a sorted string, tell me if the letter exists

abcde

Mid_point = len(string)/2

If string[mid_point] = letter: Return True

Else if string[mid_point] < letter: // search again, right

Else if string[mid_point] > letter: // search again, left

Else: Return False

ORIGINAL

I = 0 J = len(string) -1 Midpoint

While i <= j:

If string[mid_point] = letter:
	Return True

if string[mid_point] < letter: I = midpoint Midpoint = (j+i)/2 if string[mid_point] > letter: J = midpoint Midpoint = (j+i)/2 Return False

PATS I = 0 J = len(string) -1 Midpoint

While i <= j: Midpoint = (j+i)/2

If string[mid_point] = letter:
	Return True

Else if string[mid_point] < letter: I = midpoint

Else if string[mid_point] > letter: J = midpoint

Return False

Ask me assumptions: frequent char -> what if multiple same answers No-repeatijg -> in a row or across whole string?