# LeetCode (Best Time to Buy and Sell Stock I, II, III, IV etc.)

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

## 1. Best Time to Buy and Sell Stock (Easy)

`    # 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`

## 2. Best Time to Buy and Sell Stock II (Easy)

`    # Time O(N) Space O(1)    def maxProfit(self, prices: List[int]) -> int:                if…`

# LeetCode (Course Schedule I, II, III, IV)

## 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:            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) …`

# Graph (Topological Sort)

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/

`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.1Input:[  "wrt",  "wrf",  "er",  "ett",  "rftt"]Output: "wertf"Eg.2Input:[…`

# LFU Cache

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

`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): https://leetcode.com/problems/lru-cache/

`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…`

# Sorting Algorithms

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.

## 1. Pancake Sort

LeetCode 969. Pancake Sorting (Medium):

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

`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

## 1. Single Number

`a^a = 0a^0 = aa^b^a = (a^a)^b = 0^b = ba^b^c^a^c = (a^a)^(c^c)^b = 0^b = b`
`# Time O(N) Space O(1)def singleNumber(self, nums: List[int]) -> int:    output = 0    for num in nums:        output ^= numreturn output`

## 2. Single Number II

`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 = aa XOR a XOR a XOR b XOR b XOR b…`

# Bit Manipulation (Part I)

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

## 1. and, or, not, xor

`a & ba | b~a, ~ba ^ b (a or b, but not both)e.g. a ^ 0   --->   ae.g. a ^ a   --->   0e.g. a ^ b ^ a = 0 ^ b = b`

## 2. shift

`a >> num, b << nume.g. 0000 0001 << 2 ---> 0000 0100e.g. 1000 0000 >> 3 ---> 0001 0000e.g. pow(2,5) is the…` ## Jing Dong

Software Engineer