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:


1. Course Schedule(Medium)

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:

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:

while in_progress:
pre = in_progress.popleft()
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:

  • 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 of non-empty words from the dictionary, where words are sorted lexicographically by the rules of this new language. Derive the order of letters in this language.Eg.1

Output: "wertf"


LFU Cache

LeetCode 460. LFU Cache (Hard):

  • 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 is a tie…

LRU Cache

LeetCode 146. LRU Cache (Medium):

  • Description in short:
Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.Implement the LRUCache class:
- LRUCache(int capacity) Initialize the LRU cache with positive size 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, evict the 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):

  • Description in short:
Given an array of integers arr, sort the array by performing a series of pancake 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…

II. LeetCode questions

  • 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 ^= num
return 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+2c
Solution 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 b XOR b…

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.

I. Basic 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. pow(2,5) is the…

Jing Dong

Software Engineer

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store