DFS problem. Same as 46, just to make sure at one level do not repeat duplicates.

DFS practice.

Algorithm1:

1. use a stack to store current set, if len(stack) == len(nums), append stack to res
2. choose a number from nums, append it to stack and mark it as used. DFS to the next level.

Algorithms2:

1. use recursion to build all the possible set simultaneously.

It is a full permutation problem. DFS or BFS both ok.

Merge sort:

1. if head or head.next is none, return head.
2. split the list from middle into A and B
3. recursively merge sort A and B
4. merge sorted A and sorted B

Complexity:

• time: Nlog(N)
• space: recursion call is at most log(N) deep, hence log(N)

Analysis:

Although the problem only asks for implementing two operaions. It actually requires more than that. The two obvious and a few hidden required operations are:

1. get: access value by key in O(1) and update its “freshness”
2. put: add (key, value) pair in data structure and set it to be the freshest
3. delete: delete the least recently used pair
4. update: update pair’s value and “freshness” = delete and move to end

First, if we want “get” to be done in O(1), hashing is a must. And we need to keep track of the “least recently used” element, hence a queue (FIFO) is considered. But if queue is used, updating the freshness of the pair will cost linear time, which is why a linklist should be used. So we can use hashing to map key to a node, where the value is saved. To update a node’s freshness from the linklist, we need to delete it from its original position, for which we need to not only know its next but also its pre — so we need to used double linklist! Finally, to delete the LRU from the hash table, we also need the key stored in the coresponding node. So now we have somthing like:

Trick: Python has a class collections.OrderedDict(), which is a dict that keeps track of the insertion order…

Algorithm:

1. find the loop and record where slow and fast hit
2. set slow = head
3. start traverse again, until the pointers hit again

Analysis:

1. When they first hit, fast is x steps ahead of slow, where x = k * len(loop).
2. So in the second traverse, when slow first enter the loop, fast is exatcly k circles ahead and hit slow again.

Algorithm: Insertion sort

Trick: If a node is greater than the sorted tail, make it the new tail and move on to next.

Algorithm1:

1. traverse both lists and count len(a) and len(b)
2. chop |len(b) - len(a)| nodes from the head of the longer list
3. travese both lists simutaneously until two pointers hit

Algorithm2:

1. let A = A+B, B = B+A such that two lists are alighn by their tails
2. travese both lists simutaneously until two pointers hit

Analysis:

Both algs align the two lists by their tails.

Classic application of two pointers: slow and fast.

Algorithm: when fast catches up with slow, there is cycle.