This session includes the best time to buy and sell stock I, II, III, IV, with a cooldown, with a transaction fee.

- Code:

` # Time O(N) Space O(1), runtime = 68 ms`

def maxProfit(self, prices: List[int]) -> int:

if not prices: return 0

bottom_price = float('inf')

max_profit = 0

for p in prices:

bottom_price = min(bottom_price, p)

max_profit = max(max_profit, p - bottom_price)

return max_profit

- Code:

` # Time O(N) Space O(1) def maxProfit(self, prices: List[int]) -> int: if not prices: return 0 profit = 0 for i in range(1, len(prices)): diff = prices[i] - prices[i-1] if diff > 0…`

Solution: use topological sort

` # Time O(E+V) Space O(E+V), runtime = 212 ms`

def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:

if not prerequisites: return True

pre_course_dict = collections.defaultdict(list)

cc_dict = collections.defaultdict(list)

for c, p in prerequisites:

pre_course_dict[p].append(c)

cc_dict[c].append(p)

result = []

in_progress = collections.deque([])

# find the node donnot have pre requests

vs = []

for v in pre_course_dict.values():

vs += v

for k in pre_course_dict.keys():

if k not in vs:

in_progress.append(k)

while in_progress:

pre = in_progress.popleft()

result.append(pre)

for course in pre_course_dict[pre]:

cc_dict[course].remove(pre) …

Topological Sort:

For all the DAG (directed acyclic graph), there is some kind of order in the graph, and the topological sort can be used here to figure out the order.

LeetCode 269. Alien Dictionary: https://leetcode.com/problems/alien-dictionary/

- Description:

There is a new alien language which uses the latin alphabet. However, the order among letters are unknown to you. You receive a list ofnon-emptywords from the dictionary, wherewords are sorted lexicographically by the rules of this new language. Derive the order of letters in this language.Eg.1

Input:

[

"wrt",

"wrf",

"er",

"ett",

"rftt"

]Output:"wertf"Eg.2 Input…

LeetCode 460. LFU Cache (Hard): https://leetcode.com/problems/lfu-cache/

- Description in short:

Design and implement a data structure for Least Frequently Used (LFU) cache.Implement the LFUCache class: - LFUCache(int capacity) Initializes the object with the capacity of the data structure. - int get(int key) Gets the value of the key if the key exists in the cache. Otherwise, returns -1. - void put(int key, int value) Sets or inserts the value if the key is not already present. When the cache reaches its capacity, it should invalidate the least frequently used item before inserting a new item. For this problem, when there…

LeetCode 146. LRU Cache (Medium): https://leetcode.com/problems/lru-cache/

- Description in short:

Design a data structure that follows the constraints of aLeast Recently Used (LRU) cache.Implement the LRUCache class:

- LRUCache(int capacity) Initialize the LRU cache withpositivesize capacity.

- int get(int key) Return the value of the key if the key exists, otherwise return -1.

- void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation,evictthe least recently used key.Follow up:Could…

Here are a few sorting algorithms I found interesting, and it will be good to know, which is a different thought process from these commonly used sorting algorithms. E.g. bubble sort, selection sort, insertion sort, quick sort, merge sort.

LeetCode 969. Pancake Sorting (Medium):

https://leetcode.com/problems/pancake-sorting/

- Description in short:

Given an array of integers arr, sort the array by performing a series ofpancake flips.In one pancake flip we do the following steps:

- Choose an integer k where 1 <= k <= arr.length.

- Reverse the sub-array arr[1...k].For example, if arr = [3,2,1,4] and we performed a pancake…

- Diagram:

`a^a = 0`

a^0 = a

a^b^a = (a^a)^b = 0^b = b

a^b^c^a^c = (a^a)^(c^c)^b = 0^b = b

- Code:

# Time O(N) Space O(1)

def singleNumber(self, nums: List[int]) -> int: output = 0

for num in nums:

output ^= numreturn output

- Diagram:

Solution 1, using dictionay, time O(N) space O(N)Solution 2. using sort, time O(NlogN) space O(1)Solution 3. Using set, time O(N) space O(N)

a+a+a+b+b+b+c+c = 3a+3b+2cSolution 4. using bitwise XOR, time O(N) space O(1) a XOR a = 0, 0 XOR a = a a XOR a XOR a XOR b XOR…

Bit Manipulation is rarely asked during an interview. But it’s good to know all the basic concepts below in case you get asked. Personally, I haven’t run into any LeetCode questions other than the following concepts.

`a & b`

a | b

~a, ~b

a ^ b (a or b, but not both)

e.g. a ^ 0 ---> a

e.g. a ^ a ---> 0

e.g. a ^ b ^ a = 0 ^ b = b

`a >> num, b << num e.g. 0000 0001 << 2 ---> 0000 0100 e.g. 1000 0000 >> 3 ---> 0001 0000 e.g…`

Software Engineer